152
Recherche de plus court chemin sur une carte
FIGURE 8.5 - Quatrième développement.
8.2 L'algorithme A*
L' algorithme A* est une amélioration de l ' algorithme de Dijkstra. En plus de mémoriser pour chaque position le coût du chemin jusqu' à cette position (la variable g) on va
évaluer avec une heuristique la longueur du chemin qu' il reste à parcourir. On aura ainsi
une évaluation de la longueur totale du chemin. Au lieu de développer la feuille qui a le
plus petit g comme dans l ' algorithme de Dijkstra, on développera la feuille qui a le plus
petit chemin estimé. Si on veut garantir que A* trouve le plus court chemin, il est nécessaire que l' heuristique qui évalue la longueur du chemin restant soit admissible, c 'est
à dire qu'elle soit optimiste et qu' elle donne dans tous les cas une longueur de chemin
inférieure ou égale à la longueur réelle du chemin restant.
L' heuristique admissible la plus utilisée avec A* est l ' heuristique de Manhattan. Elle
consiste à considérer que le chemin vers le but est sans obstacles, de façon à calculer
rapidement un minorant du chemin restant à faire. En effet pour des déplacements horizontaux et verticaux, l 'heuristique de Manhattan revient à additionner la valeur absolue
de la différence des abscisses entre la position courante et la position d' arrivée et la valeur
absolue de la différence des ordonnées entre les mêmes points.
On note habituellement l ' heuristique admissible avec un h. La longueur estimée du
chemin passant par une position est notée f, et on calcule f en additionnant le chemin
déjà parcouru et le chemin minimum qui reste à parcourir. On a donc f = g + h.
Le déroulement de l ' algorithme A* est similaire à celui de l ' algorithme de Dijkstra,
excepté qu' on ne développe pas la feuille qui a le g le plus petit mais la feuille qui a le f
le plus petit.
Recherche de plus court chemin sur une carte
FIGURE 8.5 - Quatrième développement.
8.2 L'algorithme A*
L' algorithme A* est une amélioration de l ' algorithme de Dijkstra. En plus de mémoriser pour chaque position le coût du chemin jusqu' à cette position (la variable g) on va
évaluer avec une heuristique la longueur du chemin qu' il reste à parcourir. On aura ainsi
une évaluation de la longueur totale du chemin. Au lieu de développer la feuille qui a le
plus petit g comme dans l ' algorithme de Dijkstra, on développera la feuille qui a le plus
petit chemin estimé. Si on veut garantir que A* trouve le plus court chemin, il est nécessaire que l' heuristique qui évalue la longueur du chemin restant soit admissible, c 'est
à dire qu'elle soit optimiste et qu' elle donne dans tous les cas une longueur de chemin
inférieure ou égale à la longueur réelle du chemin restant.
L' heuristique admissible la plus utilisée avec A* est l ' heuristique de Manhattan. Elle
consiste à considérer que le chemin vers le but est sans obstacles, de façon à calculer
rapidement un minorant du chemin restant à faire. En effet pour des déplacements horizontaux et verticaux, l 'heuristique de Manhattan revient à additionner la valeur absolue
de la différence des abscisses entre la position courante et la position d' arrivée et la valeur
absolue de la différence des ordonnées entre les mêmes points.
On note habituellement l ' heuristique admissible avec un h. La longueur estimée du
chemin passant par une position est notée f, et on calcule f en additionnant le chemin
déjà parcouru et le chemin minimum qui reste à parcourir. On a donc f = g + h.
Le déroulement de l ' algorithme A* est similaire à celui de l ' algorithme de Dijkstra,
excepté qu' on ne développe pas la feuille qui a le g le plus petit mais la feuille qui a le f
le plus petit.