我正试图改进当前的8皇后问题算法，这是我第一次真正处理算法设计/算法。我想实现一个深度优先搜索与此处描述的不同Y值的排列组合： http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design深度优先搜索基础知识
我已经实现了置换部分来解决这个问题，但我有一个小麻烦缠绕我的心围绕深度优先搜索。它被描述为遍历树/图的一种方式，但它会生成树图吗？似乎只有通过深度优先搜索生成要遍历的树结构，通过实现一些逻辑来仅生成树的某些部分，该方法才会更有效。
所以基本上，我将不得不创建一个算法，生成一个修剪的词法排列树。我知道如何实现修剪逻辑，但我只是不确定如何将它与排列生成器配合使用，因为我一直在使用next_permutation。
是否有可以帮助我的深度优先搜索或创建在树的形式lexigraphic排列的基本知识的任何资源？
在一般情况下，是的，深度优先搜索的想法是，你不会有产生（或“访问”或“扩展”）的每一个节点。
在八个皇后问题的情况下，如果你把一个女王，使得它可以攻击其他的女王，则可以中止该分支;它不能导致解决方案。
如果您正在解决Eight Queens的变体，以便您的目标是找到一个解决方案，而不是全部92个，那么只要找到一个解决方案，就可以立即退出。更一般地说，如果你正在解决一个不太离散的问题，比如根据某种方法寻找皇后的“最佳”安排，那么只要你知道它不能导致最终状态更好，你就可以放弃一个分支而不是您在另一个分支上已经找到的最终状态。这与A* search algorithm有关。
更普遍的是，如果您正在攻击一个非常大的问题（如国际象棋），您可能会对某个解决方案非常满意，因此您可以放弃一个可能不会导致解决方案的解决方案你已经找到了。
DFS算法本身不生成树/图。如果你想构建树和图，就像执行搜索一样简单。如果你只想找到一个soution，像链表这样的扁平LIFO数据结构就足够了：当你访问一个新节点时，将它附加到列表中。当您在搜索中使节点返回时，请关闭该节点。
一本名为“算法导论”的书由一位李维坦撰写，为您的理解提供了合适的解释。他还提供了解决8皇后问题的解决方案，就像你描述它的方式一样。它肯定会帮助你。
正如我的理解，为了找到一个解决方案，你不需要任何置换，所有你需要的是dfs.That孤独就足以找到解决方案