51

ハノイの塔に対するこの珍しい、反復的な解決策を発見したとき、私はインターネットで迷子になりました。

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

この投稿には、回答の1つに同様のDelphiコードもあります。

しかし、私の人生では、なぜこれが機能するのかについての良い説明を見つけることができないようです.

誰でもそれを理解するのを手伝ってもらえますか?

4

3 に答える 3

42

ハノイの塔の再帰的な解決策は、ペグ A から C に N 個のディスクを移動する場合、最初に 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)

明らかに hanoi( _ , _ , _ , 1) は 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 にあります (上の 3 つの星でマークされています)。

ここで、式 (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 の累乗にあるため、ちょうど 1 つのビットが設定されているため、中央の行の値 (この場合は 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)) では movedisk(0, 2) が必要です。再帰規則により、(2 ** (N-2)) で movedisk(0, 1) と (2 ** (N-1)) + 2 ** (N-2) movedisk ( 1、2)。これにより、上の表のさまざまな順列で表示される from ペグの「0,0,1」パターンが作成されます (0,0,1 の行 2、4、および 6 と 0,0 の行 1、2、3 を確認してください)。 、2、および 1、1、0 の行 5、6、7、すべて同じパターンの順列バージョン)。

では、2 のべき乗付近でオフセットを使用して自身のコピーを作成するという特性を持つすべての関数の中で、作成者は 3 を法として正しい順列を生成する関数を選択しました。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です。これにより、"スペア」ペグ。これはアルゴリズムの最後のステップにも当てはまります。したがって、実際には著者のアルゴリズムはわずかな「ごまかし」であることがわかります。つまり、円盤をペグ 0 からペグ 2 N % 3 に移動させているのです。 -指定された「to」ペグ。これは、それほど手間をかけずに変更できます。

元のハノイ アルゴリズムは次のとおりです。

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) を実行すると、"from" と "to" のペグは、行 (a) の対応するペグが 2 N-1 % 3 シフトされたものであると主張します。これは、簡単でより一般的な補題に従います。では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 に答える