左の柱に下から大きい順に積まれた3枚の円盤を、右の柱へすべて移すハノイの塔を探索問題として解く。円盤の置き方を状態（ノード）、円盤を1枚動かす操作を枝とする探索木を作り、初期状態から幅優先探索を行う。円盤は1回に1枚だけ動かせ、小さい円盤の上に大きい円盤は置けない。最初に見つかるゴールの深さ（手数）として、最も適切なものを1つ選べ。
正解と解説を見る
解説
正解 B
この問題の論点：ハノイの塔の最短手数と探索
ポイント
幅優先探索は浅い順に調べるため、最初に見つかるゴールは最短手数の解です。円盤3枚のハノイの塔では7手になります。
選択肢ごとの解説
- A
不適切
円盤の枚数と同じ3手では移せません。いちばん大きい円盤を動かす前に、その上の2枚をいったん中央の柱へ移す必要があり、そこだけで3手かかるためです。
- B
適切 正解
上の2枚を中央へ移す（3手）、最大の円盤を右へ移す（1手）、2枚を右へ重ねる（3手）で、3＋1＋3＝7手です。幅優先探索は浅い順に調べるため、この最短手数の深さで最初にゴールに達します。
- C
不適切
8は2の3乗です。n枚の最短手数は、n−1枚を2回移す手数に最大の円盤の1手を足したもので、2のn乗から1を引いた値になります。3枚では8−1＝7手です。
- D
不適切
27は3の3乗で、各円盤を3本のどの柱に置くかで決まる状態の総数です。探索空間の大きさを表す数であり、ゴールまでの手数ではありません。
試験での狙われ方
ハノイの塔は探索木の代表例として、状態と操作の対応や、探索方法と最短手数の関係を問う形で扱われます。
参考
- G検定 試験出題範囲（シラバス2024）第1.4版 （技術分野 項目3 探索・推論）