深度优先搜索基础知识

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

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

Answer 2

anany levitan的一本名为“算法导论”的书对你的理解有一个恰当的解释。他还提供了8皇后问题的解决方案，就像你描述的那样。它肯定会对你有帮助。

根据我的理解，要找到一个解决方案，你不需要任何排列，你只需要dfs.That就可以找到解决方案