回溯搜索算法
我真正的问题是，‘为什么回溯不加速我的搜索？’但如果没有更多的背景我不确定这是否有意义..。
这个问题实际上只是学术性的--代码“工作”，我的程序找到了我是expecting....but的解决方案，我想确保我理解这些术语。为了帮助说明，让我们使用一个具体的例子，我们需要一个搜索算法-n-皇后问题。
N皇后问题 -在n×n棋盘上放置n个皇后，这样就没有女王可以攻击别人。
One解决方案
互联网上有很多例子代码可以在搜索，‘N-皇后回溯’，维基百科关于回溯的文章甚至使用internet解释什么是回溯(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 in a8，Q2 in a7)似乎可以阻止任何可以修剪的情况？
什么板配置，我的呼吸优先实现应该考虑回溯避免？
回答 3
Stack Overflow用户
发布于 2013-07-21 19:43:13
回溯是避免搜索坏路径的几种方法之一。启发法，就像“理性地”放置皇后是另一回事。您的非回溯解决方案一定有足够好的启发，以避免搜索所有无效路径。一个根本没有修剪的解决方案将测试每一个(64选择8)的皇后在董事会上的安排。
Stack Overflow用户
发布于 2013-07-23 14:26:16
香草的回溯和深度优先搜索是一样的。你在树枝上越走越深，当你不能再往前走(因为没有更多的皇后可以放在板子上)的时候，你跟踪你的路向根，然后尝试其他的树枝--因此“回溯”。
你的深度第一搜索和“回溯搜索”可能是相同的算法，只是表面上的不同。当你有6个皇后在董事会上，没有更多的皇后适合那里，你不能“理性地”继续搜索，所以你的深度第一次搜索可能停止在那里无论如何(而不是枚举所有无效的配置，你从添加第7和第8皇后在董事会的任何地方)。
Stack Overflow用户
发布于 2013-07-22 01:08:28
维基百科对回溯的描述将(i)重新访问节点以考虑未访问的分支和(ii)剪枝节点，例如通过强制执行局部一致性的算法。如果不这样做(ii)，那么访问的节点数就不会减少。
https://stackoverflow.com/questions/17775979
复制相似问题
腾讯云开发者
