深さ制限探索

深さ制限探索（ふかさせいげんたんさく、英: depth-limited search）とは、グラフの頂点を探索するアルゴリズムの一種である。深さ優先探索からの派生であり、反復深化深さ優先探索アルゴリズムなどで使う。

概要

通常の深さ優先探索のように、深さ制限探索も一様な探索を行う。深さ優先探索と異なるのは、探索する深さを制限する点である。制限を越えて探索木を深くしていくことがないため、無限の経路に捉われたり、環状の経路に捉われたりすることがない。従って、深さ制限探索は制限された深さの範囲内で、あらゆるグラフの最適解を求めることができる。

アルゴリズム（木構造の場合）

探索の始点となるノードを決定し、探索すべき深さの上限を決定する。
現在のノードが目標とする状態かどうか調べる。
- 目標状態の場合: 探索成功。終了する。
現在のノードが探索すべき深さの範囲内にあるか調べる。
- 範囲内の場合: ノードを展開し、深さ制限探索を再帰的に呼び出し、ステップ2に戻る。
探索失敗

木構造ではなく一般のグラフの場合、訪問済みのノードかどうかを管理すべき。ただし、深さ優先探索とは異なり、閉路があっても、無限ループに陥ることはない。また、訪問済みのノードを管理するとメモリ不足に陥る場合は、諦めるか、量を制限するかなどをする。

擬似コード（木構造の場合）

EXPAND(node): ノード展開関数：探索候補の集合を返す。
IS_GOAL(node): ノード探索終了判定関数：ゴールに到達したかどうか。

function DLS(node, depth)
    if (IS_GOAL(node)) then
        return node
    if (depth > 0) then
        for each (child in EXPAND(node))
            found = DLS(child, depth - 1)
            if (found != NULL) then
                return found
    return NULL

特性

空間計算量

深さ制限探索は深さ優先探索の一種であるため、空間計算量は通常の深さ優先探索と同じである。

時間計算量

深さ制限探索は深さ優先探索の一種であるため、時間計算量は通常の深さ優先探索と同じで O( $\vert V\vert +\vert E\vert$ ) である。ここで、 $\vert V\vert$ は探索するグラフの頂点数、 $\vert E\vert$ は枝の数である。ただし、深さ制限探索はグラフ全体を探索するのではなく、制限された範囲内だけを探索する。

完全性

深さ制限探索は無限に長い経路を探索することはできないし、環状の経路（閉路）にとらわれることもない。そのため、制限した深さを越えたところにある解を見つけることができないという不完全性がある。ただし、制限をうまく設定すれば、完全に解を求められる。

最適性

深さ制限探索は最適ではない。深さ優先探索の問題点は依然として残っており、見つけた解が別の経路にある解よりも悪い解という可能性がある。

参考文献

Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2