問題タブ [depth-first-search]

私はこれを一週間ずっと試してきましたが、私の人生では、それを理解することはできません.

pathSoFar を再帰して返すヘルパー関数が必要であることはわかっています。再帰について頭が回らないようです。

私は非常に混乱しているので、再帰以外の問題を正確に定式化することさえできません。

助けてくれてありがとう。

編集：わかりました、少し明確にします。私を混乱させることの 1 つは、ノードに隣接ノードがない場合に返されるパスです。ゴール パスが最初に返される場合がありますが、ヘルパーがまだ再帰的であるため、行き止まりのパスが返される可能性があります。私はバックトラックについて混乱していると思います。

iterative deepeningについて読み続けていますが、 depth-first searchとの違いがわかりません。

深さ優先探索がますます深く進んでいることがわかりました。

反復的な深化では、レベルの値を確立します。そのレベルに解決策がない場合は、その値を増やして、ゼロ (ルート) からやり直します。

これは深さ優先探索と同じではないでしょうか?

つまり、解決策が見つかるまで、どんどん増やしていきます。私はこれを同じものと見ています！ゼロからやり直すと、以前と同じブランチにたどり着くので、同じブランチにたどり着きます。

スタックを使用してパスを返したいのですが、不可能だと思います。

ノードは、その背後にあるパスを受信できるように、親から直接呼び出される必要がありますが、このノードがスタックにプッシュされると、これまでのところパスが失われます。スタックを使用すると、ノードが個別に評価され、ノードの親へのパスをノードに渡すことができませんでした。

宿題なので、ノードにパスのプロパティを持たせることはできません。

私はこれに一週間以上困惑しています！

バークレーのウェブサイトのAIコースページにある課題に取り組んでいます。パックマンのパスを見つけることができるように、深さ優先探索を作成する必要があります。問題は、パックマンがスタックすることです。私が言っていることをより明確にするために、最初にコードを貼り付けます：

dfsの下で私のコードを読むと、開いているリストに私が訪れて展開したすべてのポイントが含まれていることがわかります。

パスファイルには、pacmanに設定された方向が含まれています。問題は、私が取得した両方の後継者が訪問されていないという条件に直面したときに発生します。私のpacmanは行き止まりにつながるパスをたどるので、バックトレースする必要があります。My Openはそれを実行して解決策を見つけますが、パスリストでバックトレースの方向を提供する方法を見つけることができません。http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.htmlにアクセスし、zipをダウンロードして、search.pydfs searchの下にコードを貼り付けると、私の問題が理解できます。

したがって、現在、次の擬似コードを含むDFSがあります

検索の深さを制限する 3 番目の引数を受け入れるようにこの関数を変更するにはどうすればよいですか?

このdfs/bfsの問題を解決しています。

DFS の反復バージョンと再帰バージョンの両方を作成しました。

ノードにアクセスする順序が異なり、その理由がわかりません。

反復 DFS:

再帰的 DFS:

チュートリアルの問題では、反復 DFS バージョンでの私の出力は次のとおりです。

1 4 3 2 6

(問題のサンプル出力と再帰バージョンによると):

1 3 2 6 4

ここで何が起こっているのですか？再帰を排除すると、訪問したノードの順序が変更されるのはなぜですか?

-> Netbeans プロジェクトの完全なコード。

私はDFSとBFSについて何度も読んだことがありますが、長い間、この疑問が頭に残っています。多くの記事で、DFSが無限ループに陥る可能性があると述べられています。

私の知る限り、この制限は、訪問したノードを追跡することで簡単に取り除くことができます。実際、私が読んだすべての本で、この小さなチェックはDFSの一部です。

では、なぜ「無限ループ」がDFSの欠点として言及されているのでしょうか。元のDFSアルゴリズムに、訪問したノードに対するこのチェックがなかったという理由だけですか？説明してください。

(リンクされたリスト) グラフの DFS を実装しています。

私のグラフ構造の例: http://i.imgur.com/Pm9jC.png

ご覧のとおり、「a」という名前のノードが多数あります。頂点に関しては同じですが、ノードに関しては実際には異なります。DFS の実装には、「a」をある時点で訪問済みとしてマークすることが含まれます。これは簡単に思えますが、ここで私の問題を確認していただければ幸いです。訪問済みとしてマークする「a」がたくさんあります。ここで何か間違ったことをしているといいのですが。

問題: - 最初に "a" を訪問済みとしてマークし、それをスタック s にプッシュします。これにより、最初の隣接リンク リスト内のノード "a" が訪問済みとして効果的にマークされますが、他の隣接リンク リスト内の他のすべてのノード "a" は依然として "未訪問" としてマークされます。- 次に、「a」に隣接する最初の未訪問の頂点である「b」を検討します。訪問済みとしてマークし、スタック s にプッシュします。- 今は「b」を探っています。2番目の隣接リンクリストから、「b」に隣接する頂点は「a」であり、これは未訪問であるため、再度スタックにプッシュします。違う！

もちろん、「a」のすべての出現を一度に訪問済みとしてマークする markVisit($vertex) メソッドを作成することはできますが、上記の実装では正しいアプローチを持っているとは思いません。ご協力いただきありがとうございます。

有向非巡回グラフGのソース頂点Vからすべての可能な頂点へのすべての可能なパスを見つける関数を実装したいと思います。

今はパフォーマンスは関係ありません。アルゴリズムを理解したいだけです。深さ優先探索アルゴリズムの定義を読みましたが、何をすべきか完全には理解していません。

方法がわからないため、ここで提供する完成したコードはありません。

• 結果を保存します（A-> B-> C->とともに、A->BおよびA->B-> Cも保存する必要があります）。
• グラフを表す（有向グラフ？タプルのリスト？）;
• 使用する再帰の数（隣接する各頂点で機能しますか？）。

Erlangの有向非巡回グラフで1つの特定のソース頂点を形成するすべての可能なパスを見つけるにはどうすればよいですか？

UPD：これまでの回答に基づいて、グラフの定義を再定義する必要があります。これは非循環グラフです。私の再帰関数がサイクルにヒットした場合、それは無期限のループであることを私は知っています。これを回避するために、現在の頂点が結果のパスのリストに含まれているかどうかを確認できます。含まれている場合は、トラバースを停止してパスを返します。

UPD2：考えさせられるコメントをありがとう！はい、1つのソース頂点から他のすべての頂点へのループがないすべての単純なパスを見つける必要があります。

このようなグラフでは：

ソース頂点Aを使用すると、アルゴリズムは次のパスを見つける必要があります。

• A、B
• A、B、C
• あいうえお
• 広告
• A、D、C
• A、D、C、B

次のコードは機能しますが、頂点が20を超えるグラフでは使用できません（再帰に問題があると思います。メモリが多すぎて、終了しません）。

UPD3：

問題は、通常の深さ優先探索アルゴリズムが最初にパスの1つ（（A、B、C、D）または（A、D、C、B））に移動し、2番目のパスには移動しないことです。

いずれの場合も、これが唯一のパスになります。たとえば、通常のDFSが（A、B、C、D）からバックトラックすると、Aに戻り、D（Aの2番目のネイバー）にアクセスしたかどうかを確認します。また、通常のDFSは各頂点のグローバル状態を維持するため、Dは「訪問済み」状態になります。

したがって、再帰に依存する状態を導入する必要があります。（A、B、C、D）からAまでバックトラックする場合、結果のリストに（A、B、C、D）が含まれている必要があり、アルゴリズムの最初の時点で、Dが未訪問としてマークされています。

末尾再帰のソリューションを最適化しようとしましたが、それでもアルゴリズムの実行時間は実行不可能です。頂点ごとに3つのエッジを持つ16の頂点の小さなグラフをトラバースするのに約4秒かかります。

これを許容可能な時間で実行するためのアイデアはありますか？

ベクトルのリストを返す dfs メソッドがあります。ベクトルの長さに応じて要素を並べ替えるにはどうすればよいですか。