algorithm - A* がダイクストラのアルゴリズムよりも高速に実行されるのはなぜですか?

Question

ウィキペディアによると、A* は O(|E|) で実行され、|E| は グラフ内のエッジの数です。しかし、私の友人は、A* はダイクストラのアルゴリズムの一般的なケースにすぎず、ダイクストラのアルゴリズムは O(|E| + |V| log |V|) で実行されると言っています。A* が Dijkstra のアルゴリズムよりも高速に実行される理由について、私は混乱しています。

Answer 1

基本的に、A* はヒューリスティックを使用して、ケースに最適なルートについてより知識に基づいた推測を行うことができるため、より高速です。これは、ダイクストラのアルゴリズムでは行われません。