通常、グラフをたどる必要があるときは、空間の複雑さが低いため、常に深さ優先検索を使用してきました。私の経験はかなり限られていますが、正直なところ、幅優先検索が必要な状況を見たことがありません。
幅優先検索を使用する意味があるのはいつですか?
更新：ここでの私の答えは、BFSを使用した状況を示していると思います（DFSだと思っていたため）。この場合、なぜそれが役に立ったのか、私はまだ知りたいと思っています。
質問する
20000 次
10 に答える
14
できるだけ少ないエッジをたどってノードに到達したい場合、つまり重み付けされていないグラフで最短経路を見つけたい場合。
また、深さ優先検索の空間複雑度は、各ノードが子ノードを 1 つしか持たない場合、つまりグラフが深いがあまり広くない場合、幅優先検索よりも高くなる可能性があります。
于 2009-11-01T13:32:50.227 に答える
7
検索ドメインが無限の場合、有限の解が存在する場合でも、深さ優先探索は解を終了/検出することを保証しません。
また、幅優先探索の特別なサブタイプである A* のようなより精巧なアルゴリズムも確認できます。
一般に、bfs は最適かつ完全 (分岐係数が有限) ですが、dfs はそうではありません。
于 2009-11-01T14:07:10.050 に答える
3
幅優先探索が有用な場合の重要な要因については、まだ誰も言及していません。ある方法でノードにアクセスすると、別の方法でノードにアクセスする必要がなくなる可能性があります。場合によっては、ノードにアクセスする順序に関係なく同じ作業を行うことになりますが、BFS は DFS よりも一度に保留中のアクションがはるかに少なくなります。他のケースでは、あるシーケンスでノードを訪問すると、他のノードよりも多くの作業が必要になる場合があります。その例として、さまざまな最短経路アルゴリズムが示されています。ノードが現在のものよりも短いパスで到達可能であることがわかっていない限り、ノードを訪問するためにその近隣を訪問する必要がある場合、幅優先の順序でノードを訪問すると、通常、ノードに最短パスまたはそれに近いものが割り当てられます。 -彼らの最初の訪問で。対照的に、
ところで、深さ優先アルゴリズムと幅優先アルゴリズムの違いを示す 1 つの優れたグラフィカルな図は、エリア フラッド フィルです。ここでは、白いノードを黒く塗りつぶし、隣接するノードをフラッド フィルすることによって塗りつぶします。角から始まる NxN の正方形領域をフラッディング フィルしようとすると、深さ優先の操作によって正方形がらせんまたはジグザグ シーケンスで塗りつぶされ、NxN-1 の操作がスタックに残ります。幅優先の塗りつぶしは、開始点から「注ぎ出され」、塗りつぶされる形状に関係なく、保留中の操作が最大で O(N) になります。ところで、IBM BASICA のフラッド フィルはそのように機能しました (QBASIC についてはわかりません)。
于 2011-02-04T20:03:43.037 に答える
3
最小ステップ数で検索問題を解決するために使用できます。最初に深く掘り下げると、（何らかの制限がなければ）無限の深さにつながる可能性があります。
例: 条件を満たすルートに最も近いノードを見つける。
于 2009-11-01T13:34:08.790 に答える
2
1 つの例として、ファイルシステムのトラバースがあります (再帰の深さが制限されています)。
wikipediaによると、特定のグラフ アルゴリズム (二部、連結成分) にも役立ちます。
于 2009-11-01T13:32:12.113 に答える
2
幅優先検索を使用する意味があるのはいつですか?
たとえば、グラフで最短パスを見つける必要がある場合、DFS ではそれができません。他にもいくつかのアプリケーションがありますが、一般に、DFS と BFS は異なるデータ構造で動作する同じアルゴリズムです (BFS はキューを使用し、DFS はスタックで動作します)。
于 2009-11-01T22:19:25.467 に答える
1
辺の重みのないグラフから頂点への最短経路を取得する必要がある場合。
于 2009-11-01T13:34:27.837 に答える
1
詳細な最初の検索では、「ローカル」ソリューションを見つけることができます。実際にグローバルなソリューションを見つけるには、グラフ全体をトラバースする (またはヒューリスティックを使用する) 必要があります。
于 2009-11-01T13:34:34.230 に答える
1
BFS は時々本当に便利です。たとえば WBS を表すツリーがあるとします。ユーザーにそのレベルを 1 つだけ提示したい場合があります。
于 2009-11-01T13:35:36.647 に答える
1
幅優先探索アルゴリズムは、開始点に可能な限り近くにとどまることを好みます。私が考えることができる状況のいくつかは次のとおりです。
- ソーシャル ネットワーキング Web サイトは、指定された距離にいる人を見つけるために使用できます。
- トレント/ピアツーピア ネットワークで近隣のコンピューターを探すのに役立ちます。
- GPS ナビゲーション システムは、これを使用して近くの場所を見つけることができます。
于 2016-05-06T09:45:33.060 に答える