アルゴリズムクイックリファレンス 第2版

7.7

 深さ優先探索

■

221

A

I

深さ優先探索

は、今後訪問するオープンな盤面状態をスタックに積んで管理する。

深さ優先探索

は、スタックから未訪問の盤面状態を取り出し、可能な手を用いて、

次の盤面状態集合を計算してスタックを拡張する。目標状態に到達したら、探索は

終了する。次の盤面状態のうち、クローズした（訪問済み）集合に既にあるものは捨

てられる。残りの未訪問盤面状態がスタックに積まれ、探索が続けられる。

図7-15は、

8

パズルの初期状態に対して深さ制限

9

の探索木の計算を示す。木の

他のところで深さ

9

まで探索した後、

8

手の（目標という印の）解が見つかったこと

に注意。全部で

50

の盤面状態が処理され、まだ

4

つが調べられていない（明るい灰

色で示す）。この場合、パズルは解けたが、最良（最短）の解を探し出しているかは

保証できない。

目標

図7-15　8 パズルの深さ優先探索木の例

7.7.1

 入出力

深さ優先探索

は、初期盤面状態から出発して目標状態を探索する。初期状態から

目標状態への経路を表現する一連の手を返す（または、既存の資源ではそのような

解が見つからなかったと宣言する）。