ダイクストラとAスターの違いと利点 [重複] 質問する

A* はダイクストラ法を使用するよりも高速であり、最良優先探索を使用して処理を高速化すると述べています。

A* は基本的に、ダイクストラ法の情報に基づいたバリエーションです。A * は、 [ ] の値 (はヒューリスティック、 はこれまでのコスト
) に応じて、次に探索する頂点を貪欲に選択するため、「最善の初回探索」と見なされます。f(v)f(v) = h(v) + g(v)hg

非情報ヒューリスティック関数を使用する場合、h(v) = 0各 に対してv、A* は「これまでのコスト」( ) のみに従って次に展開する頂点を選択することに注意してくださいg(v)。これは、ダイクストラのアルゴリズムと同じです。つまり、 の場合h(v) = 0、A* はデフォルトでダイクストラのアルゴリズムを使用します。

アルゴリズムを数ミリ秒単位で実行する必要がある場合、A* が最も重要な選択肢となるのはいつでしょうか。

必ずしもそうではありません。それは多くのことに依存します。適切なヒューリスティック関数がある場合、私の個人的な経験では、貪欲なベストファースト（ヒューリスティック関数のみに従って選択する）は通常、A* よりも大幅に高速です（ただし、最適にはほど遠いです）。

私の理解では、必ずしも最良の結果が返されるわけではありません。

A*は、完全（存在する場合はパスを見つける）かつ最適（常に最短パスを見つける）である。許容されるヒューリスティック関数あなたの機能が許容されない場合は、すべてが無効になります。

すぐに結果が必要な場合は、パスを事前に計算したほうがよいでしょうか? パスを保存するには数メガバイトのスペースが必要になる場合があります。

これは、いくつかの問題で行われる一般的な最適化であり、例えば、15パズル問題ですが、より高度です。ポイント A からポイント B までのパスはマクロと呼ばれます。パスの中には非常に便利なものもあり、覚えておく必要があります。これらのマクロを記憶することで処理を高速化するために、機械学習コンポーネントがアルゴリズムに追加されています。

ここでのポイント A からポイント B へのパスは、通常、状態グラフ上ではなく、問題自体の中にあることに注意してください (たとえば、一番下の線から上の線に正方形を移動する方法など)。

スピードを上げるには:
ヒューリスティックスがあり、それが遅すぎると感じ、最適ではないとしてもより速い解決策を望む場合 -A* イプシロン通常は A* よりも高速であり、パスの最適性 (最適にどれだけ近いか) の上限を示します。