ハノイ塔のアルゴリズム: Python, C++ Code

ハノイの塔とは何ですか？

ハノイの塔は、3本の棒と、大きさが徐々に小さくなる円盤を積み重ねた構造からなる数学パズルです。フランスの数学者エドゥアール・リュカが1883年に考案したことから、ブラフマーの塔、あるいはリュカの塔とも呼ばれています。このパズルは、3本の棒の間で金の円盤を動かすという伝説に基づいています。

このパズルは3本の棒と、積み重ねられた円盤の枚数（可変）で構成されています。棒は円柱状に積み重ねられており、大きな円盤は下部に、小さな円盤は上部に積み重ねられています。

最初に、3本の棒（またはペグ）が与えられます。そのうちの1本（例ではペグA）には、すべてのディスクが積み重ねられています。目標は、いくつかの特定のルールに従いながら、積み重ねられたディスク全体を1本の棒（A）から別の棒（C）に移動させることです。

パズルの初期設定は以下のとおりです。

ハノイ塔問題

そしてこれが最終目標です。

ハノイ塔のルール

ハノイの塔に関する基本的なルールは以下のとおりです。

• パズルの初期状態では、すべてのディスクが1番目の棒の上に積み重ねられています。
• 最終状態では、ロッド１からのすべてのディスクがロッド２またはロッド３の上に積み重ねられる。
• 一度に1枚のディスクだけが、1本のロッドから別のロッドへ移動できる。
• ロッドの一番上のディスクのみを動かすことができます。
• ディスクを小さいディスクの上に置くことはできません。

元の伝説は、64枚の円盤を動かすというものでした。司祭たちは、規則に従って一度に1枚の円盤を動かすことができました。伝説によると、彼らがこの行為を成し遂げれば世界が終わるという予言がありました。時間計算量のセクションでは、n枚の円盤を使ったハノイの塔の設定では、2^n – 1回の移動が必要であることを示します。

つまり、司祭たちが円盤を1枚動かすのに1秒かかったとすると、パズルを解くのにかかる合計時間は2^64 - 1秒、つまり約584,942,417,356年26日7時間15秒になります。

ハノイ塔のアルゴリズム

ハノイの塔を解く最も一般的な方法は、再帰アルゴリズムを用いることです。まず、2本の棒を始点と終点として選び、予備の棒を補助棒またはヘルパーとして用います。

ハノイの塔パズルを解く手順は次のとおりです。

• 上位 n-1 個のディスクをソース ペグからヘルパー ペグに移動します。
• n番目のディスクをソースピンからデスティネーションピンに移動します。
• 残りのn-1枚のディスクを補助ペグから目的のペグに移動させます。

注意： ディスクが1枚しかない場合は、ソースから宛先へ直接移動できます。

ハノイの塔パズルの解き方

3枚のディスクを使ったアルゴリズムを説明しましょう。ペグAをソース、ペグBをヘルパー、ペグCを宛先とします。

ステップ1） 最初は、すべてのディスクがAの杭に積み重ねられています。

この段階では、ソース＝ペグA、宛先＝ペグC、ヘルパー＝ペグBとなります。

次に、上位 n-1 個のディスクをソースからヘルパーに移動する必要があります。

注意： 一度に移動できるディスクは1枚だけですが、この手順によって3枚のディスクの問題が2枚のディスクの問題に縮小され、再帰呼び出しによって処理されます。

ステップ2） ペグAからペグBを宛先として再帰呼び出しを行う際に、ヘルパーとしてペグCを使用します。

同じハノイの塔の問題で、ステージ1に戻ったことに注目してください。ただし、今回は2枚のディスクです。n-1枚（つまり1枚）のディスクをソースからヘルパーに移動させ、ヘルパーは最小のディスクを杭Aから杭Cに移動させます。

この段階では、ソース＝ペグA、宛先＝ペグB、ヘルパー＝ペグCとなります。

ステップ3） アルゴリズムによれば、n番目（2番目）のディスクが宛先であるペグBに転送されます。

この段階では、ソース＝ペグA、宛先＝ペグB、ヘルパー＝ペグCとなります。

ステップ4） 次に、アルゴリズムの第3段階に従って、n-1枚目のディスク（ディスク1）を補助ペグCから目的のペグBに移動させます。

この段階では、ソース＝ペグA、宛先＝ペグB、ヘルパー＝ペグCとなります。

ステップ5） 再帰呼び出しが完了すると、アルゴリズムの最初の段階の以前の設定に戻ります。

ステップ6） 第2段階では、ディスク3をソースのペグAから宛先のペグCに移動します。

この段階では、ソース＝ペグA、宛先＝ペグC、ヘルパー＝ペグBとなります。

ステップ7） 次の作業は、残りのディスクをヘルパー（ペグB）から宛先（ペグC）に移動することです。今回は、元のソース（ペグA）をヘルパーとして使用します。

ステップ8） 2枚のディスクを同時に移動できないため、ディスク1に対して再帰呼び出しを行います。 アルゴリズムこのステップでの目的地はペグAです。

この段階では、ソース＝ペグB、宛先＝ペグA、ヘルパー＝ペグCとなります。

ステップ9） 再帰呼び出しが完了しました。次に、ディスク2をソースから宛先に移動します。

この段階では、ソース＝ペグB、宛先＝ペグC、ヘルパー＝ペグAとなります。

ステップ10） 最後に、残りのn-1枚のディスク（ディスク1）をヘルパーから宛先へ移動させます。

この段階では、ソース＝ペグA、宛先＝ペグC、ヘルパー＝ペグBとなります。

ニックネーム Code ハノイの塔のために

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

プログラムコード C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

出力：

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

プログラムコード Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

出力：

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

ハノイの塔の複雑さ

ハノイの塔の時間計算量と空間計算量は以下のとおりです。

1) 時間計算量:

アルゴリズムを振り返ってみると、1回の呼び出しで(n-1)個のディスクに対して2回再帰呼び出しを行います。各(n-1)回の再帰は((n-1)-1)回の再帰に分解され、これを繰り返して最終的に単一ディスクの基本ケースに到達します。

3枚のディスクの場合：

• ディスク3は、ディスク2の再帰関数を2回呼び出します。
• ディスク2は、ディスク1の再帰関数を2回呼び出します。
• ディスク1は一定時間で移動するため、3枚のディスクについて解くのに十分な時間がある。

繰り返しとして表現すると：

= 2 × (2枚のディスクを解くのにかかる時間) + ディスク3を移動させるのにかかる定数時間

= 2 × (2 × ディスク1枚を解くのにかかる時間 + ディスク2を移動させるのにかかる定数時間) + ディスク3を移動させるのにかかる定数時間

= (2 × 2) × ディスク1の移動にかかる定数時間 + 2 × ディスク2の移動にかかる定数時間 + ディスク3の移動にかかる定数時間

n 枚のディスクの場合、これは次のようになります。

2^n-1 × ディスク1 + 2を移動するのにかかる定数時間^n-2 × ディスク2を移動する定数時間 + …

この等比数列の合計は O(2) になりますⁿ – 1) は、以下のように簡略化されます。 O（2ⁿ)指数関数的な時間計算量。

2) 空間計算量:

ハノイの塔の空間計算量はO(n)です。再帰処理ではコールスタックが使用され、スタックの最大深度はディスクの数であるnに等しくなります。そのため、空間計算量はO(n)となります。

よくあるご質問