ハノイの塔と探索

問題

ハノイの塔に関する次の記述のうち、誤りを1つ選べ。

ハノイの塔は、「3本の杭と、大きさの異なる複数の円盤」を用い、ルールに従って円盤を別の杭にすべて移動させる古典的なパズルです。

AIの分野では、現実の複雑な問題を単純化した「トイ・プロブレム（おもちゃの問題）」の代表例として扱われます。

状態空間の探索や再帰的アルゴリズムの動作を学ぶための格好の題材ですが、円盤の数が増えると計算量が指数関数的に爆発（組み合わせ爆発）を起こすため、探索の難しさを理解する上でも重要な教材です。

1. ハノイの塔は古典的なトイ・プロブレムである。

正しい：ハノイの塔は、迷路やチェスなどと並び、AIの初期研究で盛んに取り組まれた「トイ・プロブレム（単純化されたパズル・ゲーム）」の代表例です。

2. ハノイの塔は探索問題として扱うことができる。

正しい：現在の円盤の配置を「状態」、円盤を移動させることを「状態遷移（行動）」とみなすことで、初期状態から目標状態に至る経路を見つける「探索問題」として定式化して解くことができます。

3. ハノイの塔は現実世界の複雑な問題を直接解くために設計された。

誤り：ハノイの塔は、アルゴリズムや探索手法の有効性を検証するための教育用・研究用の単純化された問題（トイ・プロブレム）であり、現実世界の複雑な課題を直接解決する目的で設計されたものではありません。

4. ハノイの塔は状態空間が指数関数的に増加するため、探索が難しくなる。

正しい：円盤の数が $n$ 枚のとき、最短手数は $2^n - 1$ となり、状態空間の規模が指数関数的に増大するため、少し数が増えただけで探索に膨大な計算時間が必要となります（組み合わせ爆発）。

← 前の問題次の問題 →

📚 より詳細を学びたい方へ