DFSとBFSの違いは理解しているのですが、どのような場合に使い分けるのが現実的なのでしょうか?
DFSがBFSに勝る例、逆にBFSがDFSに勝る例があれば教えてください。
それは、サーチツリーの構造や、解答(検索された項目)の数と位置に大きく依存する。
もし、解がツリーのルートからそれほど離れていないことが分かっていれば、幅優先探索(BFS)の方が良いかもしれません。 BFS(幅優先探索)がよいでしょう。
ツリーが非常に深く、解決策が稀な場合は、深さ優先探索(DFS)がよいでしょう。 (DFS)は非常に時間がかかるが、BFSの方が速いかもしれない。
木が非常に広い場合、BFSはメモリを大量に必要とするので 全く実用的でない可能性がある。
解が頻繁に出てくるが、木の深いところにある場合、BFSは実用的でない可能性 は実用的でない。
探索木が非常に深い場合、深さ優先探索(DFS)のために探索深さを制限する必要があります。 深さ優先探索(DFS)を行うには、深さを制限する必要があります。 深化を繰り返すなど)。
しかし、これは経験則に過ぎず、実際に試してみる必要があるでしょう。
奥行き先検索。 -----------。
デプスファーストの検索は、ゲームのシミュレーション(および現実世界のゲームのような状況)でよく使用されます。 典型的なゲームでは、いくつかの可能なアクションの1つを選択できます。 それぞれの選択は、さらなる選択につながり、それぞれがさらなる選択につながり、さらに拡大し続けるツリー型の可能性のグラフにつながります。
。。
たとえば、チェスのようなゲームでは、何をするかを決めるときに三目並べをすると、精神的に動きを想像し、次に対戦相手の可能な応答、次に応答などを想像できます。 どの動きが最良の結果につながるかを確認することで、何をすべきかを決定できます。
ゲームツリーのいくつかのパスだけがあなたの勝利につながります。 対戦相手の勝利につながる人もいます。そのようなエンディングに達したら、前のノードにバックアップまたはバックトラックして、別のパスを試す必要があります。 このようにして、成功した結論を持つパスを見つけるまで、ツリーを探索します。 次に、このパスに沿って最初の動きをします。
----------。
ブレッドファースト検索。 --------------------。
幅の広い最初の検索には興味深いプロパティがあります。最初に、開始点から1エッジ離れているすべての頂点が見つかり、次に2エッジ離れているすべての頂点が見つかります。 これは、開始頂点から特定の頂点への最短経路を見つけようとする場合に役立ちます。 BFSを起動すると、指定された頂点が見つかると、これまでに追跡したパスがノードへの最短パスであることがわかります。 より短いパスがあった場合、BFSはすでにそれを発見したでしょう。
ブレッドファースト検索は、BitTorrentなどのピアツーピアネットワークで隣接ノードを見つけるため、GPSシステムが近くの場所を見つけるため、ソーシャルネットワーキングサイトが指定された距離にいる人を見つけるためなどに使用できます。
からの素晴らしい説明。 http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/。
BFSの例。
BFSがどのようになるかの例を次に示します。 これは、ITERATIVEアプローチでQUEUEを使用するレベルオーダーツリートラバーサルのようなものです(ほとんどの場合、RECURSIONはDFSで終了します)。 数値は、ノードがBFSでアクセスされる順序を表します。
ここに画像の説明を入力してください。! 詳細な最初の検索では、ルートから開始し、探しているノードが見つかるか、リーフノード(子供がいないノード)にぶつかるまで、可能な限りツリーの枝の1つに従います。 葉の節にぶつかった場合は、未踏の子供と一緒に最も近い祖先で検索を続けます。
DFSの例。
DFSがどのようになるかの例を次に示します。 バイナリーツリーの注文後のトラバーサルは、最初にリーフレベルから作業を開始すると思います。 数値は、ノードがDFSでアクセスされる順序を表します。
DFSとBFSの違い。
BFSとDFSを比較すると、DFSの大きな利点は、すべての子ポインターを各レベルに格納する必要がないため、BFSよりもメモリ要件が大幅に低いことです。 データと探しているものによっては、DFSまたはBFSのどちらかが有利になる可能性があります。
たとえば、家系図が生きている人を探しているなら、その人が木の底にいると想定しても安全です。 これは、BFSがその最後のレベルに到達するのに非常に長い時間がかかることを意味します。 ただし、DFSは目標をより早く見つけます。 しかし、非常に昔に亡くなった家族を探していたら、その人は木の上に近づくでしょう。 その場合、BFSは通常DFSよりも高速になります。したがって、どちらの利点も、データと探しているものによって異なります。
もう1つの例はFacebookです。友達の友達への提案。 BFSを使用できる場所を提案するには、すぐに友達が必要です。最短経路を見つけるか、サイクルを検出する(再帰を使用)、DFSを使用できます。
木の深さが様々で、木の一部だけを探索すれば解が得られる場合、一般にBreadth First Searchが最適なアプローチとなる。例えば、ある開始値から最終値までの最短経路を求める場合などは、BFSを使うのがよいでしょう。
深さ優先探索は、木全体を探索する必要がある場合によく使われます。BFSよりも実装が簡単で(再帰を利用する)、必要な状態量も少ない。BFSでは 'frontier' 全体を保存する必要がありますが、DFSでは現在の要素の親ノードのリストだけを保存すればよいのです。
DFSはBFSよりスペース効率は良いが、不必要な深さまで行く可能性がある。
もし、幅が大きく(分岐係数が大きく)、深さが非常に限られている場合(例えば、移動回数が限られている)、BFSよりもDFSの方が好ましいと言えます。
DFSの空間効率とBFSのレベルオーダー訪問を組み合わせた、あまり知られ ていないアルゴリズムとして、反復深化第一探索があることを 述べておく必要があります。このアルゴリズムはいくつかのノードを再訪しますが、漸近的な差の一定ファクターにしか寄与しません。
プログラマーとしてこの質問にアプローチすると、1つの要素が際立っています。再帰を使用している場合、ノードを含む追加のデータ構造を維持する必要がないため、実装するには深さ優先検索がより単純です。まだ探索します。
ノードに「既にアクセス済み」の情報を保存している場合の非指向グラフの深さ優先検索を次に示します。
def dfs(origin): # DFS from origin:
origin.visited = True # Mark the origin as visited
for neighbor in origin.neighbors: # Loop over the neighbors
if not neighbor.visited: dfs(next) # Visit each neighbor if not already visited
「すでにアクセスした」情報を別のデータ構造に保存する場合:
def dfs(node, visited): # DFS from origin, with already-visited set:
visited.add(node) # Mark the origin as visited
for neighbor in node.neighbors: # Loop over the neighbors
if not neighbor in visited: # If the neighbor hasn't been visited yet,
dfs(node, visited) # then visit the neighbor
dfs(origin, set())
これを、何があってもまだアクセスできないノードのリスト用に個別のデータ構造を維持する必要がある、幅の広い最初の検索と比較してください。
BFSについては、Facebookの例を検討できます。 他の友達のプロフィールからFBプロフィールから友達を追加するという提案を受けます。 A-> BをB-> EとB-> Fの間に、AがEとFの提案を得るとします。彼らはBFSを使用して2番目のレベルまで読む必要があります。 DFSは、ソースから宛先までのデータに基づいて何かを予測したいシナリオに基づいています。 チェスや数独についてすでに述べたように。 ここで私が異なるのは、DFSが最初にパス全体をカバーし、次に最良のものを決定できるため、DFSを最短のパスに使用する必要があるということです。 しかし、BFSは貪欲なアプローチを使用するため、最短経路のように見えるかもしれませんが、最終結果は異なる場合があります。 私の理解が間違っているかどうか教えてください。
簡単に言えば:
ブレッドファーストサーチ。 (BFS。) アルゴリズム。, その名前"から。;Breadth"。; ノードの外側の端からノードのすべての隣人を発見し、次に、前述の隣人の訪問されていない隣人を、それらの外側の端などから発見します。, 元のソースから到達可能なすべてのノードが訪問されるまで。 (訪問されていないノードなどが残っている場合は、続行して別の元のソースを取得できます。). そのため、エッジの重みが均一であれば、ノード(元のソース)から別のノードへの最短パス(存在する場合)を見つけるために使用できます。
深度ファーストサーチ(DFS)アルゴリズムは、その名前「深度」から、最近発見されたノードxの訪問されていない隣人をその外縁から発見します。 ノードxから訪問されていない隣人がいない場合。, アルゴリズムは、ノードの訪問されていない隣人を検出するためのバックトラックです。 (その外縁を通して。) そこからノードxが発見されました。, など。, 元のソースから到達可能なすべてのノードが訪問されるまで。 (訪問されていないノードなどが残っている場合は、続行して別の元のソースを取得できます。).
BFSとDFSの両方が不完全になる可能性があります。 たとえば、ノードの分岐係数が無限である場合、またはリソース(メモリ)がサポートするのに非常に大きい場合(例:. 次に発見されるノードを格納する場合)、検索されたキーが元のソースから数エッジの距離にある場合でも、BFSは完全ではありません。 この無限の分岐係数は、特定のノードから検出する無限の選択肢(隣接するノード)が原因である可能性があります。 深さが無限である場合、またはリソース(メモリ)がサポートするのに非常に大きい場合(例:. 次に発見するノードを保存する場合)、検索されたキーが元のソースの3番目の隣になる可能性がある場合でも、DFSは完全ではありません。 この無限の深さは、アルゴリズムが発見するすべてのノードについて、少なくとも以前は訪問されていなかった新しい選択(隣接するノード)がある状況が原因である可能性があります。
したがって、BFSとDFSをいつ使用するかを結論付けることができます。管理可能な限られた分岐係数と管理可能な限られた深度を扱っていると仮定します。 検索されたノードが浅い場合、つまり. 元のソースからいくつかのエッジの後に到達可能である場合、BFSを使用することをお勧めします。一方、検索されたノードが深い場合、つまり. オリジナルソースから多くのエッジの後に到達可能なので、DFSを使用する方が良いです。
たとえば、ソーシャルネットワークで特定の人の同様の興味を持つ人を検索したい場合は、この人のBFSを元のソースとして適用できます。これは、これらの人が直接の友達や友達の友達になるためです。 1つまたは2つのエッジが遠いです。 一方、特定の人の興味がまったく異なる人を検索したい場合は、この人のDFSを元のソースとして適用できます。これは、これらの人のほとんどが彼から遠く離れているためです。 友達の友達の友達。... つまり. あまりにも多くのエッジ。
BFSとDFSのアプリケーションは、それぞれを検索するメカニズムが原因で異なる場合があります。 たとえば、ノードがどこにあるか情報がないノードから別のノードへの到達可能性を確認したいだけの場合は、BFS(分岐係数が管理可能であると仮定)またはDFS(深さが管理可能であると仮定)を使用できます。 また、どちらもグラフのトポロジーソートなどの同じタスクを解決できます(ある場合)。 BFSを使用して、ノード(元のソース)から別のノードへの単位重量エッジの最短パスを見つけることができます。 一方、DFSは、非循環グラフで2つのノード間の最長の経路を発見するなど、深く掘り下げることの性質上、すべての選択肢を使い果たすために使用できます。 また、DFSは、グラフでのサイクル検出に使用できます。
最終的に無限の深さと無限の分岐係数がある場合、反復深化検索(IDS)を使用できます。
これは、特定のケースではBFSがDFSよりも優れていることを示す良い例です。 https://leetcode.com/problems/01-matrix/。
正しく実装されている場合、両方のソリューションは、現在のセル+1より遠い距離にあるセルを訪問する必要があります。 しかし、DFSは非効率的であり、同じセルを繰り返し訪問し、O(n * n)の複雑さをもたらしました。
例えば、。
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,