Recherche gloutonne (meilleur d’abord)
Puis-je arriver plus vite en fonçant vers le but ?
Développe toujours la case qui semble la plus proche du but. Rapide en terrain dégagé, mais il peut renvoyer un long chemin.
Le meilleur d’abord glouton est l’algorithme de Dijkstra avec une autre priorité. Au lieu du coût déjà payé, il ordonne la frontière par une heuristique : une estimation de la distance restante. Il plonge vers le but.
En terrain dégagé, il développe très peu de cases. Autour d’un obstacle, il paie son obstination : il continue de pousser contre le mur qui fait face au but, et le chemin renvoyé peut être bien plus long que le plus court, car il ne compte jamais ce qu’il a déjà dépensé.
Chargement de la démo…
La grille avec le meilleur d’abord glouton sélectionné. Dessinez un mur juste devant le but et regardez-le s’acharner dessus.
- 01Choisir une heuristique h(case) : la distance en ligne droite, de Manhattan ou octile jusqu’au but.
- 02Mettre le départ dans une file de priorité ordonnée par h.
- 03Prendre la case de h le plus bas.
- 04Si c’est le but, remonter les parents mémorisés jusqu’au départ.
- 05Sinon, mettre en file chaque voisine non visitée selon son propre h et recommencer.
function greedy_best_first(start, goal, h):
parent = {start: none}
heap = [(h(start), start)]
while heap is not empty:
_, cell = heap.pop_min()
if cell == goal: return path_from(parent, goal)
for n in neighbours(cell):
if n not in parent:
parent[n] = cell
heap.push((h(n), n))
return no_pathLe pire cas est celui de Dijkstra ; en pratique il développe souvent bien moins de cases.
- Très peu de cases développées en terrain dégagé.
- Une ligne de différence avec Dijkstra.
- Pas optimal : le chemin peut être bien plus long que le plus court.
- Piégé par une impasse qui fait face au but.
- Ne vaut que ce que vaut l’heuristique.
- 01Recherche de cheminComparez le peu de cases qu’il développe à la longueur de son chemin, à côté d’A* et de Dijkstra.