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

7.7

 深さ優先探索

■

223

A

I

//

訪問済みなら、別の状態を試す。

if (closed.contains(successor) != null) { continue; }

int depth = 1;

if (trans != null) { depth = trans.depth+1; }

//

解の経路を後で復元できるように、前の手を記録する。もし解が得られたら、

//

ここで終わる。そうでなく、まだ深さ限界の範囲内なら、オープン集合に追加する。

successor.storedData(new DepthTransition(move, n, depth));

if (successor.equals(goal)) {

return new Solution

(initial, successor);

}

if (depth < depthBound) { open.insert (successor); }

}

}

return new Solution (initial, goal, false); //

解はない

}

盤面状態は、同じ状態を再度訪問しないように貯えられている。アルゴリズムの

性能を高めるために、盤面状態に対して一意なキーを生成する効率的な関数がある

ものと仮定する。この関数が、

2

つの盤面状態が同じキーを生成するなら、それら

は等しい盤面であると判定できる。

7.7.4

 分析

d

を

深さ優先探索

の最大深さ限界として、

b

を探索木の分岐数と定義する。

アルゴ ...