5

我真正的问题是，“为什么回溯不能加快我的搜索速度？” 但我不确定如果没有更多上下文这是否有意义......

这个问题实际上只是学术问题 - 代码“有效”并且我的程序找到了我期望的解决方案......但我想确保我理解这些术语。为了帮助说明问题，让我们使用一个需要搜索算法的特定示例 - n-Queens 问题。

n 皇后问题- 将 n 个皇后放置在 n×n 棋盘上，使得没有皇后可以攻击另一个。

一种解决方案

示例解决方案

互联网上有很多示例代码可以通过搜索“N-queens backtracking”找到，维基百科关于回溯的文章甚至使用 N-Queens 来解释什么是回溯（http://en.wikipedia.org /wiki/回溯）。据我所知，这个想法是，给定一个无效的棋盘配置——假设两个可以互相攻击的皇后，该算法会忽略所有通过添加额外棋子而产生的棋盘配置。

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

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

我的实际实现是通用的，所以我没有利用板镜/旋转或其他任何聪明的东西。

我觉得我一定是误解了，但我没有看到回溯给我带来什么好处？

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

我的呼吸优先实施应该考虑回溯避免哪些板配置？

4

3 回答 3

4

回溯是避免搜索不良路径的几种方法之一。启发式方法，例如“合理地”放置皇后是另一回事。您的非回溯解决方案必须具有足够好的启发式方法以避免搜索所有无效路径。一个完全不修剪的解决方案将测试棋盘上每一个（64 选 8）皇后的排列。

于 2013-07-21T19:43:13.437 回答
1

原版回溯与深度优先搜索是一回事。你在你的分支上越来越深，当你不能继续前进时（因为没有更多的皇后可以放在板上）你跟踪你的路径向后到根，并尝试树的其他分支 - 因此“回溯”。

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

于 2013-07-23T14:26:16.740 回答
0

Wikipedia 对回溯的描述将 (i) 重新访问节点以考虑未访问的分支和 (ii) 修剪节点，例如，通过强制本地一致性的算法。如果您不执行 (ii)，则访问的节点数不会减少。

于 2013-07-22T01:08:28.563 回答