1. 序章


このチュートリアルでは、深さ優先探索と反復深化の2つの探索アルゴリズムについて説明します。 どちらのアルゴリズムもグラフを検索し、多数のアプリケーションがあります。 ただし、それらの間には大きな違いがあります。


2. グラフ検索








一般に、ノードのセットが無限であり、それらを接続するエッジのセットが含まれるグラフがあります。 私たちの目標は、開始ノードとターゲットノードの間の最短経路を見つけることです。 


問題のいくつかのバリエーションが可能です。 この記事では、エッジが方向付けられており、重みがないことを前提としているため、パスの長さは正確に含まれるエッジの数です。重みのある代替案では、他のアルゴリズムを使用します。 有向エッジを使用するため、ノードのネイバーはその子であり、それらの関係の非対称性を強調します。


グラフは暗黙的であると想定します。これは、入力でノードを受け取り、その子を返す関数があることを意味します。 明示的なグラフには些細な暗黙の定式化があるため、この方法で一般性を失うことはありません。 同じことがターゲットノードにも当てはまります。ノードがターゲットとして適格かどうかをテストできる関数があると想定します。 このようにして、グラフに複数のターゲットノードがある場合をカバーします。


2.1. 例


作業例は、正の整数に関するKnuthの予想に基づいています。 Knuthは、1964年に、平方根、フロア、および階乗演算の有限シーケンスを4番から開始することにより、すべての正の整数を取得できると推測しました。 例えば：


 (1)    


例をわかりやすくするために、フローリングの代わりに最も近い整数（）への丸めを使用します。


対応するグラフでは、ノードは正の実数です。 開始ノードは4番です。 ノード間に有向エッジがあり、、、、またはの場合。 任意の数が与えられた場合、4から始まるそれに到達する操作の最短シーケンスを見つけたいと思います。 そのシーケンスは、4と暗黙のグラフの間の最短経路に対応します。 次に、ターゲットテスト機能は次のとおりです。


      


非整数のみを丸める必要があり、平方根のみがそれらを生成できることに注意してください。 また、階乗は整数にのみ適用する必要があります。 それを念頭に置いて、検索グラフのごく一部を見てみましょう。


2. 深さ優先探索


深さ優先探索（DFS）は、開始ノードで検索を開始します。 最初に、それがターゲットであるかどうかをテストします。 そうでない場合、DFSは次のステップとして子を識別してテストします。 このステップは拡張と呼ばれます。 DFSがその子を識別した場合、ノードを拡張（または探索）と呼びます。 私たちが呼ぶ子供たちが訪れました。 テストに合格した子がいない場合、DFSは最後にアクセスしたが拡張されていない子を選択し、手順を繰り返します。


ターゲットが見つかるか、現在のノードに子がないため、ノードにバックトラック する必要があるまで、グラフ内でどんどん深くなります。バックトラック後、DFSはとの2番目の子を展開します。ターゲットノードに到達するか、すべてのノードを探索するまで検索を続行します。


2.1. 例


DFSがこの例を数字でどのように処理するかを見てみましょう。


DFSが、ルートが開始ノードであるツリーを作成していることがわかります。 検索は第3レベルを超えて続行され、検索が停止するまでツリーは指数関数的に成長します。


2.2. アルゴリズム


再帰の有無にかかわらずDFSを実装できます。 ここでは、再帰バージョンを使用します。




このバージョンのDFSは、グラフが（有限の）ツリーである場合に終了するため、ツリー検索DFS（TSDFS）と呼ばれます。 検索グラフがツリーでない場合、TSDFSはループでスタックする可能性があります。 無限ループを回避するために、DFSは展開したノードを追跡する必要があります。 そうすれば、ノードを2回以上探索することがないため、ループに陥ることがありません。 そのバージョンのDFSは、ツリーだけでなく一般的なグラフを処理できるため、グラフ検索DFS（GSDFS）と呼ばれます。


3. 反復深化


DFSには2つの欠点があります。


    

  • 最適なパスを見逃す可能性があります。 ノードの子を返す順序によっては、DFSは必要以上に多くのノードを拡張する場合があります。
    • 



    

  • また、DFSは決して終わらないかもしれません！ アルゴリズムのグラフ検索バージョンを使用しても、ターゲットノードにつながることができないノードの拡張でスタックする可能性があります。
    • 



反復深化（ID）は、両方の問題を解決します。 深度が制限されたDFSに依存しています。


3.1. 深さ制限DFS


深さ制限DFS（DLDFS）は、DFSと同じように実行されますが、追加の停止基準があります。 つまり、開始ノードまでの距離、つまり検索ツリーでの深さが最大であるノードのみを探索します。 有限の場合、DLDFSは終了します。 事前に適切な値を選択するのは私たちの責任です。


を設定すると、ここで、は開始点に最も近いターゲットノードの深さであり、DLDFSは最短パスを見つけます。 なんで？ 深さが最大であるすべてのノードを探索し、深さが。よりも小さいターゲットノードがないためです。 ただし、の場合、DLDFSはそれに到達できません。 さらに、の場合、DLDFSはターゲットノードへの次善のパスを見つける可能性があります。 ただし、開始頂点から到達可能なターゲットノードがない場合、制限深度に関係なく、DLDFSは常に失敗します。


したがって、DLDFSを終了する方法は3つあります。


    

  • パスを見つけます（最短または次善）
    • 

  • 限界深度が浅すぎるため、ターゲットノードへのパスを見つけることができません
    • 

  • パスがないため、パスが見つかりません
    • 



3.2. 擬似コード


DLDFSの擬似コードは、DFSの擬似コードに似ています。




同じノードを複数回拡張することを心配する必要はありません。 深度制限により、すべてのパスの探索が最終的に停止します。 たとえば、を使用すると、DLDFSは第3レベルの直後に停止します。


3.3. 深化


深化は、DLDFSとDFSの問題を整理します。  DLDFSがターゲットノードを見つけるまで、深度制限として増分値を試すという考え方です。制限深度を増分するので、DLDFSが最初に検出するパスが、で終わるすべてのパスの中で最短であることがわかります。ターゲットノード：そうでない場合、DLDFSはより浅い深さで別のパスを見つけたでしょう。


これは反復深化の擬似コードです。




3.4. 例


番号1を検索するとします。 IDはで始まり、開始ノードのみを検査します。 次に、検索をインクリメントして再開し、最初のレベルの後で停止します。 最後に、を使用すると、IDは番号1を検索します。


深化しないと、DFSは最短経路を見逃したり、終わらない可能性があります。


3.5. 幅優先探索との比較


幅優先探索（BFS）は、一度に1レベルずつノードを探索します。 最初に、開始ノードの子を展開します。 それらすべてを処理する場合にのみ、BFSは子を拡張します。 IDは、深度のすべてのノードを展開した後にのみ、深度のノードを探索するという意味で類似しています。 ただし、違いは、IDが段階的な深さでノードを連続して処理するのに対し、BFSはレベルごとに検索を実行することです。 また、BFSは各ノードに1回アクセスしますが、IDはDLDFSを再起動するため、一部のノードに複数回アクセスします。


3.6. DFSをランダム化できませんでしたか？


もっと簡単な解決策があると思うかもしれません。 深くする代わりに、関数がノードを返す順序をランダム化できませんでしたか？ 答えは、最悪のシナリオと無限ループの可能性を低くしたとしても、それらを除外することはできないということです。 DFSが永久に実行されるか、次善のパスを返す可能性はまだわずかです。


4. 比較


DFSとIDを比較します。


    

  • 完全
    • 

  • 最適性
    • 

  • 時間計算量
    • 

  • スペースの複雑さ
    • 



完全性とは、手元のアルゴリズムがターゲットノードへのパスまたはそのようなノードに到達できなかったというメッセージのいずれかを返すという保証の存在を指します。 最適性とは、アルゴリズムがターゲットノードへのパスだけでなく、ターゲットノードへの最短パスを見つけることを意味します。


複雑さの分析に関しては、最初に表記法を設定しましょう。 開始ノードからターゲットノードまでの最短経路の長さ（検索ツリーでのノードの深さに対応）、グラフ内のノードの子の最大数、およびグラフ内の任意の2つのノード間の最長パス。


4.1. 完全性と最適性


 DFSは完全ではありません。ツリー検索バージョンはループでスタックする可能性がありますが、グラフ検索バリアントは無限のグラフで永久に実行される可能性があります。 一方、 IDは、無限の数の子を持つノードがない場合は常に完全です。 これが、より深い深度に少なくとも1つのノードがあり、後続ノードにターゲットノードがない場合、IDはノードの子を永久に拡張します。


最適性に関しては、 IDはターゲットノードへの最短経路を検出するか、完全性条件が成立する場合は開始頂点からターゲットノードに到達できないと結論付けます。 対照的に、 TSDFSとGSDFSの両方が、次善のパスを見つける可能性があります。ノードの子を返す順序によって、見つかったパスが最適かどうかが決まります。


4.2. 時間計算量


最悪の場合、GSDFSは各ノードを1回、各エッジを2回処理することにより、グラフ全体を探索します。したがって、その複雑さはです。ここで、はノードの数、はのエッジの数です。グラフ。 ノードを複数回拡張できるため、TSDFSの複雑さはグラフのサイズに制限されません。 代わりに、TSDFSはleafsを使用して検索ツリーを生成できます。 したがって、その複雑さは次のとおりです。


 (2)    


これは、グラフのサイズの上限としても機能します。 これは、私たちが知らないが知っている、または推測できる場合のGSDFSの複雑さの上限でもあります。


IDの複雑さは次のとおりです。 アルゴリズムは、開始ノード時間、その子時間などを調査します。 検索ツリーの深さでノードを1回だけ探索し、最短パスが深さであるため、他のノードにはアクセスしません。 開始ノードの子、深さ2のノードなどがあります。 したがって、IDは最大でこの数のノードを探索します：


 (3)    


したがって、その時間計算量はです。 以来、IDはこの基準でもDFSを上回っていると結論付けます。


4.3. 反復深化が遅くならないのはなぜですか？


DFSと比較してIDの複雑さが低いことは、やや直感に反する可能性があります。 結局のところ、GSDFSは各ノードを1回拡張し、ループを回避するために現在のパスを記憶するようにTSDFSを変更できますが、各ノードのIDは深度ですべてのノードを再訪します。


IDは桁違いに多くの作業を行うように見えるかもしれませんが、そうではありません。 すべてのノードにほぼ同じ数の子がある場合、ほとんどのノードは、開始ノードをルートとする検索ツリーの最下位レベルに属します。 したがって、ツリーの上位レベルにあるノードは、すべてのノードの比較的小さなシェアを占めるため、それらを数回再訪しても、オーバーヘッドはそれほど大きくなりません。たとえば、すべてのノードに5がある場合子供たちの場合、探索木の葉は木の約80% ofを占めます。 最後から2番目のレベルがさらに16％を占めます。 したがって、ツリーが2回以上処理されるのは4% ofだけです。


4.4. スペースの複雑さ


 GSDFSは、拡張するすべてのノードを記憶し、最悪のシナリオでグラフ全体を探索するため、最悪の場合のスペースの複雑さがあります。 対照的に、TSDFSは、現在のパスに沿ったノードの訪問されたが拡張されていない子のみを追跡する必要があります。 つまり、パスの長さの上限であり、子を超えるノードがないため、スペースの複雑さはです。


 IDは深度制限ツリー検索DFSを使用します。したがって、深度制限のあるDLDFSにはスペースの複雑さがあり、スペースの複雑さはです。


4.5. 概要


したがって、DFSがない場合でも、IDは完全であり、最短パスが存在する場合はそれを返し、時間計算量が高く、必要なメモリが少なくなります。




5. 結論


この記事では、深さ優先探索と反復深化について説明しました。後者の方が空間と時間の複雑さが低い理由を説明しました。 また、なぜそれが完全であり、最短経路が存在する場合はそれを見つけることが保証されているのかを示しました。 ただし、検索グラフのエッジには重みがないと仮定しました。 仮定が成り立たない場合は、他のアルゴリズムを使用する必要があります。