logo标签列表

回溯搜索算法

c#pythonalgorithmsearch
5
我的真正问题是，“为什么回溯法不能加速搜索？”但我不确定没有更多上下文是否有意义...
这个问题实际上只是学术性的 - 代码“可以工作”，我的程序能够找到我期望的解决方案...但我想确保我理解术语。为了帮助说明问题，让我们使用一个需要搜索算法的具体例子 - n皇后问题。 n-queens problem - 在n×n的棋盘上放置n个皇后，使得没有一个皇后可以攻击另一个皇后。
一个解决方案。

Example Solution

在互联网上可以找到很多关于“N皇后问题回溯算法”的示例代码，维基百科的回溯算法文章甚至在解释回溯算法时使用了N皇后问题（http://en.wikipedia.org/wiki/Backtracking）。据我所知，这个想法是，如果给定一个无效的棋盘配置，比如两个可以互相攻击的皇后，算法会忽略通过添加额外棋子而产生的所有棋盘配置。

我还实现了一个（非递归/非回溯）深度优先和广度优先版本的搜索。如预期的那样，这两种变体测试了完全相同数量的状态。我预计使用递归、深度优先和回溯算法应该测试更少的状态。但我没有看到这一点。

Depth First
    Found 92 solutions in 10.04 seconds
    Tested 118969 nodes (1.2k nodes per second)
    Largest Memory Set was 64 nodes
BackTracking
    Found 92 solutions in 9.89 seconds
    Tested 118969 nodes (1.2k nodes per second)
    Largest Memory Set was 170 nodes
Breadth First
    Found 92 solutions in 12.52 seconds
    Tested 118969 nodes (0.95k nodes per second)
    Largest Memory Set was 49415 nodes

我的实现旨在通用，因此我不会利用棋盘的镜像/旋转或其他任何聪明的东西。

我觉得我一定是误解了，但我不知道回溯给我带来了什么好处？

维基百科解释说，一旦发现某个状态无效，它的子树就会被跳过（剪枝），但合理地放置皇后（避免Q1在a8和Q2在a7）似乎可以防止任何可以被剪枝的情况？

我的广度优先实现应该考虑哪些棋盘配置，而回溯则可以避免这些情况？

3
你确定你的深度优先搜索不已经是一种回溯算法了吗？（回溯并不需要递归。） - user2357112
2
@user2357112 绝对正确；这是一个奇怪的问题；你说你已经实现了深度优先和广度优先的解决方案“没有回溯”，但深度优先和广度优先都是回溯策略，所以这对我来说毫无意义。 - Eric Lippert
3个回答
4
回溯法是避免搜索错误路径的几种方式之一。例如，像“合理地”放置皇后这样的启发式方法也是一种方式。您的非回溯解决方案必须具有足够好的启发式方法，以避免搜索所有无效的路径。没有任何修剪的解决方案将测试棋盘上所有皇后的(64个中选择8个)排列。
1

香草回溯算法与深度优先搜索相同。您在分支上越来越深，当无法继续（因为不能再放置更多皇后）时，您会向根回溯并尝试树的另一个分支---因此称为“回溯”。

您的深度优先搜索和“回溯搜索”可能是相同的算法，只是有些表面差异。当您在棋盘上放置了6个皇后并且没有更多的皇后适合时，您可能无法“理性地”继续搜索，因此您的深度优先搜索也会在那里停止（而不是枚举从任何位置添加第7个和第8个皇后得到的所有无效配置）。

0

维基百科对回溯的描述混淆了两个概念：（i）重新访问节点以考虑未访问的分支和（ii）修剪节点，例如通过强制执行本地一致性的算法。如果不执行（ii），则访问的节点计数不会减少。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接