我'm trying to improve my current algorithm for the 8 Queens problem, and this is the first time I' m真正处理算法设计/算法 . 我想实现深度优先搜索，并结合此处描述的不同Y值的排列：http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design
我已经实现了排列部分来解决这个问题，但是我在深度优先搜索时遇到了一些麻烦 . 它被描述为遍历树/图的一种方式，但它是否生成树图？只有当深度优先搜索生成要遍历的树结构时，通过实现某些逻辑才能生成树的某些部分，这似乎是唯一的方法 .
基本上，我必须创建一个算法，生成一个修剪过的lexigraphic排列树 . 我知道如何实现修剪逻辑，但我不知道如何将其与置换生成器联系起来，因为我一直在使用next_permutation .
是否有任何资源可以帮助我进行深度优先搜索或以树形式创建lexigraphic排列的基础知识？
3 回答
通常，是的，深度优先搜索的想法是您不必生成（或“访问”或“扩展”）每个节点 .
在八皇后问题的情况下，如果你放置一个女王，它可以攻击另一个女王，你可以中止该分支;它不能导致解决方案 .
如果您正在解决八皇后的变体，那么您的目标是找到 one 解决方案，而不是全部92，那么您可以在找到解决方案后立即退出 .
更一般地说，如果你正在解决一个不那么离散的问题，比如根据某种方法找到女王的排列，那么一旦你知道它不能导致最终状态比最终状态更好，你就可以中止分支 . d已经在另一个分支上找到了 . 这与A* search algorithm有关 .
更一般地说，如果你正在攻击一个非常大的问题（比如国际象棋），你可能会对一个不准确的解决方案感到满意，所以你可以中止一个可能已经找到的分支 .
DFS算法本身不生成树/图 . 如果您想构建树和图形，那么在执行搜索时就像构建它一样简单 . 如果您只想找到一个源，那么像链接列表这样的扁平LIFO数据结构就足够了：当您访问新节点时，将其附加到列表中 . 当您在搜索中退出节点回溯时，请关闭该节点 .
anany levitan的一本名为“算法简介”的书对你的理解有适当的解释 . 他还提供了解决8皇后问题的解决方案 . 它肯定会帮到你 .
根据我的理解，为了找到一个解决方案，你不需要任何排列，你只需要dfs . 这将是寂寞足以找到解决方案