問題タブ [depth-first-search]

8 クイーン問題の現在のアルゴリズムを改善しようとしていますが、アルゴリズムの設計/アルゴリズムを実際に扱うのはこれが初めてです。ここで説明されているさまざまな Y 値の順列と組み合わせた深さ優先検索を実装したい: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

問題を解決するために順列部分を実装しましたが、深さ優先検索に頭を悩ませています。ツリー/グラフをトラバースする方法として説明されていますが、ツリー グラフを生成しますか? ツリーの特定の部分のみを生成するロジックを実装することにより、深さ優先検索がトラバースされるツリー構造を生成する場合にのみ、この方法がより効率的になる唯一の方法のようです。

したがって、基本的には、辞書順列の枝刈りされたツリーを生成するアルゴリズムを作成する必要があります。プルーニング ロジックを実装する方法は知っていますが、next_permutation を使用しているため、それを順列ジェネレーターと結び付ける方法がわかりません。

深さ優先検索の基本や、ツリー形式での辞書順列の作成に役立つリソースはありますか?

深さ優先検索に関するウィキペディア:

深さ優先検索 (DFS) は、ツリー、ツリー構造、またはグラフをトラバースまたは検索するためのアルゴリズムです。1 つはルート (グラフの場合はルートとしていくつかのノードを選択) から開始し、バックトラックする前に各ブランチに沿って可能な限り探索し ます。

幅優先探索とは

「開始ノードを選択し、すべてのノードのバックトラックをチェックし、最短パスを選択し、隣接ノードのバックトラックを選択し、最短パスを選択し、連続的なバックトラックにより各パスをトラバースするため、最終的に最適なパスを見つけるアルゴリズム。

Regexfindのプルーニング -- バックトラッキング?

バックトラッキングという用語は、そのさまざまな用途のために混乱を招きます。UNIX のfindSO ユーザーの剪定は、バックトラッキングで説明されました。Regex Buddy は、正規表現の範囲を制限しない場合、「壊滅的なバックトラッキング」という用語を使用します。あまりにも広く使われている包括的な用語のようです。そう：

1. グラフ理論で特に「バックトラッキング」をどのように定義しますか?
2. 幅優先検索と深さ優先検索の「バックトラック」とは何ですか?

[追加した]

バックトラックに関する適切な定義と例

1. ブルートフォース法
2. ストールマン (?) が発明した用語「依存性指向のバックトラッキング」
3. バックトラッキングと正規表現の例
4. 深さ優先検索の定義。

このアルゴリズムがどのように機能するかは知っていますが、どのアルゴリズムをいつ使用するかを決めることはできませんか?

他の考慮事項よりも優れたパフォーマンスを発揮するガイドラインはありますか?

どうもありがとう。

私はこの質問にかなりの数の答えが存在することを知っています。しかし、私はそれらのどれも実際にそれを要点に持って来ていないのを見つけました。
サイクルは（ほぼ）強連結成分と同じであると主張する人もいます（有向グラフですべてのサイクルを見つける）。そのため、その目標のために設計されたアルゴリズムを使用できます。サイクルの検索は
DFSを介して実行でき、バックエッジをチェックできる と主張する人もいます（ファイルの依存関係に関するグラフのドキュメントを強化します）。グラフ内のすべてのサイクルをDFSを介して検出し、バックエッジをチェックできる かどうかについて、いくつかの提案がありますか？http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf


（ここでSOにあります）は、サイクルベースに基づく1つの方法を述べています。私個人的には、あまり直感的ではないので、別の解決策を探しています。

編集：私の最初の意見は明らかに間違っていました。S.「モロン」による次の答え。
最初の意見：私の意見では、DFS-VISIT（DFSの擬似コード）がまだアクセスされていない各ノードに新たに入るので、実際にそのように機能する可能性があります。その意味で、各頂点は潜在的なサイクルの開始を示します。さらに、DFSが各エッジに1回アクセスすると、サイクルの開始点につながる各エッジもカバーされます。したがって、DFSとバックエッジチェックを使用することで、実際にすべてを検出できるはずです。グラフのサイクル。参加ノードの数が異なるサイクル（三角形、長方形など）が存在する場合は、各サイクルの実際の「形状」を識別するために追加の作業を行う必要があることに注意してください。

主に、BFS ではなく、グラフ内のサイクルを見つけるために DFS が使用されます。理由はありますか？どちらも、ツリー/グラフをトラバースしているときに、ノードが既にアクセスされているかどうかを確認できます。

簡単にするために、テーブルには英語辞書のすべての単語が含まれています。

私がやりたいことは、データをトライとして保存できることです。このようにして、トライのさまざまな分岐をたどり、最も関連性の高い結果を返すことができます。

まず、データをテーブルにトライとして格納するにはどうすればよいですか?

次に、ツリーをどのようにトラバースしますか?

それがまったく役立つ場合、この前の質問の提案は、この質問がどこから発生したかです。

私たちが話しているSQLであることを確認してください。ポインターのおかげでMike DunlaveyのC実装を理解しましたが、この部分（トライ自体）がSQLでどのように機能するかわかりません。

ありがとう、
マット

私はJavaを使用して、指定された「行」と「列」の迷路を互いの上に作成して、グリッドのように見せています。深さ優先の再帰的方法を使用して、部屋 (行と列によって作成されたボックス) の間の「ドアを開く」ことを計画しています。

部屋間のリンクを解除する openDoor メソッドを作成するのに助けが必要です。

C で深さ優先検索を作成しようとしています。検索では、到達可能なすべてのノードのセットを維持する代わりに、Vertex の isVisited フィールドを訪問済みの 1 としてマークする必要があります。これが私のデータ構造体とアルゴリズムの試みです。

DFS実装での私の試みは次のとおりです。

この検索の問題は、ノードが到達可能であっても到達可能であることを決して返さないことです。これを修正する方法を知っている人はいますか？

私は BFS と DFS を理解していますが、一生深化と BFS の違いを理解することはできません。どうやら反復的な深化は DFS と同じメモリ使用量を持っていますが、BFS のように拡張し続けるだけなので、これがどのように可能かはわかりません。誰かがそれを明確にすることができれば、それは素晴らしいことです。

必要に応じて作業するツリー:

私は3Dコンピュータグラフィックスでいくつかのことをしましたが、グラフ理論には少し慣れていません。特に、Perl（Jarkko Hietaniemi）でアルゴリズムをマスターするで説明されているように、深さ優先探索（DFS）を使用して問題を調べ、解決しようとしています。これまでのところ、私はそれを取得することができませんでした:-(しかし、私はかなりです-DFSが私が欲しいものであると確信しています。

Perlである必要はありませんが（言語を学ぼうとしているだけです）、JavaまたはC++が適しています。

私は53の位置ベクトル、つまり（x、y、z）を持っています。

次に、ノード間にランダムなリンクを生成するために作成したPerlプログラムを実行し、最大数を割り当てます。ホップの数、たとえば6。したがって、トポロジは次のようになります。

シンクに到達するまでのパス「実行」、つまり0を決定したいと思います。たとえば、ノード1からノード18、ノード3...このパスはすでに完了しています。。。。

DFSが欲しいと思います。再帰的な運動のようです。

誰かが私にコードを理解してくれてくれたら、それは素晴らしいことです。私は学生ではありませんが、51歳です！多分それは私がこれを取得していないことと関係があります:-)

私は自分のqを見て、何らかの理由で（おそらく私:-(それは「文字化け」していた）

トポロジは5のようになります<-ノード1には5つのリンクがあります。18 4 23 6 48 <-ノード18、ノード4、ノード23、ノード6、ノード482<-ノード2には2つのリンクがあります。14 5、<-ノード14、ノード5 0 <-ノード3はリンクがないため、リーフです。。。2<-ノード18には2つのリンクがあります。3 17 <-ノード3、ノード17。。。4<-ノード53には4つのリンクがあります。10 46 49 22 <-ノード10、ノード46、ノード49、ノード22

誰かがコードを提供できる場合に備えて明確にしておきたい（Perl、Java、c ++ / C ...）

ありがとう。