这种递归的河内塔算法是一种不知情的搜索吗？

Question

void Form(int N, char pegA, char pegB, char pegC) {
    if (N == 1)
        cout<<"move top disk on peg "<<pegA<<" to peg"<<pegC<<endl;
    else {
        Form(N-1, pegA, pegC, pegB);
        cout<<"move top disk on peg "<<pegA<<" to peg"<<pegC<<endl;
        Form(N-1, pegB, pegA, pegC); 
    }
}

这是汉诺塔博弈的递归算法。这可以是深度优先搜索的一种形式吗？如果不是，那是什么？谢谢

Answer 1

这不是深度优先搜索，因为我们知道每次要走哪一步，所以别无选择。你可以这样想。仅此而已。

看，在深度优先搜索的情况下，我们要做什么？我们更深入 尝试 以找到正确的方法。但是在这里，你能告诉我一个不必要的动作吗？没有。

所以这是一个简单的递归方法，我们解决更小问题的实例，然后构造 较大 的解决方案，简单地说，来自较小的结果。就是这样。

Answer 2

这不是深度优先搜索。

是递归树遍历...潜水?

算法内置了走哪一步的逻辑，它巧妙地使用递归来处理每个子塔的转换。这里没有搜索。

算法的工作原理如下

• 递归结束：
  • 当剩下一张盘子时，将其移动到目标挂钩
  • 这是每个子塔移动的结束
• 递归逻辑：
  • 将我们感兴趣的磁盘上方的所有磁盘移动到另一个挂钩
  • 输出我们感兴趣的磁盘的移动命令
  • 将我们之前移动的所有磁盘移动到我们刚刚移动的磁盘之​​上。

它执行此操作的方式是巧妙（且令人困惑）地操纵挂钩引用。它在进行第二次递归调用时重新映射源和目标挂钩。

还有一点要注意：

此算法中没有持久状态。每层关心的唯一状态是 n 的状态，并且只有在它是否为 1 时才关心。在函数入口时，当前层（在起始钉上）和上面的所有层（也在起始钉上）的状态是已知的，并且不需要当前层以下的任何磁盘的状态。

这就是为什么实际上不需要移动任何东西的原因；由于状态是已知的，因此可以将有关状态变化的知识编码到算法中（并且通过传递给递归调用的钉子的更改顺序）。无需根据当前状态做出决策，因此无需影响状态。