深さ制限探索

深さ制限探索は、グラフの頂点を探索するアルゴリズムの一種で、深さ優先探索から派生したものです。特に、反復深化深さ優先探索アルゴリズムなどで活用されます。

概要

深さ制限探索は、深さ優先探索と同様に一様な探索を行います。しかし、深さ優先探索とは異なり、探索する深さに制限を設ける点が特徴です。この制限により、無限に続く経路や環状の経路に陥るのを防ぎます。そのため、深さ制限探索は、設定された深さの範囲内であれば、あらゆるグラフの最適解を見つけることができます。

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

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

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

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

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(|V| + |E|)となります。ここで、|V|は探索するグラフの頂点数、|E|は枝の数を表します。ただし、深さ制限探索はグラフ全体ではなく、制限された範囲内のみを探索します。

完全性

深さ制限探索は、無限に長い経路を探索したり、環状の経路に捉われたりすることはありません。しかし、制限された深さよりも深い場所にある解は見つけることができません。したがって、深さ制限探索は完全ではありません。ただし、制限を適切に設定すれば、完全な解を求めることも可能です。

最適性

深さ制限探索は、必ずしも最適解を見つけるわけではありません。深さ優先探索の問題点を受け継いでおり、最初に見つけた解が、他の経路にあるより良い解よりも劣る可能性があります。

まとめ

深さ制限探索は、深さ優先探索の欠点を補うために導入されたアルゴリズムです。深さ制限を設けることで、無限探索を防ぎ、効率的な探索を可能にします。ただし、探索範囲が限定されるため、解の完全性や最適性が保証されない点には注意が必要です。適切な深さ制限の設定が、アルゴリズムの有効性を左右します。

参考文献

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

もう一度検索