algorithm - 深さ優先検索の基本

Question

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

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

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

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

Answer 1

一般に、はい、深さ優先検索の考え方は、すべてのノードを生成 (または「訪問」または「展開」) する必要がないということです。

エイト クイーンの問題の場合、別のクイーンを攻撃できるようにクイーンを配置すると、そのブランチを中止できます。解決に導くことはできません。

92 のすべてではなく1 つの解を見つけることを目的として、エイト クイーンのバリエーションを解いていた場合、 1 つを見つけたらすぐにやめることができます。

より一般的には、ある尺度に従ってクイーンの「最適な」配置を見つけるなど、あまり離散的でない問題を解決している場合、最終状態よりも良い最終状態につながる可能性がないことがわかったらすぐにブランチを中止できます。あなたはすでに別のブランチで見つけていました。これは、A* 検索アルゴリズムに関連しています。

さらに一般的に言えば、非常に大きな問題 (チェスなど) に取り組んでいる場合、正確ではない解決策に満足する可能性があるため、既に見つけた解決策におそらくつながらない分岐を中止することができます。

Answer 2

DFSアルゴリズム自体は、ツリー/グラフを生成しません。ツリーとグラフを作成する場合は、検索を実行するのと同じくらい簡単に作成できます。1つの解決策だけを見つけたい場合は、リンクリストのようなフラットなLIFOデータ構造で十分です。新しいノードにアクセスするときに、それをリストに追加します。検索でバックトラックするノードを離れるときは、ノードをポップオフします。