Mise en œuvre de la recherche étendue

Question

J'essaie de faire une implémentation de la recherche de la largeur d'abord (aussi d'autres algorithmes, mais actuellement bfs) en Javascript. Finalement, je veux appliquer tous les algorithmes de recherche sur une grille, pour trouver un chemin depuis le début vers le nœud de but (je sais que bfs n'est pas particulièrement bon dans ce domaine). J'ai fait une implémentation, mais le problème est que je n'ai pas tout l'arbre à l'avance. Ce que je veux, c'est lui donner un startnode et un endnode et, sur cette base, trouver un chemin entre eux.

Le problème que je rencontre est que lorsque je détermine les carrés-carrés adjacents, il renvoie TOUS les voisins, donc même ceux qui sont déjà traversés. Ce qui le transforme en recherche graphique plutôt qu'en recherche arborescente. Une façon de le résoudre est de se souvenir de tous les chemins afin que je puisse vérifier quels voisins ont déjà été traversés et ne devrait donc pas avoir besoin d'être examiné plus avant. Cependant, comme j'ai appris dans un cours sur les algorithmes de recherche, bfs a une utilisation de la mémoire de tous les nœuds sur le niveau de profondeur actuel. Si je stocke tous les chemins, alors il consomme beaucoup plus de mémoire que ce droit?

Est-il possible de ne conserver en mémoire que les nœuds de la profondeur actuelle sur laquelle bfs recherche, alors que je n'ai pas la structure arborescente à l'avance et que j'évite toujours d'avoir des cycles?

J'espère que je me suis fait comprendre.

Merci à l'avance, Stefan

Answer 1

Si vous « oublier » les noeuds que vous visitez, vous pouvez entrer dans les mêmes problèmes DFS rencontre - il n'est pas optimale (pourrait ne pas trouver le chemin optimal), ni complète (en raison des boucles infinies, il pourrait ne pas trouver une solution même si une existe).

Notez que:

• Même si vous vous rappelez seulement les plus profonds nœuds de niveau - il ne fonctionne toujours pas vous aider beaucoup - rappelez-vous que dans un arbre binaire, par exemple, la moitié des noeuds sont des feuilles, de sorte la complexité de l'espace sera encore énorme. Se souvenir seulement d'une partie des nœuds ne garantit pas l'optimalité, car vous finirez par retrouver un sommet que vous avez oublié - et vous vous êtes mis en boucle.

Si vous êtes à la recherche d'un algorithme plus efficace pour la mémoire qui soit à la fois complet et optimal - un Iterative Deepening DFS pourrait être ce que vous recherchez.