① 人工知能の基礎と動向 ／ 3. 探索・推論
ハノイの塔とは
ハノイの塔とは、3本の杭と大きさの異なる円盤を使うパズルで、再帰的な考え方や探索問題を説明する例題として広く使われます。G検定ではトイ・プロブレムの代表例として登場します。
この用語はG検定シラバスの「3. 探索・推論」に含まれます。 章全体の用語は用語解説①（全54語）にまとまっています。
一言でいうと
3本の杭と円盤を使うパズル。再帰や探索の考え方を説明する定番の例題です。
ルール
- 3本の杭と、大きさの異なる複数の円盤を使う
- 円盤は1枚ずつしか動かせない
- 小さな円盤の上に大きな円盤を置いてはいけない
- すべての円盤を別の杭へ、最小手数で移動させる
なぜ例題として使われるのか
ルールと状態が完全に定義でき、取りうる手をすべて列挙できるため、探索木としてきれいに表現できます。
一方でこの明確さは、現実問題との距離でもあります。ハノイの塔が解けても現実の課題は解けないことから、トイ・プロブレムの代表例として扱われます。
最小手数
円盤がn枚のとき、必要な最小手数は2のn乗から1を引いた数になります。3枚なら7手、10枚なら1,023手です。
枚数が増えるだけで手数が急激に増えるこの性質は、ブルートフォースで問題になる組合せ爆発とよく似ています。
🎯 G検定での押さえどころ
- トイ・プロブレムの代表例として押さえる
- 「小さい円盤の上に大きい円盤を置けない」というルール
- 再帰的な考え方・探索の例題
⚠️ よくある誤りの選択肢
- 「ハノイの塔では大きい円盤の上に小さい円盤を置いてはならない」→ 誤り。制限は逆です
- 「ハノイの塔は現実問題への応用例として挙げられる」→ 誤り。トイ・プロブレムの代表例です
この用語を覚えたら
チェックは章ページと「試験内容解説」TOPの進捗にも反映されます
関連する用語
ご利用にあたって 本ページの内容は、JDLAが公開しているG検定シラバス2024や公式テキストなど、一般に公開されている情報をもとに独自に整理・解説したものです。実際の試験の出題内容を示すものではなく、また合格を保証するものでもありません。制度・法令・試験要項は変更されることがあるため、最新の情報は必ずJDLA公式サイトでご確認ください。