問題タブ [depth-first-search]

再帰的な深さ優先の方法で最近傍を見つけようとしています。この点に到達する前に多くの要素が関係していますが、簡単にするために、現在問題が発生しているセクションのみを含めました。

私の考えは、あるしきい値距離に基づいて特定のポイントに最も近いものを見つけることです。プロセスを 2 つの方法に分けることにしました。最近隣が存在するかどうかを実際に確認する方法と、その関数を再帰的に何度も呼び出す方法です。

ポイントとして扱う double 値を持つ ArrayList があります... 0.0 を返す場合は、最も近い隣人を見つけられなかったことを意味します (実際にオブジェクトを使用しているかどうか疑問に思っている場合は、ロジックをクリーンアップすると実行される可能性があります)。

そして、これが私の方法で、上記を再帰的な dfs の方法で呼び出すことを計画していました。

私が苦労しているのは、再帰的な深さ優先検索です。それに加えて、ビジターの実装が正しくないようです。

これが私が訪問者を処理しようとした方法です

次に VisitedPoint オブジェクトを作成しますprivate VisitedPoint[] isVisited;が、それを isBelongTo() メソッドで使用すると、null ポインター例外が発生します。

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

アイデアと代替ソリューションで返信してくれた皆さんに感謝します。問題を解決するためのより効率的な方法はいつでも歓迎されます。とはいえ、私がアルゴリズムで解決しようとしている問題をしばらく無視して、私が書いたアルゴリズムの非常に複雑な部分を分析するのを手伝ってもらいたいのですが、すべて単純なパスです.ここで説明されている深さ制限検索を使用したグラフで、ここで実装されています。ありがとう！

編集：これは宿題ですが、私はすでにこの課題を提出しており、私の答えが正しいかどうか知りたいだけです. 再帰が関係している場合、Big-O の複雑さに少し混乱します。

以下の元の質問：

このアルゴリズムによって与えられる全パス検索の複雑さを見つけようとしています。2 つの頂点が与えられた場合、深さ優先検索を使用してそれらの間のすべての単純なパスを見つけています。

DFS の時間計算量は O(V+E) であり、その空間計算量は O(V) であることを知っています。私の直感では、全パス検索の複雑さはそれ以上になると思いますが、それが何であるかを決定します。

関連する SO の質問はこちらとこちらです。

更新（以下のコメントに応じて）：

私は6 次のケビン ベーコン問題を解こうとしています。これには通常、アクターのペア間の最小の分離度を見つける必要がありますが、すべての分離度を見つける必要があります (現時点では 6 未満ですが、これは変更される可能性があります)。

上記のコードは、隣接行列として保存されたグラフにdfsを実装します。生成されたグラフが接続されているかどうかを知るために、どのような変更を行う必要があるかを提案します。

私は別の同様の質問に戻ってきました。私は現在、グラフが 2-colorable かどうか、つまりグラフに奇数サイクル (奇数の長さのサイクル) が含まれていないかどうかをチェックする Java プログラムに取り組んでいます。アルゴリズム全体は、O(V+E) 時間で実行されることになっています (V はグラフ内のすべての頂点であり、E はすべてのエッジです)。私の現在のアルゴリズムは、Depth First Search を実行し、パス内のすべての頂点を記録してから、バック エッジを探し、エッジがどの頂点の間にあるかを記録します。次に、バック エッジの一方の端からエッジのもう一方の端にあるもう一方の頂点に到達するまでパスをトレースし、バック エッジが完了するサイクルをたどります。

この種のトラバースは、グラフに存在するすべてのサイクルに対して O(V+E) 時間で実行できるという印象を受けましたが、アルゴリズムが非常に大規模なために途方もなく長い時間実行されているため、何かが欠けているに違いありませんグラフ (10k ノード、エッジの数がわからない)。

私のアルゴリズムは完全に間違っていますか? もしそうなら、誰かが私を正しい方向に向けて、これらのサイクルを記録するためのより良い方法、または頂点の数が奇数であるかどうかを知ることができますか? 皆さんが与えることができるすべての助けに感謝します。必要な場合は、コードを以下に示します。

追加: 申し訳ありませんが、グラフが 2-colorable でない場合は、そうでないことを証明する奇妙なサイクルを提供する必要があります。

頂点クラス

次の方法で、重み付き有向グラフに DFS を実装しています。

ソース ノードと宛先ノード間のすべてのパスの検索中にサイクルを許可するように上記を変更する必要があります。無限サイクルを回避するために、行われた「停止」の数、またはソースからの最大許容移動距離に基づいて検索を終了する条件を設定できます。

このようにして、たとえば、A で始まり D で終わり、ちょうど 5 つの停留所があるトリップの数を見つけることができます。1 つの解は ABCDCD です。または、たとえば、D から D までの距離が 40 未満のさまざまなルートの数を見つけることができます。いくつかの解は、DECD、DEBCD、DCDCD です。

私の問題は、宛先ノードに到達しないことが保証されている無限の検索サイクルを回避しながら、メインアルゴリズムの検索を維持するロジックを作成する方法がわからないことです。

A から D に移動したいとしましょう。考えられる行き止まりのサイクルは ABCEBCEBCEB....(無限大まで) です。停留所の数、または移動距離の合計に基づく私の条件は、このループを終了させることができますが、検索全体を終了させることもできます。それ以外の場合は、たとえば ABCDCDCDCD の正しいパスを見つけることができ、いずれかの事前設定された条件が満たされたときに正しく終了します。

アイデアをありがとう。

深さ優先探索を使用して、有向加重グラフのパスを特定し、サイクルに属するノードを再検討し、移動した合計距離またはソースノードからの停止に基づいてカットオフ条件を設定しています。

私が理解しているように、再帰では、深さ優先探索に明示的なスタック構造は必要ありません。したがって、明示的なスタックを使用せずに、以下のコードをさらに単純化できるかどうか疑問に思いました。

ただし、明示的なスタック構造を持たない他の再帰的な実装では、通常、すでにアクセスしたノードを白、灰色、または黒に色付けして考慮します。それで、再訪が許可され、パスを記録する必要がある私の場合、明示的なスタックは絶対に必要ですか？より簡単な代替案の提案をありがとう。

Python で深さ優先検索を実行しようとしていますが、うまくいきません。

基本的に、ペグ ソリティア ボードがあります。

1 はペグを表し、0 はオープン スポットです。ペグを一度に 2 つのスロットを後方または前方に 1 つずつ空の場所に移動する必要があります。その過程で別のペグを飛び越えると、それは空のスロットになります。ペグが 1 つ残るまでこれを行います。基本的に、ゲームは次のようになります。

ここに私が持っているものがあります:

だから、今私の質問：

1. これは、これに対して深さ優先検索を行う正しい方法ですか?
2. アルゴリズムが機能しません!!! 行き詰まります。ここで質問するまで何日も苦労してきたので、助けてください。
3. 私は DRY に従っていないようですが、何か提案はありますか?
4. ああ、助けて？

Java で FlowChart ダイアグラム エディタを作成しました。それは、フローチャートを描画し、それらを相互に接続して、2 つの配列を作成します。1 つはノードとラインの接続を示し、もう 1 つは要素同士の接続を示します。Begin Two And の開始からすべての方法を見つけなければなりません。たとえば、決定のためのダイヤモンドがある場合、2 つの別々の方法があります..このすべての方法を取得したい..どのアルゴリズムを使用する必要がありますか?

編集3： 解決済みこんにちは、私は自分の問題を自分で解決しました..ここに私のコード..））

編集1：私が自分の問題に取り組んでいたので、一部を解決しましたが、間違いもありません...ここで私の問題の詳細な説明：要素間の接続を説明する配列があります

これは私の接続配列です..AからEまでのすべての方法を見つけようとしています

2通りあります

A->B->C->E

A->B->D->E

左から右に配列を検索する最初の方法を見つけることができます。1 が表示されたら、J の walu e を取り、i の J 番目の要素行に移動し、その要素を 2 にして [i,j+1] から検索を開始し、E に到達した場合は結果を送信します。

しかし、ここで私の問題は、最初の行の ecnd 検索で 1 が表示されず、2 行目に移動し、最初の要素 1 がありますが、最初の行を参照し、ループになります。

また、バックトラックを使用して DFS を使用しようとしましたが、すべてのパスを表示するのではなく、1 つのパスのみを表示します。

そして、1を見つけて[i、j]の検索を開始すると、列の下のすべてを0にしようとしましたが、2回目の検索では何も表示されず、私のarryテーブルは空白のテーブルになります))。

私は何かが欠けていることを知っていますが、それを理解することはできません..

編集2：

今、私は解決策を閉じましたが、再び問題があります。このコードを使用して、マトリックスからパスを計算しました

}

出力は終了です

創業 創業 創業

[ 0 0, 0 1, 1 2, 2 4, 1 3, 3 4]

2は、訪問して変更したことを意味します..問題は、訪問リストに追加することです

00 、 01 、 12 、 24 これは最初のパスですが、その後は 13,34 のみです。これは、配列の残りを 0 に変更して検索しないためです。どうすればこれを解決できますか? 00,01,12,24 および 00,01 または 10,13,34 でなければなりません。そして、これがDFSまたはBFSであるとは思いませんか？または、他の何か？？

グラフの実装に必要な一般的な関数のほとんどを実装した後、いくつかの関数 (頂点の削除、頂点の検索、頂点の取得) には「最適な」実装がないことに気付きました。

グラフの実装にリンクされたリストを含む隣接リストを使用しています。必要な頂点が見つかるまで、次々と頂点を検索していました。私が言ったように、私は「最良の」実装を使用していないことに気付きました。10000 個の頂点を持つことができ、最後の頂点を検索する必要がありますが、その頂点には最初の頂点へのリンクが含まれている可能性があり、これにより作業が大幅に高速化されます。しかし、これはあくまでも仮説であり、実際に起こるかもしれないし、起こらないかもしれません。

では、検索ルックアップにはどのアルゴリズムをお勧めしますか? 私たちの教師は、主に幅優先と深さ優先について話しました (そして、Dikjstra のアルゴリズムですが、それはまったく別の主題です)。その2つのうち、どちらがおすすめですか?

両方を実装できれば完璧ですが、そのための時間がありません。第 1 フェーズの締め切りが近づいているので、どちらかを選択して実装する必要があります...

私の推測では、Depth-first を使用することであり、実装が容易であり、それらの動作方法を見ると、それが最善の策のようです。しかし、それは本当に入力に依存します。

しかし、あなたたちは何を提案しますか？

When does pruning stop being efficient in a depth-first search? I've been working on an efficient method to solve the N-Queens problem and I'm looking at pruning for the first time. I've implemented it for the first two rows, but when does it stop being efficient? How far should I prune to?