Algorithme de Dijkstra et Best-First-Search#
L’algorithme de Dijkstra fonctionne en visitant les sommets du graphe en commençant par le point de départ de l’objet. Il examine ensuite de manière répétée le sommet le plus proche non encore examiné, en ajoutant ses sommets à l’ensemble des sommets à examiner. Il s’étend vers l’extérieur à partir du point de départ jusqu’à ce qu’il atteigne le but. L’algorithme de Dijkstra est assuré de trouver le plus court chemin entre le point de départ et le but, tant qu’aucun des bords n’a un coût négatif. (J’écris « un chemin le plus court » car il existe souvent plusieurs chemins de longueur équivalente). Dans le diagramme suivant, le carré rose est le point de départ, le carré bleu est le but, et les zones sarcelles montrent quelles zones l’algorithme de Dijkstra a balayées. Les zones sarcelles les plus claires sont celles qui sont les plus éloignées du point de départ, et forment donc la « frontière » de l’exploration :
L’algorithme Greedy Best-First-Search fonctionne de manière similaire, sauf qu’il dispose d’une certaine estimation (appelée heuristique) de la distance du but de tout sommet. Au lieu de sélectionner le sommet le plus proche du point de départ, il sélectionne le sommet le plus proche de l’objectif. La recherche rapide du meilleur chemin n’est pas garantie pour trouver le chemin le plus court. Cependant, elle s’exécute beaucoup plus rapidement que l’algorithme de Dijkstra, car elle utilise la fonction heuristique pour se diriger très rapidement vers l’objectif. Par exemple, si l’objectif se trouve au sud de la position de départ, la fonction Meilleur-Premier-Service de Greedy aura tendance à se concentrer sur les chemins qui mènent vers le sud. Dans le diagramme suivant, le jaune représente les nœuds ayant une valeur heuristique élevée (coût élevé pour atteindre l’objectif) et le noir représente les nœuds ayant une valeur heuristique faible (coût faible pour atteindre l’objectif). Cela montre que le Meilleur-Premier-Recherche Gourmand peut trouver des chemins très rapidement par rapport à l’Algorithme de Dijkstra :
Cependant, ces deux exemples illustrent le cas le plus simple – lorsque la carte n’a aucun obstacle, et que le chemin le plus court est vraiment une ligne droite. Considérons l’obstacle concave tel que décrit dans la section précédente. L’algorithme de Dijkstra travaille plus dur mais il est garanti de trouver un chemin le plus court:
L’algorithme Greedy Best-First-Search en revanche fait moins de travail mais son chemin n’est clairement pas aussi bon:
Le problème est que Greedy Best-First-Search est « gourmand » et essaie d’aller vers le but même si ce n’est pas le bon chemin. Puisqu’il ne considère que le coût pour atteindre le but et ignore le coût du chemin jusqu’à présent, il continue même si le chemin qu’il emprunte est devenu vraiment long.
Ne serait-il pas bien de combiner le meilleur des deux ? A* a été développé en 1968 pour combiner des approches heuristiques comme le Best-First-Search de Greedy et des approches formelles comme l’Algorithme de Dijsktra. Il s’agit d’une approche un peu inhabituelle dans la mesure où les approches heuristiques offrent généralement un moyen approximatif de résoudre les problèmes sans garantir l’obtention de la meilleure réponse. Cependant, A* est construit au-dessus de l’heuristique, et bien que l’heuristique elle-même ne vous donne pas de garantie, A* peut garantir un chemin le plus court.