L'algorithme A*
La recherche d'un plus court chemin guidée par une estimation : coût payé, estimation du reste, listes ouverte et fermée, heuristique admissible et cohérente, et ce que devient A* avec une heuristique nulle (Dijkstra) ou seule (recherche gloutonne).
- 26 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
Quelques cartes du deck
Algorithme A* : de quoi s'agit-il ?
Voir la réponse
Recherche de plus court chemin qui développe toujours le nœud de plus petite somme : coût déjà payé depuis le départ plus estimation du coût restant.
La somme f(n) = g(n) + h(n) estime le coût du meilleur chemin passant par n ; avec une estimation admissible, le chemin trouvé quand l'arrivée sort de la liste ouverte est un plus court chemin.
Une grille contient des murs et les déplacements se font dans les quatre directions, à coût 1. A* utilise la distance de Manhattan. Le chemin rendu est-il un plus court chemin ?
- Oui, car un mur ne peut qu'allonger le chemin réel
- Non, la distance de Manhattan doit compter les murs pour être admissible
- Non, A* n'est optimal que sur une grille sans aucun obstacle
- Oui, mais seulement si l'arrivée est dans la même ligne que le départ
Voir la réponse
Oui, car un mur ne peut qu'allonger le chemin réel
La distance de Manhattan est le coût d'un chemin sans mur, donc un minorant du coût réel : elle ne surestime jamais, les murs ne la rendent pas inadmissible.
A* classe les nœuds par f(n) = … + …, où g est le coût déjà payé depuis le départ et h l'estimation du coût restant.
Voir la réponse
A* classe les nœuds par f(n) = g(n) + h(n), où g est le coût déjà payé depuis le départ et h l'estimation du coût restant.
g est connu exactement ; h est une estimation. Mettre g à 0 donne la recherche gloutonne, mettre h à 0 donne Dijkstra.
Heuristique : de quoi s'agit-il ?
Voir la réponse
Estimation rapide à calculer du coût qui reste jusqu'à l'arrivée ; elle guide la recherche sans en garantir seule le résultat.
Une bonne estimation évite d'explorer des cases qui s'éloignent de l'arrivée. Sa qualité fixe le gain de temps, et ses propriétés fixent si le chemin rendu est optimal.