425

DFS と BFS の違いは理解していますが、どちらを使用するのがより実用的か知りたいですか?

DFSがBFSを打ち負かし、その逆の例を誰か挙げてもらえますか?

4

15 に答える 15

440

これは、検索ツリーの構造と、ソリューション (別名、検索項目) の数と場所に大きく依存します。

  • 解がツリーのルートから遠くないことがわかっている場合は、幅優先探索 (BFS) の方が適している可能性があります。

  • ツリーが非常に深く、ソリューションがほとんどない場合、深さ優先検索 (DFS) は非常に長い時間がかかる可能性がありますが、BFS の方が高速である可能性があります。

  • ツリーが非常に広い場合、BFS は大量のメモリを必要とする可能性があるため、まったく実用的ではない可能性があります。

  • ソリューションが頻繁に発生するが、ツリーの奥深くにある場合、BFS は実用的ではない可能性があります。

  • 検索ツリーが非常に深い場合は、深さ優先検索 (DFS) の検索の深さを制限する必要があります (たとえば、反復的な深化など)。

しかし、これらは単なる経験則です。おそらく実験する必要があります。

とにかく、実際には、これらのアルゴリズムを純粋な形で使用することは通常ないと思います。検索空間の有望な部分を最初に探索するのに役立つヒューリスティックがある場合もあれば、効率的に並列化できるように検索アルゴリズムを変更したい場合もあります。

于 2010-07-26T07:32:46.993 に答える
208

深さ優先検索

深さ優先検索は、ゲームのシミュレーション (および現実世界のゲームのような状況) でよく使用されます。典型的なゲームでは、いくつかの可能なアクションから 1 つを選択できます。それぞれの選択肢はさらなる選択肢につながり、それぞれの選択肢はさらなる選択肢につながり、さらに拡大し続ける可能性のツリー形状のグラフになります。

ここに画像の説明を入力

たとえば、チェスや三目並べのようなゲームでは、どの手を打つかを決めるときに、頭の中で動きを想像し、次に対戦相手の考えられる反応、次に自分の反応などを想像できます。どの動きが最良の結果につながるかを見て、何をすべきかを決めることができます。

ゲーム ツリーの一部のパスのみが勝利につながります。対戦相手の勝利につながるものもあります。そのような結末に到達した場合は、前のノードに戻るかバックトラックして、別のパスを試す必要があります。このようにして、成功した結論を持つパスが見つかるまで、ツリーを探索します。次に、このパスに沿って最初の移動を行います。

幅優先探索

幅優先検索には興味深い特性があります。最初に、開始点から 1 エッジ離れたすべての頂点を見つけ、次に 2 エッジ離れたすべての頂点を見つけます。これは、開始頂点から特定の頂点までの最短パスを見つけようとしている場合に役立ちます。BFS を開始し、指定された頂点を見つけると、これまでトレースしてきたパスがノードへの最短パスであることがわかります。もっと短いパスがあれば、BFS はすでにそれを見つけているはずです。

幅優先探索は、BitTorrent のようなピア ツー ピア ネットワークで近隣ノードを見つけるために使用できます。近くの場所を見つけるための GPS システム、指定された距離にいる人を見つけるためのソーシャル ネットワーキング サイトなどです。

于 2016-05-06T09:35:06.197 に答える
127

http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/からの素敵な説明

BFSの例

BFS がどのように見えるかの例を次に示します。これは Level Order Tree Traversal のようなもので、QUEUE を ITERATIVE アプローチで使用します (ほとんどの RECURSION は DFS で終了します)。数字は、BFS でノードがアクセスされる順序を表します。

ここに画像の説明を入力

深さ優先検索では、ルートから開始し、探しているノードが見つかるか、リーフ ノード (子を持たないノード) に到達するまで、可能な限りツリーの枝の 1 つをたどります。リーフ ノードにヒットした場合は、探索されていない子を持つ最も近い祖先で検索を続けます。

DFSの例

DFS の例を次に示します。二分木でのポスト オーダー トラバーサルは、最初にリーフ レベルから作業を開始すると思います。数字は、DFS でノードがアクセスされる順序を表します。

ここに画像の説明を入力

DFS と BFS の違い

BFS と DFS を比較すると、DFS の大きな利点は、各レベルですべての子ポインターを格納する必要がないため、BFS よりもメモリ要件がはるかに低いことです。データと探しているものに応じて、DFS または BFS のいずれかが有利な場合があります。

たとえば、ある家系図でまだ生きている人を探している場合、その人は木の一番下にいると想定しても問題ありません。これは、BFS が最後のレベルに到達するまでに非常に長い時間がかかることを意味します。ただし、DFS を使用すると、より早くゴールを見つけることができます。しかし、はるか昔に亡くなった家族を探しているなら、その人は木のてっぺんに近いでしょう。その場合、通常、BFS は DFS よりも高速です。したがって、どちらの利点も、データと探しているものによって異なります。

もう 1 つの例は Facebook です。友達の友達に関する提案。BFS を使用できる場所を提案するために、すぐに友人が必要です。DFS を使用して、最短パスを見つけたり、(再帰を使用して) サイクルを検出したりすることができます。

于 2015-02-13T08:49:52.017 に答える
59

幅優先探索は、一般に、ツリーの深さが変化する可能性があり、ツリーの一部のみを検索して解を求める必要がある場合に最適な方法です。たとえば、開始値から最終値までの最短経路を見つける場合は、BFS を使用するのに適しています。

深さ優先検索は、ツリー全体を検索する必要がある場合によく使用されます。BFS より (再帰を使用して) 実装するのが簡単で、必要な状態も少なくなります。BFS では「フロンティア」全体を保存する必要がありますが、DFS では現在の要素の親ノードのリストのみを保存する必要があります。

于 2010-07-26T12:09:20.707 に答える
34

DFS は BFS よりもスペース効率が高いですが、不必要な深さになる可能性があります。

それらの名前は明らかです: 大きな幅 (つまり、大きな分岐係数) があるが、非常に限られた深さ (たとえば、「移動」の数が限られている) がある場合、DFS は BFS よりも好ましい可能性があります。

IDDFS について

DFS のスペース効率を組み合わせたあまり知られていないバリアントがあることを言及する必要がありますが、(累積的に) BFS のレベル順の訪問は、反復的な深さ優先探索です。このアルゴリズムはいくつかのノードを再検討しますが、漸近差の定数係数のみに寄与します。

于 2010-07-26T07:30:53.817 に答える
21

プログラマーとしてこの質問に取り組む場合、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(neighbor) # 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(neighbor, visited)             # then visit the neighbor
dfs(origin, set())

これを幅優先検索と比較してください。ここでは、何があっても、まだアクセスしていないノードのリスト用に別のデータ構造を維持する必要があります。

于 2012-03-13T17:56:59.633 に答える
16

BFS の重要な利点の 1 つは、重み付けされていないグラフ内の任意の 2 つのノード間の最短経路を見つけるために使用できることです。一方、同じ に DFS を使用することはできません。

于 2015-12-11T23:08:43.017 に答える
4

一部のアルゴリズムは、動作するために DFS (または BFS) の特定のプロパティに依存します。たとえば、2 連結コンポーネントを見つけるための Hopcroft および Tarjan アルゴリズムは、DFS によって検出された、既にアクセスされた各ノードがルートから現在探索されているノードへのパス上にあるという事実を利用します。

于 2010-07-26T14:13:31.660 に答える
2

DFSとBFSの性質による。たとえば、最短経路を見つけたいとき。通常は bfs を使用しますが、「最短」を保証できます。しかし、dfs は、この時点から到達できることのみを保証でき、「最短」を保証することはできません。

于 2015-08-12T04:01:29.937 に答える
2

深さ優先検索はノードの処理時にスタックを使用するため、バックトラッキングは DFS で提供されます。幅優先検索では、スタックではなくキューを使用して処理されるノードを追跡するため、バックトラッキングは BFS では提供されません。

于 2017-05-22T17:39:30.613 に答える
1

ツリーの幅が非常に大きく、深さが小さい場合は、再帰スタックがオーバーフローしないため、DFS を使用します。幅が小さく、深さが非常に大きい場合は、BFS を使用してツリーをトラバースします。

于 2017-11-26T18:10:44.183 に答える
0

これは、特定の場合に 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,
于 2017-06-01T06:11:24.577 に答える