ハノイの塔の複雑さ
1. 序章
ハノイの塔は、コンピュータサイエンスと数学の両方に応用できる古典的な数学パズルです。 もともとはエドゥアール・リュカというフランスの数学者によって発明されたこのパズルは、再帰の力と優雅さを示しています。
この記事では、ハノイの塔問題のアルゴリズムと複雑さを研究します。 詳細な例を使用して、問題が何であるかを説明することから始めます。 次に、関連するアルゴリズムと複雑さの説明に移ります。
問題の再帰的および反復的な解決策と、再帰的アルゴリズムの擬似コードの両方を紹介します。 最後に、詳細な複雑さの分析を行います。
2. 問題の説明
サイズの異なる3本のロッドとディスクがあります。 どのディスクもどのロッドにもスライドできます。 パズルの初期状態では、1つのロッドにすべてのディスクがあり、サイズが下から上に向かって降順であり、最大のディスクが下にあります。
パズルの目的は、次の3つの簡単なルールに従って、最初のスタック全体を別のロッドに移動することです。
- サイズが小さい別のディスクの上にディスクを配置することはできません
- 一度に移動できるディスクは1つだけです
- 移動するたびに、スタックの1つから一番上のディスクを取り出して、別のスタックの上または空のロッドに移動する必要があります。
合計3つのディスクがある場合のパズルの動作例を見てみましょう。 ロッドをA、B、Cで表します。 3つのロッド（この場合はロッドA）の1つに3つのディスクすべてを積み重ねることから始めます。
目標が3つのディスクすべてをロッドCに移動することであるとしましょう（目的地が重要ではないため、どのロッドを選択するか）。 スタックが1つだけで、このディスクがその一番上にあるため、最初の移動では最小のディスクしか使用できません。 それでは、最小のディスクをロッドCに移動しましょう。
これで、移動できるディスクが2つあります。つまり、最小のディスクと2番目に小さいディスクです。 最小のディスクをロッドAに移動すると元の状態に戻るため、最小のディスクを移動してもあまり効果はありません。最初に最小のディスクをロッドBに移動するだけでよいため、ロッドBに移動するのは冗長です。
したがって、2番目に小さいディスクを移動する必要があることは明らかです。 それをロッドBに移動しましょう：
次に、最小のディスクをロッドBにも移動します。
ロッドCの下部に最大のディスクが必要なことがわかっているので、次の移動はそれをそこに移動することです。
次に、ロッドBのスタックをロッドCに移動する必要があります。 これを行うには、最初に最小のディスクをロッドAに移動します。
次に、2番目に小さいディスクをロッドCに移動できます。
最後に、最小のディスクもロッドCに移動し、完了です。
今行ったことを詳しく見ると、問題が自然に再帰的な構造になっていることがわかります。 最初に、上の2つのディスクをロッドBに移動し、次に最大のディスクをロッドCに移動し、次に最小の2つのディスクをもう一度ロッドCに移動しました。 このパターンは、簡単に実装できる再帰的なソリューションを示しています。
3. アルゴリズム
3.1. 再帰的アルゴリズム
この問題を一連の小さなサブ問題に分解できるため、この問題を再帰的に解決できます。
ディスクのスタックをソースロッドAからデスティネーションロッドCに移動する場合は、次の4ステップのプロセスを使用できます。
- ディスクが1つしかない場合は、ディスクをロッドCに移動して終了します。
- トップディスクをロッドAからロッドBに再帰的に移動します
- ロッドAに残っている最大のディスクをロッドCに移動します
- ディスクのスタックをロッドBからロッドCに再帰的に移動します
手順1と3を見ると、の代わりに移動するディスクがあることを除けば、元の問題と同じ問題を解決していることを確認するのはそれほど難しくありません。 ディスクのスタックをあるロッドから別のロッドに移動しているため、同じ問題が発生します。どのディスクも最大のディスクの上に置くことができます。
3.2. 反復アルゴリズム
この問題を解決する別の方法は、それについて繰り返し考えることです。
この方法の背後にある考え方は、使用しているアルゴリズムの反復に応じて、間で合法的に移動するロッドのペアを選択することです。 このアプローチは再帰的な方法ほど直感的ではありませんが、それでも機能します。
ここでも、再帰的アプローチと同じ4つの入力があります。
- パズルを解くのに必要な最小移動数を計算します。これは次のようになります（この数に到達した方法については後で説明します）。 この値と等しくします。
- その場合でも、デスティネーションロッドを補助ロッドに設定し、補助ロッドを元のデスティネーションロッドに設定します。 言い換えれば、交換と。
- からへのループで繰り返します。 このループの各反復では、3で割ったときに得られる余りに応じて何かを実行します。 i％3 == 1の場合、ロッドとの間を合法的に移動します。 i％3 == 2の場合、ロッドとの間を合法的に移動します。 i％3 == 0の場合、ロッドとの間を合法的に移動します。
4. 擬似コード
これで、擬似コードを使用して、この問題の優れた再帰アルゴリズムを作成できます。 このアルゴリズムは、段階的な指示を印刷することにより、指定されたハノイの塔インスタンスのソリューションを印刷します。
、、、、およびの4つの入力があります。 はディスクの数、はソースロッドの名前、は補助ロッドの名前、はデスティネーションロッドの名前です。
5. 複雑
アルゴリズムにかかる時間は、行われた基本的な動きの数に比例することがわかっています。 私たちの場合、基本的な動きは、ディスクをあるロッドから別のロッドに移動することです。 したがって、ハノイの塔のアルゴリズムにかかる時間は、ディスクを移動する回数に比例します。
ハノイの塔のインスタンスをディスクで解決するために必要なディスク移動の最小数を示します。 この問題の複雑さの分析における私たちの目標は、式を再帰的に使用せずに、の式を取得することです。
まず、ディスクが1つある場合は、1回の移動で目的のロッドに移動できるため、これは1に等しいことに気付きます。 ここで、が等しい場合は、最初に上部のディスクを補助ロッドに再帰的に移動し、最大のディスクを宛先ロッドに移動してから、スタックを補助ロッドから宛先ロッドに再帰的に移動できるためです。
それが最小移動数であることをどうやって知ることができますか？ これは、数学的帰納法によって正式に証明できます。 = 1の基本ケースの場合、1に等しいことがわかりました。 これは、単一のディスクに対して1回の移動よりも優れた移動を行うことはできないため、最小の移動回数です。
次に、帰納的ケースの場合、最初にそれがの最小値であると仮定できます。 少なくとも一番上のディスクをできるだけ少ない数の移動で邪魔にならないように移動してから、最大のディスクを目的のロッドに移動する必要があることを私たちは知っています。 私たちの帰納的仮説により、最小限の動きでこれを達成できることがわかります。
次に、残りのディスクを目的のロッドに移動する必要がありますが、移動回数は最小限に抑えます。 したがって、の合計移動は最小でなければなりません。
これで最小であることがわかりましたが、再帰が含まれていない式を取得したいと思います。 つまり、この漸化式を解きたいのです。
まず、の値にパターンが見つかるかどうかを見てみましょう。 = 1、= 3、= 7、= 15、=31などであることがわかります。 のようなものに等しいようです。 推測とチェックの方法を使用して、この推測が正しいかどうかを確認しましょう。
したがって、私たちの仮説は基本ケースにも当てはまります。 ここで、のすべての小さい値に対して仮説が成り立つと仮定します。 次に、帰納的仮説を使用することにより、それがわかっているので、推測は正しかったです！。
マスター定理を使用したり、繰り返しを展開したりするなど、この繰り返しを解決する方法は他にもあります。
ディスクを使用したハノイの塔インスタンスに必要な移動の最小数はです。 これは、増加するにつれて非常に速く成長します。
今回の複雑さがどれほど悪いかを理解するために、あるディスクをロッドから別のロッドに移動するのに1秒かかるとします。 次に、64個のディスクを持つインスタンスを解決するには、約5,850億年かかります。
6. 結論
この記事では、最初にハノイの塔の問題を紹介して説明しました。
次に、それを解決するための再帰的アルゴリズムと反復的アルゴリズムの両方を提供し、再帰的ソリューションの擬似コードを示しました。
最後に、複雑さの分析を行いました。 このパズルを解くには、少なくとも手順を実行する必要があることがわかりました。
