問題タブ [breadth-first-search]

DFSまたはBFSにスタックを使用するか、キューを使用するかを常に混同しています。どのアルゴリズムがどのデータ構造を使用しているかを覚える方法について、誰かが直感を教えてくれませんか？

ねえ、私は地元のプログラミングコンテストに参加していて、彼らは私にこの質問をしましたが、私にはできませんでした。この質問について私を助けてください。

ファイルから迷路のサイズをロードし、次に迷路自体をロードするプログラムを作成します。迷路をモデル化するために、開始セル「。」を指定する文字「S」を使用します。これは空きセルを指定し、「＃」は壁、「F」は最後のセルです。開始セルから最終セルへのパスを見つけるプログラムを作成します。迷路の中にはコマンドに従うロボットがあると考えることができるので、次の迷路では、ロボットは次のコマンドを受け取る必要があります：上、上、右、右、下、下。

迷路1テキストファイル

迷路2テキストファイル

一般的にプログラムを作成します（迷路の最大入力は最大200x200です）。

助けていただければ幸いです。私は新進気鋭の2年生なので、コードを提供していただければ、私はそれを理解でき、彼らは自分でそれをやり直します。

私の質問は、どちらの検索タイプのメカニズムについても実際にはありません。それよりもずっと平凡だと思います。どちらの入力と出力もわかりません。より具体的には、CLRSでは、BFSは入力としてグラフとソースノードを取りますが、DFSはグラフのみを取ります。それ以降、DFSはどこを検索してもかまいませんか？

これが入力の混乱です。出力の混乱は、DFSでは、完了すると、各ノードの検出と終了時間を記録するテーブルのような構造になっているということです。そこからソリューション、つまりソースノードから宛先ノードへのパスをどのように抽出しますか？

私は理にかなっていると思います。ありがとう！

編集：これが、DFSがソースノードを取得しないという意味です。これはCLRSからのDFS擬似コードです。私はそれがどこにもソースノードを取っているのを見ません。私が見ているのは、グラフ内のすべてのノードを通過することだけです。

問題は次のとおりです。放浪者はグリッド座標 (x,y) から開始し、座標 (0,0) に到達したいと考えています。すべてのグリッドポイントから、放浪者は北に 8 歩、南に 3 歩、東に 5 歩、西に 6 歩 (8N/3S/5E/6W) 移動できます。

幅優先探索を使用して (X,Y) から (0,0) への最短ルートを見つけるにはどうすればよいですか?

説明:

• 無制限のグリッド
• 負の座標を使用できます
• キュー (リンクされたリストまたは配列) を使用する必要があります
• 障害物はありません

私が行ったほとんどの読書によると、双方向検索アルゴリズムは、「前方」と「後方」のフロンティアが最初に交差したときに終了すると言われています。ただし、 Artificial Intelligence: A Modern Approachのセクション 3.4.6 で、Russel と Norvig は次のように述べています。

双方向検索は、ゴール テストをチェックに置き換えて、2 つの検索のフロンティアが交差するかどうかを確認することで実装されます。もしそうなら、解決策が見つかりました。2 つの検索が両方とも幅優先であっても、最初に見つかった解が最適ではない可能性があることを理解することが重要です。ギャップを横切る近道がないことを確認するために、追加の検索が必要です。

このステートメントについてかなり長い間検討してきましたが、この動作の例を見つけることができません。双方向 BFS または A* 検索の前方フロンティアと後方フロンティアの間の最初の交点が最短経路ではないグラフの例を誰か提供できますか?

編集:明らかに、BFS は加重グラフで最短パスを見つけられません。この抜粋は、無向グラフの双方向 BFS を参照しているようです。または、加重グラフで双方向 A* を使用した反例を見てみたいと思います。

質問:ツリー ノードをレベルごとに表示するにはどうすればよいですか? 時間とスペースの効率的な解決策を教えてください。

例 ：

出力: レベルごとにツリー ノードを出力する必要があります

したがって、リストをトラバースすることはできますが、各レベルを印刷することはできません。方法がわからない。

私はこのようなものを持っています：

次のように印刷する代わりに

idはそれをそのように印刷するのが好きです

私はいくつかの異なることを試みましたが、私はそれを得ることができないようです。どんな助けでもありがたいです。

次のコードでは、 を介してグラフをトラバースしていますbreadth first search。コードは、トラバース中にグラフを構築します。これは非常に大きなグラフで、ファン アウトは 12 です。このため、深さがbreadth first search増すたびに、メモリ使用量を最小限に抑えるために、その上のレイヤーを破棄したいと考えています。そのためのアルゴリズムをどのように設計できますか?

私はどこかで、BFSが解決策を見つけるために、DFSが保証されていないことを読みました。なぜですか？私はこれがどのように真実であるかを本当に理解していません..誰かがこれを証明する私のためのケースを示すことができますか？

幅優先検索、dfs、A* などの使用方法に関する多くのスタック オーバーフローの質問を読んできました。問題は、最適な使用法と、実際のシミュレートされたグラフでそれを実装する方法です。例えば

Twitter/Facebook/ソーシャル ネットワーキング サイトのソーシャル グラフがあるとします。検索アルゴリズムは次のように機能するように思われます。

ユーザー A に 10 人の友達がいた場合、そのうちの 1 人には 2 人の友達がいて、もう 1 人には 3 人の友達がいました。検索では、最初にユーザー A の友達が誰であるかを特定し、次に 10 人のユーザーそれぞれの友達が誰であるかを調べる必要があります。私にはこれはbfsのように見えますか？

ただし、それがアルゴリズムの実装方法であるかどうかはわかりません。

ありがとう、