幅優先検索実装

Question

JavascriptでBreadth First Search（他のアルゴリズムでも現在はbfs）の実装を試みています。

最終的に、すべての検索アルゴリズムをグリッドに適用して、最初からゴールノードまでのパスを見つけたいと思います。私は実装をしましたが、問題は私が事前にツリー全体を持っていないということです。私が望むのは、startnodeとendnodeを与え、それに基づいてそれらの間のパスを見つけることです。

私が遭遇している問題は、隣接するグリッドスクエアを決定すると、すべてのネイバーが返されるため、既にトラバースされているネイバーも戻ってしまうことです。これは、ツリー検索ではなくグラフ検索に変わります。それを解決する方法は、すべてのパスを覚えておいて、どの隣接ノードが既に横断されているかを調べることができるため、さらに検討する必要はありません。しかし、検索アルゴリズムのコースで学んだように、bfsは現在の深さレベルですべてのノードのメモリ使用量を持っています。私がすべてのパスを保存すると、それはそのメモリよりもはるかに多くのメモリを消費しますか？

ツリー構造を事前に持っていなくても、サイクルが発生しないようにしておくと、bfsが検索している現在の深さのノードだけをメモリに保持できますか？

私は自分自身を明確にしたいと思います。事前に

おかげで、 ステファン

Answer 1

あなたが遭遇したDFS同じトラブルに入るかもしれない、あなたが訪問したノードを「忘れる」になる場合 - それは（最適な（最適な経路を見つけるしない場合があります）も完全ではありません無限ループのために、存在していても解決策が見つからない可能性があります）。

なお：

• あなたが唯一の最も深いレベルのノードを覚えていたとしても - それはまだずっとあなたを助けにはならない - バイナリツリーで、例えば、ノードの半分は葉があることを覚えているので、スペースの複雑さは依然として巨大になります。
• ノードの一部だけを記憶していても、最適性は保証されません。なぜなら、最終的にあなたが忘れてしまった頂点を再発見するからです。

完全で最適なメモリ効率の良いアルゴリズムをお探しの場合は、Iterative Deepening DFSがあなたの後になっている可能性があります。