反復深化深さ優先探索

探索 > 深さ優先探索 > 反復深化深さ優先探索

反復深化深さ優先探索（はんぷくしんかふかさゆうせんたんさく、英語: iterative deepening depth-first search、IDDFS）とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば（刈り込みがない場合）、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。

IDDFSを知識あり探索にしたものがIDA*（英語版）である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。

概要

IDDFSは深さ優先探索のメモリ効率と幅優先探索の完全性（分岐が有限の場合）を併せ持っている。ノードの深さに対応して経路コストが減少しない場合、これが最適とされている。

IDDFSの空間計算量は $O(bd)$ であり、 $b$ は分岐係数（英語版）、 $d$ は深さである。木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。

ゲーム木でIDDFSを使う場合、アルファ・ベータ枝刈りなどのヒューリスティックが反復によって改善されていき、最も深い探索でのスコアの推定値がより正確になるという利点がある。また、探索順序を改善することができるため、探索をより高速に行えるという利点もある（前の反復で最善とされた手を次の反復で最初に調べることでアルファ・ベータ法の効率が良くなる）。

また、このアルゴリズムは応答性がよいという利点もある。初めの反復では $d$ が小さいので高速に完了する。このためこのアルゴリズムは素早く大まかな結果を示しつつ、 $d$ を深くすることでそれをさらに洗練させていくことができる。チェスプログラムのような対話型プログラムでは、任意の時点で探索を打ち切って、その時点で最善と思われる手を示すことができるという利点がある。これは通常の深さ優先探索では不可能である。

IDDFSの時間計算量は、平衡のとれた木では深さ優先探索と同じ $O(b^{d})$ である。

反復深化探索では、底辺レベルのノードは1回展開され、その1つ上のレベルのノードは2回、根ノードは $d+1$ 回展開される。したがって総展開回数は次のようになる。

$(d+1)1+(d)b+(d-1)b^{2}+...+3b^{d-2}+2b^{d-1}+b^{d}$

例えば $b=10$ で $d=5$ の場合、具体的には次のようになる。

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

これは、幅優先探索や深さ制限探索を行ったときのノード展開回数に対して11%の増加にしかならない。分岐係数が大きくなればオーバーヘッドも小さくなるが、分岐係数が2だったとしても、幅優先探索の2倍にしかならない。そのため、時間計算量は $O(b^{d})$ で、空間計算量は $O(bd)$ となる。一般に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も好ましい方法とされている^[1]。

深さ優先探索との比較

メモリに載りきらないような大規模な木を探索する場合、深さ優先探索は探索木のパスの長さが長くなりすぎて探索が終わらないという問題を抱えている。「訪れたノードを記憶する」という単純な方法は、十分なメモリ量がない場合通用しなくなるのである。また、探索対象が木ではなく一般の有向グラフである場合(特に、ループを含む場合)にも同じ問題が起こる。これは、木の深さを段階的に増やして探索する反復深化深さ優先探索で解決することができる。

下記の図を用いた場合、

グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することにより再訪しないとするならば、Aからスタートした深さ優先探索はA, B, D, F, E, C, Gという順番で訪れる。

ここで以前訪れたノードを記憶していない場合、A, B, D, F, E, A, B, D, F, Eと、A, B, D, F, Eのループに捕まって永遠にCやGに到達することはできない。

反復深化はこのループを回避し、上記のように左から右に探索が進むとすると、下記の深さにおいて下記のノードに到達する。

0: A
1: A (repeated), B, C, E

(反復深化はCをみつけていることに注意。通常の深さ優先探索では見つからない。)

2: A, B, D, F, C, G, E, F

(以前Cを見つけていることに注意。Fを別のパスでみつけていることとFでループを見つけていることにも注意。)

3: A, B, D, F, E, C, G, E, F, B

このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。

擬似コード

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

DLS は深さ制限探索。

function IDDFS(node)
    for (depth = 0; ; depth++)
        found = DLS(node, depth)
        if (found != NULL) then
            return found

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

脚注

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

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

[1]

概要

深さ優先探索との比較

擬似コード

関連アルゴリズム

脚注