1. 序章


このチュートリアルでは、深さ優先探索（DFS）と幅優先探索（BFS）について説明します。 次に、それらを比較し、どのシナリオで一方を他方の代わりに使用する必要があるかについて説明します。


2. 探す








探索問題は、グラフ内の開始ノードと目標ノードの間の最適なパスを見つけることがタスクである問題です。探索問題にはいくつかのバリエーションがあります。グラフは有向または無向、加重、または重み付けされておらず、複数のゴールノードが存在する可能性があります。


DFSとBFSは重み付けされていないグラフに適しているため、これらを使用して、開始と目標の間の最短経路を見つけます。


3. 深さ優先探索と幅優先探索


どちらのアルゴリズムも、グラフ上にツリーを重ね合わせて検索します。これを検索ツリーと呼びます。 DFSとBFSは、ルートを開始ノードに設定し、ツリーの現在の葉の後続を追加して成長させます。 このようにして、DFSとBFSは、ゴールノードを見つけるかグラフを使い果たすまでグラフ全体をカバーします。 それらが異なるのは、ノードにアクセスする順序、つまり、検索ツリーにノードを追加する順序です。


各ステップで、 DFSは、少なくとも1つの含まれていない子を持つ、最後に含まれたノードの子をツリーに追加します。したがって、DFSは、開始ノード、その子、次にその孫というように追加します。 そのため、DFSは、各ステップで可能な限り検索ツリーの深さを増やします。 次に、追加するノードの子がこれ以上ない場合は、ノードの親に戻ります。


対照的に、BFSはツリーをレイヤーごとに成長させます。 最初にすべての開始ノードの子を追加して、レベル1を完了します。 次に、最初のレベルのすべての葉のすべての子を1つずつ追加します。 その後、開始ノードの孫のすべての子を追加します。 したがって、分岐係数がすべてのレベルで一定である場合、BFSは各ステップでツリーを広くします。 そのために、BFSはDFSの反対のことを行います。少なくとも1つの含まれていない子を持つ、最後に追加されたノードの子をツリーに追加します。


3.1. ツリーのような検索と グラフ検索


どちらのアルゴリズムにも、ツリーのような検索とグラフ検索の2つのバリエーションがあります。 Tree-Like Search（TLS）バージョンは、繰り返されるノードをチェックせず、ツリーに同じノードが複数回含まれる場合があります。 そのため、彼らはループに陥りがちです。 対照的に、グラフ検索（GS）の代替手段は繰り返しをチェックするため、サイクルの影響を受けませんが、より多くのメモリが必要になります。


TLSバージョンの違いを見つけやすいので、TLSバージョンに焦点を当てます。


4. 概念の違い


次の例は、DFSとBFSの主な概念上の違いを示しています。 次の検索ツリーがあると想像してみましょう。


ツリーに含まれる序数で各ノードにマークを付けましょう。 DFSとBFSにノードが含まれる順序は異なります。


BFSツリーでは、レベルのすべての包含数はレベルの数よりも低くなっています。 DFSではそうではありません。 DFSでは、ノードの包含番号がノードよりも小さい場合、のすべての子孫の番号はとその子孫よりも小さくなります。


したがって、BFSはツリーをレベルごとに成長させますが、DFSはサブツリーごとに成長させます。


5. 実装の違い


各実行ステップで、DFSとBFSの両方が検索フロンティアと呼ばれるものを維持します。 これは、現在ツリーにあるノードの子として識別されたが、まだ追加されていないノードのセットです。 BFSは常に最も最近含まれていないノードの子を追加するため、FIFOキューを使用してフロンティアを維持します。 対照的に、DFSは反復実装でLIFOキューを使用します。


検索ツリーにノードを追加するときは、その子も識別してフロンティアに追加します。 これは、ノードの拡張と呼ばれます。 したがって、BFSとDFSは次のように説明できます。


    

  • DFSは、フロンティアで最も深いノードを拡張します。
    • 

  • BFSは最も浅いノードを拡張します。
    • 



DFSは、再帰的な実装にも非常に適しています。 その場合、コールスタックはフロンティアとして機能します。


6. 完全性と最適性の違い


常に終了する場合、検索アルゴリズムは完了していると言えます。 つまり、最初から少なくとも1つの目標に到達できる場合、アルゴリズムは目標へのパスを見つけます。 それ以外の場合は、失敗の通知を返します。


アルゴリズムが目標ノードへの最適なパスを返す場合、グラフに少なくとも1つ存在する場合、アルゴリズムは最適であると言えます。


6.1. 完全


DFSは完全なアルゴリズムではありません。グラフにサイクルが含まれていると想像してみましょう。 ノードのサクセサを検討するときにツリーに最初に追加するサクセサの選択によっては、DFSがループに陥る可能性があります。


      


選択をランダム化したとしても、そのような結果になる可能性は低くなりますが、ループで終了して無期限に実行することができます。 したがって、目標が開始ノードに非常に近く、グラフが有限で小さい場合でも、DFSが終了することはありません。


DFS（のTLSバージョン）がに移行すると、とは永久に交互になります。


一方、グラフが有限の場合、BFSは常に完全です。 グラフが無限大の場合、BFSは次の条件で完了します。


ゴールノードは最初から到達可能であり、無限の数の後継ノードを持つノードはありません。


6.2. 最適性


 DFSも最適なアルゴリズムではありません。目標への最適ではないパスが返される場合があります。これは、目標に複数の方法で到達できる場合に発生しますが、DFSは最初に長いパスを検出します。


対照的に、BFSは最適です。


7. 複雑さの違い


複雑さを分析する前に、表記法を紹介しましょう。 ツリーの分岐係数、グラフ内の最長のパスの長さ、および最も浅いゴールノードの深さとします。 最初から目標に到達できない場合は、それを考慮します。 また、アルゴリズムが終了する場合のみを検討します。


7.1. 時間計算量


最悪のシナリオでは、DFSは深さがである検索ツリーを作成するため、時間計算量はです。


BFSが最適であるため、最悪の場合の結果は、レベル1、レベル2などでノードを追加した後、ノードを追加するレベルまでゴールノードを見つけることです。 合計すると、BFSの最悪の場合のツリーにはノードが含まれます。つまり、成長する時間はのオーダーです。


7.2. スペースの複雑さ


BFSはフロンティアにノードを追加し続けますが、それらの中で最も古いノードをポップするため、すべてのノードを格納する必要があります。 したがって、最悪のシナリオでのスペースの複雑さはです。これは、フロンティアの最悪の場合のサイズだからです。


DFSは異なります。 ルートがノードであるサブツリー全体を探索した後、DFSはの兄弟を試行します。 ただし、処理中およびその子孫の間、DFSはの兄弟の子孫をメインメモリに保持する必要はありません。 現在アクティブなパスにのみ焦点を当てることができ、バックトラックに必要なのはその上のノードの兄弟だけです。 したがって、DFSの最悪の場合のスペースの複雑さは。


一度にすべてを返すのではなく、現在アクティブなパス上の最も深いノードの子を1つずつ生成すると、DFSの複雑さを軽減できます。 その場合、実行中のどの時点でもノードしか保存しません。 そして、さらに先に進むことができます！ ノードを相互に変換できる場合は、単一のノードを使用して、その子または兄弟に置き換えるときに変換を適用できます。 その結果、スペースが複雑になりますが、バックトラックのために変換を元に戻す必要があります。


8. DFSとBFSのどちらを選択するか？


とはいえ、私たちが関心を持っている実際の質問は、DFSとBFSのどちらを選択するかです。


目標が深いことがわかっている場合は、BFSよりも速く深いノードに到達するためDFSを使用する必要があります。良い例は制約の充足です。 これらの問題では、変数とその値の制約が満たされるように、いくつかの変数に値を割り当てる必要があります。 結果の検索グラフの各ノードは、割り当てのリストです。 完全なソリューションに関心があるため、BFSで不完全な割り当てをゆっくりと検索するよりも、DFSでできるだけ早く完全な割り当てノードに到達する方が理にかなっています。


一方、目標が検索ツリーの浅いレベルに表示される可能性があることがわかっている場合は、BFSの方が適しています。 最適ではないパスを受け入れることができず、理論上の保証を得るためにより多くのメモリを費やす準備ができている場合も、同じことが言えます。 ただし、注意点として、BFSは大量のメモリを必要とする可能性があり、分岐係数が大きすぎる場合や目標が深い場合は非効率であることがわかります。


 DFSが完全で最適ではない場合でも、BFSを非実用的にするのはまさにメモリの複雑さです。そのため、DFSはAIの主力製品になりました。 その不完全性と次善の解決策の問題を整理することさえできます。 反復深化は、DFSの深さを制限し、増分制限深さで実行します。これは、完全で最適であり、BFSと同じ時間計算量です。 ただし、そのメモリの複雑さはDFSのそれと同じです。


8. 結論


この記事では、深さ優先探索（DFS）と幅優先探索（BFS）を比較しました。 BFSにはDFSに比べて理論上の利点がいくつかありますが、スペースが複雑であるため、実用的ではありません。 そのため、DFSをより頻繁に使用します。