今まで読んできたものから。ダイクストラのアルゴリズムは、グラフをトラバースするときにすべてのノードを緩和する必要があるため、ゴールへの最短パスを見つけるという点では、ベスト ファースト サーチの方が高速に見えます。ダイクストラのアルゴリズムがベスト ファースト サーチよりも優れている点は何ですか?
質問する
15514 次
3 に答える
35
EDIT : あなたの編集は、 BFSではなくBest-First Searchに興味があることを明確にしています。
ベストファースト検索は、実際には情報に基づいたアルゴリズムであり、最も有望なノードを最初に展開します。よく知られているA* アルゴリズムと非常によく似ています(実際には、A* は特定の最良優先探索アルゴリズムです)。
ダイクストラは情報に基づいていないアルゴリズムです。グラフに関する知識がなく、各ノードからターゲットまでの距離を推定できない場合に使用する必要があります。
各 にヒューリスティック関数 を使用すると、A* (ベストファースト検索) がダイクストラのアルゴリズムに崩壊することに注意してください。h(v) = 0v
さらに、最適な最初の検索は最適ではありません[最短経路を見つけることが保証されていません]。また、許容ヒューリスティック関数を使用しない場合は A* ですが、ダイクストラのアルゴリズムはヒューリスティックを中継しないため、常に最適です。
結論: グラフに関する知識があり、ターゲットからの距離を推定できる場合は、ダイクストラよりも最適優先検索を使用する必要があります。そうしないと、 を使用しh(v) = 0、既に探索された頂点のみをリレーする情報に基づいていないベストファースト検索が、ダイクストラのアルゴリズムに崩壊します。
また、最適性が重要な場合 - ダイクストラのアルゴリズムは常に適合しますが、最適優先検索アルゴリズム (特に A*) は、適切なヒューリスティック関数が利用可能な場合にのみ使用できます。
元の回答 - BFS よりもダイクストラを選択した理由への回答:
加重グラフに関しては、BFS は失敗します。
例：
A
/ \
1 5
/ \
B----1----C
ここに: w(A,B) = w(B,C) = 1, w(A,C) = 5.
A からの BFSA->Cは最短パスとして返されますが、加重グラフの場合、加重 5 のパスです!!! 最短パスの重みは 2:A->B->Cです。
ダイクストラのアルゴリズムはこの間違いを犯さず、最短の加重パスを返します。
グラフが重み付けされていない場合 - BFS は最適かつ完全であり、通常はダイクストラよりも優先される必要があります - どちらも単純で高速であるためです (少なくとも漸近的に言えば)。
于 2012-04-29T17:39:34.863 に答える
1
通常、パス検索のベスト ファースト サーチアルゴリズムは、指定された 2 つのノード ( SourceとSink ) 間のパスを検索しますが、ダイクストラのアルゴリズムは、ソースと他のすべてのノード間のパスを検索します。したがって、それらを比較することはできません。また、ダイクストラ自体は一種のベスト ファースト サーチ(A *のバリエーション) であるため、ベスト ファースト サーチではないとは言えません。また、通常のベスト ファースト サーチ アルゴリズムはヒューリスティックを使用しており、正確性を保証するものではありません。最後に、重み付きの場合、通常、実行時間は重みに依存しますが、ダイクストラのアルゴリズムはグラフ サイズに依存します。
于 2012-04-29T18:09:52.253 に答える
0
BFS は、すべてのエッジの重みが同じである場合、つまりソースから頂点までのエッジの最小数を見つける場合に、ソースから頂点までの最短パスを見つけるのに適しています。Dikjstra は加重グラフに適していますが、
于 2014-06-15T07:38:55.073 に答える