51

当我发现河内塔的这种不同寻常的迭代解决方案时，我迷失在互联网上：

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

这篇文章在其中一个答案中也有类似的 Delphi 代码。

但是，对于我的一生，我似乎找不到一个很好的解释来解释为什么会这样。

谁能帮我理解一下？

4

3 回答 3

42

河内塔的递归解决方案有效，因此如果要将 N 个磁盘从挂钩 A 移动到 C，首先将 N-1 从 A 移动到 B，然后将底部的一个移动到 C，然后再次移动 N- 1个磁盘从B到C。本质上，

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

很明显 hanoi( _ , _ , _ , 1) 走一步，而 hanoi ( _ , _ , _ , k) 走的步数和 2 * hanoi( _ , _ , _ , k-1) + 1 一样多。所以解决方案长度按 1、3、7、15、... 的顺序增长。这与 (1 << k) - 1 的顺序相同，它解释了您发布的算法中的循环长度。

如果您查看解决方案本身，对于 N = 1，您会得到

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

对于 N = 2，你得到

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

对于 N = 3 你得到

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

由于解决方案的递归性质，FROM 和 TO 列遵循递归逻辑：如果您在列上取中间条目，则上面和下面的部分是彼此的副本，但数字是置换的。这是算法本身的一个明显结果，它不对挂钩数执行任何算术运算，而只是对它们进行置换。在 N=4 的情况下，中间行位于 x=4（上面标有三颗星）。

现在表达式 (X & (X-1)) 取消设置 X 的最小设置位，因此它映射例如从 1 到 7 的数字，如下所示：

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

诀窍是，因为中间行始终是 2 的精确幂，因此恰好设置了一个位，当您将中间行值（在本例中为 4）添加到行（即 4=0+4、6=2+6）。这实现了“复制”属性，中间行的添加实现了排列部分。表达式 (X | (X-1)) + 1 设置右边有 1 的最低零位，并清除这些位，因此它具有与预期相似的属性：

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

至于为什么这些序列实际上会产生正确的挂钩编号，让我们考虑 FROM 列。递归解决方案从 hanoi(0, 2, 1, N) 开始，所以在中间行 (2 ** (N-1)) 你必须有 moveisk(0, 2)。现在根据递归规则，在 (2 ** (N-2)) 你需要有 moveisk(0, 1) 和在 (2 ** (N-1)) + 2 ** (N-2) moveisk ( 1、2)。这会为 from pegs 创建“0,0,1”模式，在上表中以不同的排列可见（检查 0,0,1 的第 2、4 和 6 行以及 0,0 的第 1、2、3 行） ,2 和 1,1,0 的第 5、6、7 行，所有相同模式的置换版本）。

现在，在所有具有这种特性的函数中，它们围绕 2 的幂创建自身的副本但具有偏移量，作者选择了那些产生模 3 正确排列的函数。这并不是一项非常困难的任务，因为三个整数 0..2 只有 6 种可能的排列，并且排列在算法中按逻辑顺序进行。(X|(X-1))+1 不一定与河内问题密切相关，也不需要如此；它具有复制属性并且恰好以正确的顺序产生正确的排列就足够了。

于 2010-02-06T05:18:57.403 回答
9

antti.huima 的解决方案基本上是正确的，但我想要更严格的东西，而且它太大而无法放入评论中。开始：

首先注意：在该算法的中间步骤 x = 2 N-1，“from” peg 为 0，“to” peg 为 2 N % 3。这留下 2 (N-1) % 3 为“备用”挂钩。对于算法的最后一步也是如此，所以我们看到实际上作者的算法是一个轻微的“欺骗”：他们将磁盘从 peg 0 移动到 peg 2 N % 3，而不是固定的 pre - 指定的“到”挂钩。这可以通过不多的工作来改变。

原始的 Hanoi 算法是：

hanoi(from, to, spare, N):
    hanoi(from, spare, to, N-1)
    move(from, to)
    hanoi(spare, to, from, N-1)

插入 "from" = 0, "to" = 2 N % 3, "spare" = 2 N-1 % 3，我们得到（抑制 %3）：

hanoi(0, 2**N, 2**(N-1), N):
(a)   hanoi(0, 2**(N-1), 2**N, N-1)
(b)   move(0, 2**N)
(c)   hanoi(2**(N-1), 2**N, 0, N-1)

这里的基本观察是：在 (c) 行中，钉子恰好是 hanoi(0, 2 N-1 , 2 N , N-1) 移动了 2 N-1 % 3 的钉子，即 它们正是钉子行 (a) 中添加了这个数量。

我声称，当我们运行 (c) 行时，“从”和“到”钉子是 (a) 行的相应钉子，偏移了 2 N-1 % 3。这是从简单、更一般的引理得出的即 in hanoi(a+x, b+x, c+x, N)，“from”和“to”钉子从 in 精确移动 x hanoi(a, b, c, N)。

现在考虑函数
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

为了证明给定的算法有效，我们只需要证明：

  • f(2 N-1 ) == 0 和 g(2 N-1 ) == 2 N
  • 对于 0 < i < 2 N，我们有 f(2 N - i) == f(2 N + i) + 2 N % 3，并且 g(2 N - i) == g(2 N + i) + 2 N % 3。

这两个都很容易展示。

于 2011-02-20T02:26:27.200 回答
4

这不是直接回答问题，但是太长了，无法发表评论。

我总是通过分析接下来应该移动的磁盘大小来做到这一点。如果您查看移动的磁盘，则会发现：

1 disk  : 1
2 disks : 1 2 1
3 disks : 1 2 1 3 1 2 1
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

奇数大小总是以与偶数相反的方向移动，如果钉 (0, 1, 2, 重复) 或 (2, 1, 0, 重复)。

如果你看一下模式，移动的环是移动xor次数和移动次数 + 1 的最高位集合。

于 2010-02-06T14:10:49.757 回答