c# - 回溯搜索算法

Question

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

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

n-queens problem - Placing n queens on an n×n chessboard in such a way that no queen can attack another.

一个解决方案

在互联网上搜索“N-queens 回溯”可以找到很多示例代码，维基百科关于回溯的文章甚至在解释什么是回溯时使用了 N-Queens (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 

我的实际实现是通用的，所以我没有利用棋盘镜像/旋转或其他任何巧妙的方法。

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

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

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

Answer 1

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