ダイクストラのアルゴリズム対ユニフォームコストの検索（時間の複雑性）

Question

私の質問は次のとおりです。異なるソースによると、ダイクストラのアルゴリズムは、ユニフォームコスト検索の変形です。 Dijkstraのアルゴリズムは、ソースとすべての宛先（単一ソース）との間の最短経路を見つけることがわかります。しかし、私たちはいつでも、DIjkstraを変更して、STARTとGOALの間の最短経路を見つけることができます（目標が優先キューからポップされたとき、単に停止します）。そうすることで、最悪の場合のシナリオは、STARTから他のすべてのノードまでの最短経路を見つけることになります（目標がグラフの最も遠いノードだとします）。

最小プライオリティヒープを使用してDijkstraのアルゴリズムを実装すると、実行時間は O（Vlog V + E）になります.Eはエッジ数、Vは頂点数です。

均一コスト検索はDijkstraと同じです（少し異なる実装）ので、UCSの実行時間はDijkstraと似ていますか？しかし、私のAIクラスによると、Uniform Cost Searchは最悪のケースで指数関数的であり、O（b ^{1 + [C * /ε]}）です。ここで、C *は最適解のコストです。 （bは分岐係数）

実行時間が異なるアルゴリズムはどちらも同じですか？ランニングタイムは同じですが、見た目は違っていますか？

私はあなたの助けをいただければ幸いです:) :)

Answer 1

ありがとうは、同じ実行している時間ですが、我々はそれを見る方法が違うのですか？

はい。 Dijkstraのオリジナルのアルゴリズムが決して終了しない無限大のグラフでは、統一コスト検索を使用できます。このような状況では、VとEの両方で無限となる可能性があり、その結果得られる大きな数字は意味がないため、複雑さを定義することは無意味です。