深度优先搜索基础知识
我正在尝试改进当前针对 8 个皇后问题的算法，这是我第一次真正处理算法设计/算法。我想实现深度优先搜索并结合此处描述的不同 Y 值的排列： _puzzle_as_an_exercise_in_algorithm_design
我实现了排列部分来解决问题，但是我在围绕深度优先搜索进行思考时遇到了一些麻烦。它被描述为一种遍历树/图的方式，但它会生成树图吗？似乎只有当深度优先搜索生成要遍历的树结构时，通过实现一些逻辑来仅生成树的某些部分，该方法才会更有效。
所以本质上，我必须创建一个算法来生成经过修剪的词典排列树。我知道如何实现修剪逻辑，但我只是不确定如何将其与排列生成器结合起来，因为我一直在使用 next_permutation。
是否有任何资源可以帮助我了解深度优先搜索或以树形式创建词典排列的基础知识？
I'm trying to improve my current algorithm for the 8 Queens problem, and this is the first time I'm really dealing with algorithm design/algorithms. I want to implement a depth-first search combined with a permutation of the different Y values described here:
http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design
I've implemented the permutation part to solve the problem, but I'm having a little trouble wrapping my mind around the depth-first search. It is described as a way of traversing a tree/graph, but does it generate the tree graph? It seems the only way that this method would be more efficient only if the depth-first search generates the tree structure to be traversed, by implementing some logic to only generate certain parts of the tree.
So essentially, I would have to create an algorithm that generated a pruned tree of lexigraphic permutations. I know how to implement the pruning logic, but I'm just not sure how to tie it in with the permutation generator since I've been using next_permutation.
Is there any resources that could help me with the basics of depth first searches or creating lexigraphic permutations in tree form?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一般来说，是的，深度优先搜索的想法是您不必生成（或“访问”或“扩展”）每个节点。
在八皇后问题的情况下，如果您放置一个皇后使其可以攻击另一个皇后，您可以中止该分支；它无法导致解决方案。
如果您正在解决八皇后的变体，并且您的目标是找到一个解决方案，而不是全部 92 个，那么您可以在找到一个后立即退出。
更一般地说，如果您正在解决一个不太离散的问题，例如根据某种措施找到皇后的“最佳”排列，那么一旦您知道它不能导致比最终状态更好的最终状态，您就可以中止一个分支你已经在另一个分支上找到了。这与 A* 搜索算法有关。
更一般地说，如果您正在解决一个非常大的问题（例如国际象棋），您可能会对不精确的解决方案感到满意，因此您可以中止一个可能无法导致的分支您已经找到的解决方案。
In general, yes, the idea of the depth-first search is that you won't have to generate (or "visit" or "expand") every node.
In the case of the Eight Queens problem, if you place a queen such that it can attack another queen, you can abort that branch; it cannot lead to a solution.
If you were solving a variant of Eight Queens such that your goal was to find one solution, not all 92, then you could quit as soon as you found one.
More generally, if you were solving a less discrete problem, like finding the "best" arrangement of queens according to some measure, then you could abort a branch as soon as you knew it could not lead to a final state better than a final state you'd already found on another branch. This is related to the A* search algorithm.
Even more generally, if you are attacking a really big problem (like chess), you may be satisfied with a solution that is not exact, so you can abort a branch that probably can't lead to a solution you've already found.
DFS 算法本身不生成树/图。如果您想构建树和图，构建它就像执行搜索一样简单。如果您只想找到一个解决方案，像链表这样的平面后进先出数据结构就足够了：当您访问一个新节点时，将其附加到列表中。当您在搜索中留下要回溯的节点时，弹出该节点。
The DFS algorithm itself does not generate the tree/graph. If you want to build the tree and graph, it's as simple building it as you perform the search. If you only want to find one soution, a flat LIFO data structure like a linked list will suffice for this: when you visit a new node, append it to the list. When you leave a node to backtrack in the search, pop the node off.
anany Levitan写的一本叫《算法导论》的书，对你的理解有正确的解释。他还按照您所描述的方式提供了 8 个皇后问题的解决方案。它肯定会对你有帮助。
据我了解，要找到一个解决方案，您不需要任何排列，您需要的只是 dfs。这足以找到解决方案
A book called "Introduction to algorithms" by anany levitan has a proper explanation for your understanding. He also provided the solution to 8 queens problem just the way you desctribed it. It will helpyou for sure.
As my understanding, for finding one solution you dont need any permutation all you need is dfs.That will lonely suffice in finding solution