这是如何运作的？河内解决方案奇怪的塔

Question

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

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

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

然而,对于我的生活,我似乎无法找到一个很好的解释为什么这个工作.

任何人都可以帮我理解吗？

Answer 1

对河内塔的递归解决方案是这样的,如果你想将N个盘子从钉子A移动到C,你先将N-1从A移动到B,然后将底部的一个移动到C,然后再移动N.从B到C的1个磁盘.本质上,

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

很明显,河内(_,_,_,1)采取一次行动,河内(_,_,_,k)采取与2*河内(_,_,_,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 ->  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)和at(2**(N-1))+ 2**(N-2)movingisk( 1,2).这为from pegs创建了"0,0,1"模式,在上表中可以看到不同的排列(检查0,4,1的行2,4和6以及0,0的行1,2,3) ,2,和行5,6,7为1,1,0,相同模式的所有置换版本).

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

Answer 2

antti.huima的解决方案基本上是正确的,但是我想要更严格的东西,而且它太大而不适合评论.开始:

首先注意:在该算法的中间步骤x = 2 ^N-1处,"from"peg为0,"to"peg为2 ^N%3.这使得"2" ^(N-1)%3为"备用的"挂钩.对于算法的最后一步也是如此,因此我们看到作者的算法实际上是一个轻微的"欺骗":他们将磁盘从挂钩0移动到挂钩2 ^N%3,而不是固定的, - 指定"到"挂钩.这可以改变,没有太多的工作.

最初的河内算法是:

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,"备用"= 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)行中,钉子恰好是河内(0,2 ^N- 1,2 ^N,N-1)移动2 ^N-1%3 的钉子,即 它们正好是钉子(a)行加入这一数量.

我声称,当我们运行第(c)行时,"from"和"to"pegs是线(a)相应的钉子移动了2 ^N-1%3.这是从简单的,更一般的引理得出的在hanoi(a+x, b+x, c+x, N)那里,"从和"到"钉子"正好从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.

这两个都很容易显示.