反復深化深さ優先探索

反復深化深さ優先探索

クラス	検索アルゴリズム
データ構造	ツリー、グラフ
最悪の場合の パフォーマンス	${\displaystyle O(b^{d})}$、ここで は分岐係数、 は最も浅い解の深さである。${\displaystyle b}$${\displaystyle d}$
最悪の場合の 空間複雑度	${\displaystyle O(d)}$[1]
最適	はい（重み付けされていないグラフの場合）

コンピュータサイエンスにおいて、反復深化探索、より具体的には反復深化深さ優先探索^[1] (IDS または IDDFS) は、状態空間/グラフ探索戦略であり、深さ制限のある深さ優先探索を、目標が見つかるまで深さ制限を増やしながら繰り返し実行します。IDDFS は最適であり、最も浅い目標を見つけます。^[2]深さのノードを訪問する前に、検索ツリーの深さまですべてのノードを訪問するため、ノードが最初に訪問される累積的な順序は、実質的に幅優先探索と同じです。ただし、IDDFS はメモリをはるかに少なく使用します。^[1]${\displaystyle d}$${\displaystyle d+1}$

次の疑似コードは、有向グラフの再帰的な深さ制限 DFS (DLS と呼ばれる) に基づいて実装された IDDFS を示しています。この IDDFS の実装では、すでに訪問されたノードは考慮されません。

関数IDDFS(root)は
    0から∞までの深さに対して実行します
        見つかった、残り ← DLS(ルート、深さ)
        見つかった≠ null の場合は見つかっ
            た
        ものを返し、残っていない場合はnullを返します。
             

関数DLS(node, depth)は、
     depth = 0の場合、
        ノードがゴールであれば( node, true )
        を返し、そうでない場合
            は( null , true )    を返します(見つかりませんが、子がある可能性があります)
            

    そうでない場合、深さ > 0の場合、 
        any_remaining ← false
        ノードの子ごとに実行します。
            見つかった、残り ← DLS(子、深さ−1)
            見つかった場合≠ nullの場合
                は(found, true )   
            を返し、残っている場合はany_remaining 
                ← true を返します    (深さで少なくとも 1 つのノードが見つかった場合は、IDDFS を深めます) ( null、 any_remaining)
を返します
        

DLSによって目標ノードが見つかった場合、IDDFS は深く調べずにそれを返します。それ以外の場合、その深さのレベルで少なくとも 1 つのノードが存在すると、remainingフラグによってIDDFS が続行されます。

2 タプルは、ツリーの深さと目標のメンバーシップが事前に不明な場合に、IDDFS に深化を続行するか停止するかを通知するための戻り値として役立ちます。別の解決策としては、代わりにセンチネル値を使用して、見つからない結果や残りのレベルの結果 を表すことができます。

IDDFSは、深さ優先探索の空間効率を利用して、幅優先探索の完全性（分岐係数が有限の場合）を実現します。解が存在する場合、最も少ない弧を持つ解のパスを見つけます。 ^[2]

反復深化は状態を複数回訪問するため、無駄に思えるかもしれない。しかし、IDDFSが探索木を深さまで探索する場合、全体の労力のほとんどは深さの状態の探索に費やされる。深さの状態の数に比べて、この深さより上の状態を繰り返し訪問するコストは常に小さい。^[3]${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$

ゲームツリー探索におけるIDDFSの主な利点は、初期の探索によってキラーヒューリスティックやアルファベータプルーニングなどの一般的に使用されるヒューリスティックが改善される傾向があるため、最終的な深さの探索でさまざまなノードのスコアをより正確に推定でき、より良い順序で探索が行われるため探索がより速く完了することです。たとえば、アルファベータプルーニングは、最初に最善の動きを検索する場合に最も効率的です。^[3]

2 つ目の利点は、アルゴリズムの応答性です。初期の反復では に小さな値を使用するため、非常に速く実行されます。これにより、アルゴリズムは結果の早期の兆候をほぼ即座に提供し、 が増加するにつれて改良を加えることができます。チェスをプレイするプログラムなどの対話型設定で使用する場合、この機能により、プログラムは、それまでに完了した検索で見つかった現在の最善の動きを使用していつでもプレイできます。これは、各ステップで行われる作業は再帰的ですが、検索の各深さが共再帰的にソリューションのより良い近似値を生成すると表現できます。これは、中間結果を生成しない従来の深さ優先検索では不可能です。 ${\displaystyle d}$${\displaystyle d}$

（バランスの取れた）木におけるIDDFSの時間計算量は、幅優先探索と同じ、つまり[1] : 5になります。ここ^で、は分岐係数、は目標の深さです。 ${\displaystyle O(b^{d})}$${\displaystyle b}$${\displaystyle d}$

反復深化探索では、深さのノードは1回拡張され、深さのノードは2回拡張され、探索木のルートまで拡張されます。^{[1] : 5}したがって、反復深化探索における拡張の総数は ${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d+1}$

${\displaystyle b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}}$

ここで は深さ での展開の数、は深さ での展開の数、などです。因数分解すると、 ${\displaystyle b^{d}}$${\displaystyle d}$${\displaystyle 2b^{d-1}}$${\displaystyle d-1}$${\displaystyle b^{d}}$

${\displaystyle b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})}$

さて、 とします。すると、 ${\displaystyle x={\frac {1}{b}}=b^{-1}}$

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})}$

これは無限級数より小さい

${\displaystyle b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)}$

これは次のように 収束する

${\displaystyle b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}}$、 のために${\displaystyle abs(x)<1}$

つまり、

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}}$、 のために${\displaystyle abs(x)<1}$

またはは（深さ）に依存しない定数であるため、 （つまり、分岐係数が1より大きい場合）深さ優先反復深化探索の実行時間は です。 ${\displaystyle (1-x)^{-2}}$${\displaystyle \left(1-{\frac {1}{b}}\right)^{-2}}$${\displaystyle d}$${\displaystyle b>1}$${\displaystyle O(b^{d})}$

であり、その数は ${\displaystyle b=10}$${\displaystyle d=5}$

${\displaystyle \sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456}$

全体として、深さから深さまでの反復深化探索は、の場合には、深さまでの幅優先探索または深さ制限探索の単一探索よりも約多くのノードしか拡張されません。^[4]${\displaystyle 1}$${\displaystyle d}$${\displaystyle 11\%}$${\displaystyle d}$${\displaystyle b=10}$

分岐係数が高くなるほど、繰り返し拡張された状態のオーバーヘッドは低くなりますが、^{[1] : 6}分岐係数が2の場合でも、反復深化探索は完全な幅優先探索の約2倍の時間がかかります。これは、反復深化の時間計算量が依然としてであることを意味します。 ${\displaystyle O(b^{d})}$

IDDFSの空間計算量は[1]:5であり、ここ^ではゴールの深さである。 ${\displaystyle O(d)}$${\displaystyle d}$

IDDFS は、どの時点でも深さ優先探索を行うため、展開しているツリーのブランチを表すノードのスタックを保存するだけで済みます。最適な長さのソリューションが見つかるため、このスタックの最大深さは であり、したがって最大スペース量は です。 ${\displaystyle d}$${\displaystyle O(d)}$

一般的に、反復深化は、探索空間が大きく、解の深さが不明な場合に好まれる探索方法です。^[3]

次のグラフの場合:

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: エー
• 1: A、B、C、E

(反復深化により、従来の深さ優先探索では検出されなかった C が検出されました。)

• 2: A、B、D、F、C、G、E、F

(C はまだ認識されていますが、後から来たものです。また、別のパスを介して E を認識し、F に 2 回ループバックします。)

• 3: A、B、D、F、E、C、G、E、F、B

このグラフでは、深さが増すにつれて、アルゴリズムが諦めて別の分岐を試す前に、2 つのサイクル「ABFE」と「AEFB」が長くなるだけです。

反復深化に似た検索戦略として、反復長化検索があります。これは、深さ制限ではなく、経路コスト制限の増加で機能します。経路コストの増加順にノードを拡張するため、最初に遭遇する目標は経路コストが最も安い目標です。ただし、反復長化には大きなオーバーヘッドが発生するため、反復深化よりも有用性が低くなります。^[3]

反復深化 A*は、 A* アルゴリズムで計算される値と同様の「 f 」値に基づいて反復深化を実行するベストファースト検索です。

IDDFS には双方向の対応物があり、^{[1] : 6}は 2 つの検索を交互に実行します。1 つはソース ノードから開始して有向アークに沿って移動する検索、もう 1 つはターゲット ノードから開始して有向アークに沿って反対方向 (アークの先頭ノードからアークの末尾ノードへ) に進む検索です。検索プロセスでは、まずソース ノードとターゲット ノードが同じかどうかを確認し、同じ場合は単一のソース/ターゲット ノードで構成される単純なパスを返します。そうでない場合は、順方向検索プロセスでソース ノードの子ノード (セット) を展開し、逆方向検索プロセスでターゲット ノードの親ノード (セット ) を展開して、とが交差するかどうかを確認します。交差する場合は、最短パスが見つかります。そうでない場合は、検索の深さが増分され、同じ計算が行われます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

このアルゴリズムの制限の 1 つは、奇数の弧で構成される最短経路が検出されないことです。最短経路 があるとします。深さが弧に沿って 2 ホップに達すると、前方検索は から に進み、後方検索はからに進みます。図で表すと、検索境界は互いを通過し、代わりに偶数の弧で構成される最適ではない経路が返されます。これは、以下の図に示されています。 ${\displaystyle \langle s,u,v,t\rangle .}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$

空間の複雑さに関しては、アルゴリズムは、2 つの検索プロセスが交わる中間ノードの存在を検出するために、前方検索プロセスで最も深いノードを色付けします。

双方向 IDDFS を適用する際のさらなる難しさは、ソース ノードとターゲット ノードが異なる強く接続されたコンポーネント ( など) 内にある場合、から出て に入るアークがなければ、検索が終了しないという点です。 ${\displaystyle s\in S,t\in T}$${\displaystyle S}$${\displaystyle T}$

双方向IDDFSの実行時間は次のように表される。

そして空間計算量は次のように与えられる。

ここで、は最短経路上のノードの数です。反復深化深さ優先探索の実行時間計算量は なので、速度向上はおよそ ${\displaystyle n}$${\displaystyle s,t}$${\displaystyle \sum _{k=0}^{n}b^{k}}$

関数Build-Path(s, μ, B) は
    π ← Find-Shortest-Path(s, μ)です(リレーノードへのパスを再帰的に計算します)
    πから最後のノードを削除する
    π Bを返す（後方検索スタックを追加する）${\displaystyle \circ }$

関数Depth-Limited-Search-Forward(u, Δ, F)は、
     Δ = 0の場合、 
        F ← F {u} （ノードをマーク） uの子ごとに戻り、${\displaystyle \cup }$
        
    
        深さ制限探索前方(子, Δ − 1, F)

関数Depth-Limited-Search-Backward(u, Δ, B, F)は
    Bの前にuを追加する
    Δ = 0の場合、
         u がF  内にある場合はuを返します(マークされたノードに到達したので、それをリレーノードとして使用します)
            
        Bのヘッドノードを削除する
        
    uの親ごとにnullを返す
        μ ← 深さ制限後方探索(親, Δ − 1, B, F)
        μがnullの場合はμを返す${\displaystyle \neq }$  
            
    Bのヘッドノードを削除する
    nullを返す

関数Find-Shortest-Path(s, t)は、
    s = tの場合は
       <s>を返す。
   F, B, Δ ← ∅, ∅, 0
   永遠に
       深さ制限前方探索(s, Δ, F)
       δ = Δ, Δ + 1ごとに行う
           μ ← 深さ制限後方探索(t, δ, B, F)
           μがnullの場合、 Build-Path(s, μ, B)を返します（リレーノードが見つかりました）${\displaystyle \neq }$ 
               
       F, Δ ← ∅, Δ + 1