ハノイの塔 (G検定)

1. 定義と概要

ハノイの塔とは、3本の杭と大きさの異なる複数の円盤を使うパズルで、最初はすべての円盤が1本の杭に大きい順に積まれた状態から始まります。ルールは「一度に動かせる円盤は1枚だけ」「小さい円盤の上に大きい円盤を置けない」の2つで、この制約に従ってすべての円盤をそっくり別の杭へ移し替えれば完成です。

円盤の枚数をnとしたとき、すべての円盤を移し終えるまでに必要な最小の手数は、2をn回掛け合わせた数から1を引いた回数になります。たとえば円盤3枚なら7回、円盤10枚なら1023回という具合に、枚数が増えるほど手数は急激に増えていきます。枚数が1枚増えるだけで手数がおおよそ倍近くまで膨らむ点が、このパズルの特徴です。

従来、探索・推論の考え方はチェスや迷路のような身近な題材で説明されることが多くありました。ハノイの塔はルールが単純明快でありながら、円盤の配置と1回の移動の組み合わせが枚数の増加とともに急激に複雑化するため、探索木（状態の移り変わりを木の形で表したもの）の考え方を学ぶ教材として繰り返し取り上げられています。

G検定のシラバスでは「人工知能をめぐる動向」の探索・推論の項目に位置づけられます。また、第1次AIブーム（最初のAI研究が盛り上がった時期）で場合分けによって解かれたトイ・プロブレム（ルールと目的があらかじめ明確に決まった、単純化された問題）の代表例としても紹介されます。

2. 試験対策ポイント

まず整理しておきたいのは、ハノイの塔のルールを正確に把握しているかという点です。一度に動かせる円盤は1枚だけであり、小さい円盤の上に大きい円盤を置くことはできません。この2つの制約だけで構成されたシンプルな取り決めですが、記述を微妙に変えた説明文は取り違えやすいところです。

最小手数の公式も重要な論点です。円盤の枚数を1枚増やすごとに手数はおよそ倍に近い勢いで増えていき、この急激な増え方は組合せ爆発（考えるべき組み合わせの数が指数関数的に増えてしまう現象）と結び付けて整理しておきたいところです。円盤の枚数に2を掛けるだけといった説明は誤りで、正しくは円盤の枚数と同じ回数だけ2を掛け合わせ、そこから1を引いた回数です。

ハノイの塔は、パズルの要素を探索木の要素に置き換えると、そのまま探索木として表現できます。何が何に対応するのかを並べると次のとおりです。

ハノイの塔の要素	探索木での対応
円盤の配置（1つの状態）	ノード（木構造の中の1つ1つの点）
1回の円盤の移動	枝（ノードとノードをつなぎ、状態の移り変わりを表す線）

この対応関係は、初期状態から目標状態に至る操作の並びを求めるプランニングの説明でも引用され、ロボットなどの行動計画を立てる技術の理解につながります。また、ハノイの塔はトイ・プロブレムの代表例の一つであり、迷路やチェスと合わせて見ておきたい具体例です。

3. 関連概念との比較・相違点

ハノイの塔は、何と比べるかによって浮かび上がる違いが変わります。主な比較対象を軸ごとに並べると次のように整理できます。

比較対象	違いの軸	ハノイの塔の位置づけ
トイ・プロブレム	位置づけ	分類の名称に対して、その中に含まれる個別の題材
探索木	抽象度	一般的な枠組みに対して、それを当てはめられる具体例
現実の複雑な問題	規模	枚数を決めればすべてが明確になる有限の問題

トイ・プロブレムとの最大の違いは、位置づけそのものです。トイ・プロブレムはルールと目的が明確な単純化された問題群という分類の名称であり、ハノイの塔はその中に含まれる個別の題材にあたります。迷路やチェスといった他のトイ・プロブレムと並べて、探索・推論の考え方を学ぶ具体例として扱われる点が特徴です。

探索木との違いは、扱う対象の抽象度にあります。探索木は状態と操作を木構造で表す一般的な枠組みであり、ハノイの塔は円盤の配置をノード、1回の移動を枝とみなすことで、その枠組みに具体的に当てはめられる題材です。円盤の枚数が増えるほど、たどるべき経路の数は急激に広がっていきます。

現実の複雑な問題との違いは、扱う規模にあります。ハノイの塔は円盤の枚数を決めればルールと状態のすべてが明確になる有限の問題であり、最小手数も先述の公式でそのまま計算できます。一方、現実の問題は考慮すべき条件がはるかに膨大で、同じ指数関数的な増え方であっても、扱いの難しさは比べものになりません。この規模の違いこそが、組合せ爆発という現象の本質です。

4. ビジネス・実務での活用シナリオ

アルゴリズム教育・研修の分野では、ハノイの塔がプログラミング研修や情報科学の授業で、再帰的思考（大きな問題を同じ形の小さな問題に分解して解く考え方）を学ぶ定番教材として使われています。円盤3枚から徐々に枚数を増やして手順の規則性を体感させる進め方が一般的です。

AI・アルゴリズム研究の分野では、状態空間（問題として起こりうるすべての状態の集まり）探索やプランニングのアルゴリズムを検証するベンチマーク題材として使われています。ルールと目的が明確なため、新しい探索手法が正しく解を求められているかを確認しやすいという利点があります。

ロボット行動計画のPoC（概念実証）では、初期状態から目標状態までの操作列を求めるプランニングの説明にハノイの塔が引用されます。単純な題材でプランニングの考え方を確認したうえで現実のタスクへ応用する橋渡しとして機能します。

5. 要点まとめ

• ハノイの塔は3本の杭と大きさの異なる円盤を使い、1回に1枚だけ動かし小さい円盤の上に大きい円盤を置けないというルールで完成を目指すパズルで、円盤n枚の最小手数は、2をn回掛けた値から1を引いた回数になります。
• 円盤の配置をノード、1回の移動を枝とみなすと探索木として表現でき、ロボットの行動計画を立てるプランニングの題材としても引用されます。
• トイ・プロブレムの代表例の一つであり、同じ指数関数的な増え方でも現実の複雑な問題とは扱いの難しさが異なります。

6. 確認問題