Parcours en largeur
Quel est le plus court chemin quand tous les pas ont le même coût ?
Explore la grille en anneaux autour du départ, le plus proche d’abord. Il trouve le chemin qui a le moins de pas.
Le parcours en largeur garde une file de cases à explorer. Il prend la plus ancienne, ajoute ses voisines non visitées à la fin et recommence. Comme la file est premier arrivé, premier sorti, toutes les cases à distance un sont traitées avant celles à distance deux, et ainsi de suite vers l’extérieur.
La première fois qu’il atteint le but, aucun chemin plus court n’existe. Cette garantie ne vaut que si tous les pas ont le même coût : avec des coûts différents, il peut renvoyer le chemin au moins de pas mais au total plus élevé.
Il ne sait pas où est le but, donc il s’étale dans toutes les directions et examine beaucoup de cases.
Chargement de la démo…
La grille avec le parcours en largeur sélectionné. Dessinez des murs et regardez la recherche s’étendre en anneau.
- 01Mettre le départ dans une file et le marquer visité.
- 02Prendre la case en tête de file.
- 03Si c’est le but, remonter les parents mémorisés jusqu’au départ.
- 04Sinon, ajouter chaque voisine non visitée en fin de file, en notant d’où elle vient.
- 05Répéter jusqu’à ce que la file soit vide : il n’y a alors aucun chemin.
function bfs(start, goal):
queue = [start]
parent = {start: none}
while queue is not empty:
cell = queue.pop_front()
if cell == goal: return path_from(parent, goal)
for n in neighbours(cell):
if n not in parent:
parent[n] = cell
queue.push_back(n)
return no_pathV est le nombre de cases et E les liaisons entre elles ; sur une grille, les deux sont proportionnels au nombre de cases.
- Le moins de pas, garanti.
- Complet : il trouve un chemin dès qu’il en existe un.
- Une dizaine de lignes.
- Ignore les coûts : le moins de pas n’est pas toujours le moins cher.
- Ignore où est le but, donc il remplit un disque entier autour du départ.
- La frontière peut devenir grande.
- 01Recherche de cheminL’une des cinq recherches que vous pouvez lancer sur des murs que vous dessinez ; ici la frontière est une simple file.