ハノイの塔（Tower of Hanoi）

Tower of Hanoi

探索・推論 重要度：中

概要

ハノイの塔（Tower of Hanoi）とは、3本の杭と大きさの異なる複数の円盤を使った数学パズルです。すべての円盤が大きい順に1本の杭に積まれた状態から、一定のルールに従って別の杭に全ての円盤を移動させることが目的です。このパズルは再帰的アルゴリズム（recursive algorithm）の代表的な例として知られ、AIや計算機科学の基礎教育で広く取り上げられています。

1883年にフランスの数学者エドゥアール・リュカ（Edouard Lucas）が考案しました。n枚の円盤を移動させるために必要な最小手数は「2^n - 1」回であり、円盤の数が増えるにつれて指数関数的に手数が増大するため、計算量の爆発を理解するための教材としても優れています。

詳細解説

ハノイの塔のルール

ハノイの塔には以下の3つのルールがあります。

  1. 一度に移動できる円盤は1枚だけである
  2. 各杭の一番上にある円盤しか移動できない
  3. 小さい円盤の上に大きい円盤を置くことはできない

これらのルールを守りながら、すべての円盤を初期の杭から目標の杭に移動させる最短手順を求めることが問題の核心です。

再帰的解法

ハノイの塔の解法は、再帰的な考え方で非常にシンプルに表現できます。n枚の円盤を杭Aから杭Cに移動させるには、以下の3ステップを実行します。

  1. 上のn-1枚の円盤を杭Aから杭Bに移動させる（杭Cを補助として使用）
  2. 最も大きい円盤（n番目）を杭Aから杭Cに移動させる
  3. 杭Bに移動したn-1枚の円盤を杭Cに移動させる（杭Aを補助として使用）

この手順を再帰的に適用することで、任意の枚数の円盤を移動できます。n=1の場合は直接1枚の円盤を移動するだけです（再帰の基底条件）。

計算量と組合せ爆発

ハノイの塔の最小手数は 2^n - 1 で表されます。具体的な値は以下の通りです。

円盤の枚数（n）最小手数（2^n - 1）
11
37
531
101,023
201,048,575
64約1.8 x 10^19

円盤が64枚の場合、最小手数は約1.8 x 10^19（約1844京）回に達します。これは指数関数的増加（組合せ爆発）の典型例であり、問題の規模が大きくなると現実的な時間内に解くことが困難になることを示しています。この性質は、AI分野における計算量の議論やトイ・プロブレムの限界を考える際に重要な概念です。

探索木としてのハノイの塔

ハノイの塔の全状態を探索木として表現することもできます。n枚の円盤の場合、取りうる状態の総数は3^n通りであり、各状態から遷移可能な状態をエッジで結ぶと状態空間グラフが構築されます。この状態空間を探索することで、初期状態からゴール状態への最短経路を見つけることができます。

歴史・背景

ハノイの塔は、1883年にフランスの数学者エドゥアール・リュカによって考案されました。リュカはこのパズルを「N. Claus de Siam」（エドゥアール・リュカのアナグラム）というペンネームで発表しました。パズルには「インドのベナレスにある寺院で、ブラフマーの僧侶たちが64枚の金の円盤を移動させている。すべての円盤の移動が完了したとき、世界が終わる」という伝説が付けられています。

計算機科学では、再帰アルゴリズムの教育において最も基本的な例題の一つとして広く使われています。また、この問題は分割統治法（Divide and Conquer）の考え方を理解するための優れた教材でもあります。AIの文脈では、トイ・プロブレム（おもちゃの問題）の代表例として、探索や問題解決の基本概念を学ぶために用いられます。

具体的な事例

プログラミング教育での活用

ハノイの塔は、プログラミング教育において再帰関数の理解を深めるための定番の課題です。多くのプログラミング言語の教科書で取り上げられ、関数が自身を呼び出す仕組み（再帰呼出し）の本質を学ぶことができます。

計算量の理解

円盤64枚のハノイの塔を1秒に1回の移動で解くと、約5,845億年かかります。これは宇宙の年齢（約138億年）をはるかに超える時間であり、指数関数的な計算量の増大がいかに深刻であるかを直感的に理解できる例です。

AIのトイ・プロブレムとして

ハノイの塔は、AIにおけるトイ・プロブレムの代表例です。明確なルールと目標があるため、探索アルゴリズムの動作を検証するのに適しています。しかし、円盤の枚数が増えると計算量が爆発的に増加するため、実世界の複雑な問題をAIで解く際の限界を示す教材ともなります。

G検定での出題ポイント

試験対策のポイント ハノイの塔はG検定で以下のポイントが問われることがあります。
  • ハノイの塔の3つのルール（1枚ずつ移動、上の円盤のみ移動可能、大きい円盤を小さい円盤の上に置けない）を正確に理解する
  • 最小手数が「2^n - 1」であることを覚える（n=3なら7手、n=5なら31手）
  • 再帰的解法の考え方（分割統治法）を理解する
  • 指数関数的な計算量の増大（組合せ爆発）との関連を理解する
  • トイ・プロブレムの一例としての位置づけを押さえる
  • 1883年にフランスの数学者エドゥアール・リュカが考案したことを知っておく