Javascript で幅優先検索 (他のアルゴリズムも、現在は bfs) の実装を作成しようとしています。
最終的には、すべての検索アルゴリズムをグリッドに適用して、開始ノードから目標ノードまでのパスを見つけたいと考えています (bfs はこれが特に得意ではありません)。私は実装を行いましたが、問題は事前にツリー全体を持っていないことです。私が望むのは、それに startnode と endnode を与え、それに基づいてそれらの間のパスを見つけることです。
私が直面している問題は、隣接するグリッド スクエアを決定すると、すべての近隣が返されるため、既にトラバースされているものも返されることです。これにより、ツリー検索ではなくグラフ検索になります。これを解決する方法は、すべてのパスを覚えておくことです。これにより、どの近隣が既に横断されているかを確認できるため、これ以上調べる必要がなくなります。ただし、検索アルゴリズムのコースで学んだように、bfs には現在の深さレベルですべてのノードのメモリ使用量があります。すべてのパスを保存すると、それよりもはるかに多くのメモリが消費されますか?
事前にツリー構造を持っておらず、サイクルを避ける場合、bfs が検索している現在の深さのノードのみをメモリに保持することは可能ですか?
私は自分自身を明確にしたことを願っています。
前もってありがとう、ステファン