我正在尝试改进我目前的8皇后问题算法，这是我第一次真正处理算法设计/算法。我想实现一个深度优先搜索，并与这里描述的不同y值的排列相结合：
http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design
我已经实现了置换部分来解决这个问题，但是我在围绕深度优先搜索的问题上遇到了一些困难。它被描述为遍历树/图的一种方式，但它是否生成树图只有当深度优先搜索生成要遍历的树结构时，通过实现某些逻辑来只生成树的某些部分，这似乎是该方法更有效的唯一方法。
因此，本质上，我必须创建一个算法，生成一个剪枝树词法排列。我知道如何实现剪枝逻辑，但我不确定如何将其与置换生成器绑定，因为我一直在使用下一个置换。
有没有任何资源可以帮助我进行深度优先搜索或创建树型词法排列的基础知识？
最佳答案
一般来说，是的，深度优先搜索的思想是不必生成（或“访问”或“扩展”）每个节点。
在八皇后问题的情况下，如果你放置一个皇后以便它可以攻击另一个皇后，你可以中止该分支；它不能导致一个解决方案。
如果你正在解决八个皇后的变体，这样你的目标是找到一个解决方案，而不是所有的92，那么你可以退出，只要你找到一个。
更普遍地说，如果你正在解决一个不太离散的问题，比如根据某种度量找到皇后的“最佳”排列，那么你可以在知道分支不能比在另一个分支上已经找到的最终状态更好地导致最终状态时立即中止分支。这与A* search algorithm有关。
更普遍地说，如果你正在攻克一个非常大的问题（如象棋），你可能会对一个不精确的解决方案感到满意，因此你可以中止一个分支，这个分支可能无法找到你已经找到的解决方案。
关于algorithm - 深度优先搜索基础，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2704324/