問題タブ [depth-first-search]

ブースト ライブラリに実装されている深さ優先アルゴリズムは、各頂点を 1 回だけ訪れます。

このオプションを無効にする回避策はありますか。頂点に分岐があるときはいつでも頂点にアクセスできるようにしたい。

なにか提案を...

編集:グラフは非循環的です。

私は、時には20〜30レベルの深さの大きなオブジェクトグラフを歩く必要があるコンポーネントを書いています。

グラフを歩く最もパフォーマンスの高い方法は何ですか？

A.深い再帰を回避するために「ステップ」をキューに入れる

また

B. DFS（深さ優先探索）。多くのレベルを深くステップし、「深い」スタックトレースを持つ場合があります。

私が尋ねている質問は、「深い」スタックトレースを引き起こすDFSを実行することで.NETにパフォーマンスの低下がありますか？もしそうなら、ヒットは何ですか？また、DFSで再帰的に処理されるステップをキューに入れることで、BFSを使用したほうがよいでしょうか。

不明な点がある場合は申し訳ありません。ありがとう。

タイトルが示すように、私はboost::depth_first_searchVisitor (から継承boost::default_dfs_visitor) を使用していくつかのアルゴリズムを実装しています。

ただし、アルゴリズムの実行中に、後で照会できるように、いくつかの情報をビジターに保存したいと考えています。ただし、DFSが完了すると情報が消去されるため、コピーを使用していると思います。すべてのプライベート変数にポインターを使用する以外に、これを防ぎ、ブーストに私のコピーを使用させる方法はありますか?

DAGの保存にBGLを使用しています。頂点には状態があります。頂点の1つで状態が変化した場合、依存する頂点を更新したいと思います。これは、boost::depth_first_searchとカスタムビジターを使用して実行できます。

ここでの論理は、検索された頂点と、頂点が特定の状態にある場合にその依存する頂点を更新したくないということです。基本的に、dfsまたはbfsのいずれかで頂点のエンキューを制御したいと思います。BGLでこれを達成するための最良の方法は何ですか。

ありがとう。

私は現在、フィットネス関数を使用して 15 のパズルを解くプロジェクトに取り組んでいます。使えるフィットネス機能は3種類あり、

1. 適合度関数 1 = 1 - (置き忘れたタイルの数/タイルの総数);
2. フィットネス関数 2 = 1- (ゴール位置からのすべての間違ったタイルの距離の合計/64)
3. フィットネス関数 3= (フィットネス 2+ フィットネス 1 )/2

ソルバーは、パズル ボード全体が解決されるまで (フィットネス関数 = 1)、フィットネス関数 VALUE を改善する可能な動きを検索することを目的としています。ソルバーが失敗した検索ルートを実際のルートと一緒に出力するため、動きを生成しようとしているときにストックされます。たとえば、W、S、W、N、S、N、S、N、S、N、S、N、S、N、S ,N,S,N (逆順) で、NWSW を意味します。ただし、ソルバーは何度か前後に検索し、不要なルートも出力します。再帰で以前に訪れた場所を除外し、失敗した動きではなく有効な動きのみを出力したいと思います。コードは以下で入手できます。

ノードのリストがあり、各ノードは1つまたは複数のツリーに属しています。（必ずしも共通の祖先を共有しているわけではありません）

深さ優先探索を実行するときに見つけるのと同じ順序でノードを並べ替えたいと思います。

ツリーのルートを一緒にソートするための述語と、共通の親の子を一緒にソートするための別の述語があるとします。各ノードには、親アクセサーと子列挙子があります。パフォーマンス上の理由から（可能であれば）、Children列挙を使用しないようにします。

述語がソート関数に渡すための擬似コードは何でしょうか（ノード1がノード2より小さい場合、述語はブール値を返します）。

ウィキペディアの深さ制限検索のアルゴリズムを理解しようとしており、ノードを展開することの正確な意味を理解しようとしています。答えを検索しようとしましたが、得られたのは、ノードを展開する必要があると述べているアルゴリズムだけでした。

具体的には、stack := expand (node)関数全体に関して何を言っているのでしょうか?

For my own exercises I'm writing an XML-parser. To fill the tree I use a normal std::stack and push the current node on top after making it a child of the last top-node (should be depth-first?). So I now do the same for deletion of the nodes, and I want to know if there's a faster way.
Current code for deletion:

Works totally fine but it kinda looks slow. So is there any faster / better / more common way to do this?

グラフが接続されているかどうかを判断するアルゴリズムを作成しようとしています。StackOverFlowErrorが発生し続けますが、コードはほぼ正しいと思います。個人的には、アルゴリズムをテストしているグラフにサイクルがあるため、コードはそれを理解せず、ループに陥っていると思います。しかし、私は配列を使用して、ノードがすでにアクセスされているかどうかを確認しています！だからそれは起こらないはずです！とにかくこれは私のコードです：

sは私が始めたノードであり、ノードはノードのArrayListであり、アクセスした配列と同じサイズ（この場合は5）です。最初に訪問したのは次のようになります：[false false false false false]、したがって、どのノードも訪問されませんでした。listOfChildren（）は、特定のノードの子（すべてではなく、ノードに隣接する子のみ）のArrayListを返します。私は43545454回テストしたので、listOfChildren（）が機能すると確信しています。

どんな助けでもありがたいです（可能であれば、コードの最小限の変更で）。ありがとう。

アップデート：

私のグラフは指示されています。

私はこのように訪問を定義します：

このコードでは、コンストラクターでその中のすべてをfalseに設定します。

ノードは文字列です！訪問済みノードとノードの長さは同じです。そのため、アクセスした配列にnodes.indexOf（blabla）を使用できます。

UPDATE2：

グラフは次のようになります。

問題はN3の後であると確信しています。アルゴリズムは、N1がすでにアクセスされていることを理解していないため、N3の後でループします。なぜこれが起こるのか本当にわかりません！

UPDATE3

文字列の名前は異なり、重複はありません。たとえば、indexOf（nodes.get（2））は0などではなく2を返します。

問題は、N3にアクセスした後、アルゴリズムが停止して0または1を返す必要があることですが、その方法がわかりません:)

AIMA（Artificial Intelligence：A modernapproach）のNorvigによると、下降するサブツリーが無限大になる場合があるため、深さ優先アルゴリズムは完全ではありません（常に解が得られるとは限りません）。

一方、幅優先アプローチは、分岐係数が無限でない場合に完了したと言われます。しかし、それは、DFSでサブツリーが無限である場合と同じ「もの」ではないでしょうか。

ツリーの深さが有限である場合、DFSは完全であるとは言えませんか？BFSの完全性は分岐係数が有限であることに依存しているため、BFSは完全であり、DFSはそうではないのはどうしてですか。