Parcours en profondeur
Existe-t-il un chemin, quel qu’il soit ?
Suit un chemin aussi loin que possible avant de reculer. Il trouve un chemin vite, mais pas forcément court.
Le parcours en profondeur est le parcours en largeur dont la file est remplacée par une pile : il repart toujours de la case la plus récente. Il descend un couloir jusqu’à rencontrer un mur ou une case visitée, puis recule jusqu’au dernier carrefour et essaie la branche suivante.
C’est économe et efficace pour savoir si le but est atteignable, et c’est la base de nombreux autres algorithmes : générer des labyrinthes, ordonner des tâches, trouver des régions connexes. Comme chercheur de chemin, sa faiblesse est que le premier chemin trouvé peut errer sur toute la carte.
Chargement de la démo…
La grille avec le parcours en profondeur sélectionné. En terrain dégagé, le chemin renvoyé serpente, rarement proche du plus court.
- 01Empiler le départ et le marquer visité.
- 02Dépiler la case la plus récente.
- 03Si c’est le but, remonter les parents mémorisés jusqu’au départ.
- 04Sinon, empiler chaque voisine non visitée, en notant d’où elle vient.
- 05Répéter jusqu’à ce que la pile soit vide.
function dfs(start, goal):
stack = [start]
parent = {start: none}
while stack is not empty:
cell = stack.pop() # the newest cell
if cell == goal: return path_from(parent, goal)
for n in neighbours(cell):
if n not in parent:
parent[n] = cell
stack.push(n)
return no_pathComme le parcours en largeur au pire. Sur un arbre, ou en récursif, la mémoire n’est que la profondeur du chemin courant.
- Quelques lignes, et peu de mémoire sur les arbres.
- Répond vite à « le but est-il atteignable ? ».
- Brique de nombreux autres algorithmes.
- Le chemin trouvé peut être très loin du plus court.
- Le résultat dépend de l’ordre de visite des voisines.
- Ignore les coûts et la position du but.
- 01Recherche de cheminLancez-le sur une grille vide et comparez la longueur de son chemin à celle des quatre autres avec « Tout comparer ».