問題タブ [depth-first-search]

有向グラフですべてのサイクルを見つけたい。深さ優先探索を開始すると、1つのノードからいくつかのサイクルが検出されます（バックエッジの検出）。したがって、グラフ内のすべてのノードにdfsを適用しました（つまり、ルートが異なるノードになるたびに）。これを使用して（重複するものを排除することにより）すべてのサイクルを取得できます。しかし、これがすべてのグラフで機能するかどうか、そしてこれが正しいアプローチであるかどうかはわかりません。これがすべての状況で機能するかどうかを誰かが私に提案できますか？

ありがとう

私は最近（4日）C/JavaのバックグラウンドからC++を学び始めました。新しい言語を学ぶために、私は通常、可能な限り言語固有のさまざまな古典的アルゴリズムを再実装することから始めます。

私はこのコード、そのDFSに到達しました-方向性のないグラフでの深さ優先探索。それでも私が読んだことから、C++の参照によってパラメーターを渡すのが最善です。残念ながら、参照の概念を完全に理解することはできません。参照が必要になるたびに、私は混乱し、ポインターの観点から考えます。現在のコードでは、値渡しを使用しています。

コードは次のとおりです（おそらくCppthonicではないはずです）：

このコードを参照して、参照の使用方法に関するヒントを教えてください。

私の現在のプログラミングスタイルは、C ++の構成と互換性がありますか？

C ++の2次元配列のベクトルとタイプ**の標準的な代替手段はありますか？

後で編集：

OK、私はあなたの答えを分析しました（すべてに感謝します）、そして私はよりOOPの方法でコードを書き直しました。また、私は参照が何であるかを理解し、それを使用することになっていました。これは、constポインターにいくぶん似ていますが、そのタイプのポインターがNULLを保持できるという事実が異なります。

これは私の最新のコードです：

DFS と BFS の違いは理解していますが、どちらを使用するのがより実用的か知りたいですか?

DFSがBFSを打ち負かし、その逆の例を誰か挙げてもらえますか?

次のグラフについて考えてみます。

ソースノードからターゲットノードへのすべての可能なパスを列挙する方法を見つけようとしています。たとえば、AからEまで、次のパスが考えられます。

ACDEの場合、パスの1つはエッジF3を使用し、もう1つはエッジF5を使用するため、実際には2つのパスがあることに注意してください。また、AとCの間にサイクルがあるため、パスの数が無限になる可能性がありますが、この目的のために、ソースからターゲットへのパスでノードが繰り返されないパスにのみ関心があります。

深さ優先探索（DFS）アルゴリズムを作成しましたが、問題は、2つのノード間に複数のエッジがある場合（上記のエッジF3とF5など）、それを処理する方法がわからないことです。A C D E私のアルゴリズムはパスを戻すだけA C Eで、他のパスは返しません。の場合A B C E、理由は理解できます。Aから開始してCに移動し、それらのパスを構築しますが、DFSがノードBに戻ると、Cに移動しようとしますが、Cはすでにアクセスされているためです。止まります。

とにかく、これを行う方法があるのか​​、それともこれがNP完全であるのか疑問に思いました。

私のDFSをご覧になりたい場合は、以下のコードをご覧ください（マクロの乱用については申し訳ありませんが、コンテストプログラミングで使用しているので、少し習慣になっています）。

出力：

複数の川を渡る問題 (Fox Goat Cabbage、Jealous Husbands、Mercenaries and Cannibals など) を解決する DFS を作成しようとしています。パズル クラスを作成しましたが、ソルバーの構造化に問題があります。DFS がどのように機能するかは理解していますが、この設計に適応させるためにどこから始めればよいかわかりません。

各パズルには move() メソッドがあり、有効な手であれば true を返し、ルールセットに違反している場合は false を返します。乗客は、川のそれぞれの側を表す一対のリストで追跡されます。ソルバーはこれらのリストにアクセスできますが、乗客が川を渡るたびに可能な動きが変わるため、これを使用して可能な動きセットを生成する方法がわかりません。

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

私は、列ごとに1つのクイーンしか存在できないという条件でN-クイーンの問題を解決しました。だから私は最初の列の正方形に女王を置き、次に次の列に移動して、船上の女王に攻撃されていない正方形に女王を置きます。このアプローチですべての解決策を見つけることができますが、n=13から長い時間がかかり始めます。また、問題の解決策のほとんどは、ごく少数の異なる解決策の回転と反射によって見つけることができることがわかりました。たとえば、8クイーン問題には合計92の解決策があり、そのうち12のみが明確です。（http://en.wikipedia.org/wiki/Eight_queens_puzzle）

だから私の質問は、ボードのこれらの状態をチェックし、明確な解決策を与えるスタックにそれらの状態のみをプッシュするにはどうすればよいですか？

これが私が今していることです。

ノードを再訪せずに、2 つのノード間の最長パスを見つける Lisp 関数をプログラムする必要があります。ただし、開始ノードと終了ノードが同じ場合は、このノードに再度アクセスできます。この関数は、再帰的かつ深さ優先検索の両方である必要があります。

私は何時間もこれに取り組もうとしてきましたが、解決策が思いつきません。関数の大まかな概要は知っていますが、正しくプログラミングできません。一部のコードとほとんどが擬似コード:

ネットは '((ab) (bc)) のように見えます。ここで、最初の項目はノードで、それ以外はすべてその隣接ノードです (たとえば、ノード a には隣接 b があり、ノード b には隣接 c があります)。

はい、これは宿題ですので、解決策やその一部を投稿することに自信がない場合は、投稿しないでください。私は Lisp を初めて使用するので、適切なスタートを切るためのヒント/ヘルプが必要です。

ありがとう

編集：まあ、私が得ることができたのはこれだけでした：

開始ノードと終了ノードが同じ場合を除いて、正しいソリューションが生成されます。同じなのに検索の仕方がわかりません。

グラフの連結要素をカウントするスクリプトを作成しようとしましたが、正しい解が得られません。6 つのノード (頂点) を持つ単純なグラフがあり、ノード 1 と 2 が接続され、ノード 3 と 4 が接続されています (6 つの頂点; 1-2,3-4,5,6)。したがって、グラフには 4 つの連結要素が含まれます。次のスクリプトを使用して連結成分を数えますが、間違った結果が得られます (2)。

誰でも間違いを見つけるのを手伝ってもらえますか?

こんにちは、皆さん、DFS アルゴリズムを手伝ってくれる人はいますか : Path* agent_DFS (void* arg1,...); これはCプログラムで書かれており、車が彼の目標に到達する方法を見つけなければならない人工知能に関するものです..?? タイプパスの配列を返します。それについてはまったくわかりません...助けてください