ハノイの塔
解説
ハノイの塔とは、3本の杭と、大きさの異なる複数の円盤からなる古典的な数学パズルであり、AI研究においては「トイ・プロブレム（おもちゃの問題）」の最も有名な例の一つです。
ルールとAIにおける意義
「1回に1枚しか動かせない」「小さい円盤の上に大きい円盤を置いてはいけない」という単純なルールですが、AI（探索アルゴリズム）の性能を測るためのモデルとして古くから利用されてきました。
この問題は、円盤の枚数を n とすると、最短でも 2n – 1 回の手順が必要になります。枚数が増えると必要な手数が指数関数的に爆発するため、「単純なルールでも、組み合わせ爆発が起きる」ことを学ぶための格好の教材となっています。
G検定対策
出題ポイント
- 分類：トイ・プロブレム（第1次AIブーム）。
- 活用：「状態空間探索」や「再帰的アルゴリズム（Recursion）」の理解度を試すベンチマークとして使われる。
- 関連：円盤が増えると計算量が爆発的に増える（組み合わせ爆発）。
よくあるひっかけ問題
- × ハノイの塔は、現実世界の複雑な物流問題を解決するために開発された
（解説）違います。あくまで数学的なパズルであり、現実の複雑さ（不確実性など）を含まない「おもちゃの問題」です。
