深度第一搜索基础知识

Question

我正在尝试改善8皇后问题的当前算法，这是我第一次真正处理算法设计/算法。我想实现深度优先搜索，并结合此处描述的不同Y值的排列：http://en.wikipedia.org/wiki/eight_queens_puzzle#the_eight_queens_queens_puzzle_as_as_an_exercise_in_algorithm_design

我已经实施了置换部分来解决问题，但是在深度优先的搜索中，我遇到了一些麻烦。它被描述为遍历树/图的一种方式，但是它会生成树图吗？似乎只有当深度优先搜索生成要穿越的树结构，通过实现某些逻辑以仅生成树的某些部分来生成要穿越的树结构时，此方法似乎更有效。

因此，从本质上讲，我将不得不创建一种算法，该算法生成修剪的Lexigraphic排列树。我知道如何实现修剪逻辑，但是我不确定如何将其与置换生成器联系起来，因为我一直使用next_permunt。

是否有任何资源可以帮助我进行深度搜索的基础知识或以树形式创建词法排列？

Answer 1

通常，是的，深度优先搜索的想法是，您不必生成每个节点（或“访问”或“扩展”）。

在八个皇后问题的情况下，如果您放置一个女王可以攻击另一个女王，则可以中止该分支。它不能导致解决方案。

如果您要解决八个皇后的变体，以便您的目标是找到 一 解决方案，不是全部92，那么您就可以在找到一个解决方案后立即辞职。

更一般地，如果您解决了一个较少离散的问题，例如根据某种措施找到皇后区的“最佳”安排，那么一旦您知道它不能导致最终状态比最终状态更好您已经在另一个分支上找到了。这与 a*搜索算法.

更一般地，如果您要攻击一个非常大的问题（例如国际象棋），您可能对不准确的解决方案感到满意，因此您可以中止一个分支机构 大概 无法导致您已经找到的解决方案。

Answer 2

DFS算法本身不会生成树/图。如果要构建树和图形，则像执行搜索一样简单地构建它。如果您只想找到一个soution，那么像链接列表这样的平坦LIFO数据结构就足够了：当您访问新节点时，请将其附加到列表中。当您将节点留在搜索中时，请弹出节点。

Answer 3

Anany Levitan的一本名为“算法简介”的书为您的理解提供了适当的解释。他还以您下降的方式为8个皇后问题提供了解决方案。它一定会帮助您。

作为我的理解，要找到一个解决方案，您不需要任何置换您所需要的只是DF。