私はこれを読みました: http://en.wikipedia.org/wiki/A*_search_algorithm
A* は dijkstra を使用するよりも高速であり、ベスト ファースト サーチを使用して処理を高速化します。
アルゴリズムをミリ秒単位で実行する必要がある場合、A* が最も重要な選択肢になるのはいつですか。
私が理解していることから、必ずしも最良の結果が返されるとは限りません。
迅速な結果が必要な場合、パスを事前に計算したほうがよいですか? それらを保存するには、メガバイトのスペースが必要になる場合があります。
A *は、ダイクストラを使用するよりも高速であり、最良優先探索を使用して処理を高速化します。
A *は、基本的にダイクストラの情報に基づいたバリエーションです。
A *は、 [ ]
の値に応じて、次に探索する頂点を貪欲に選択するため、「最良優先探索」と見なされます。ここで、はヒューリスティックであり、はこれまでのコストです。f(v)f(v) = h(v) + g(v)hg
非有益なヒューリスティック関数を使用する場合：h(v) = 0それぞれについて：A *は、ダイクストラのアルゴリズムと同じvように、「これまでのコスト」（）のみに従って次に開発する頂点を選択することに注意してください。したがって、A*はデフォルトでダイクストラのアルゴリズムになります。アルゴリズム。g(v)h(v) = 0
アルゴリズムをミリ秒単位で実行する必要がある場合、A*が最も目立つ選択肢になるのはいつですか。
完全ではありませんが、それは多くのことに依存します。私の個人的な経験から、降下ヒューリスティック関数を使用している場合、最初に貪欲な最良優先（ヒューリスティック関数のみに従って選択）は、通常、A *よりも大幅に高速です（ただし、最適に近いわけではありません）。
私が理解していることから、それは必ずしも最良の結果を返すとは限りません。
A *は、 Admissibleヒューリスティック関数を使用する場合、完全（パスが存在する場合はパスを検索）と最適（常に最短パスを検索）の両方です。あなたの機能が許容されない場合-すべての賭けはオフです。
迅速な結果が必要な場合は、パスを事前に計算する方がよいですか？それらを保存するには、メガバイトのスペースが必要になる場合があります。
これは、 15パズルの問題など、一部の問題で行われる一般的な最適化ですが、より高度です。ポイントAからポイントBへのパスはマクロと呼ばれます。一部のパスは非常に便利であり、覚えておく必要があります。これらのマクロを記憶することで処理を高速化するために、機械学習コンポーネントがアルゴリズムに追加されています。
ここでのポイントAからポイントBへのパスは、通常、状態グラフではなく、問題自体にあることに注意してください（たとえば、正方形を一番下の線から上の線に移動する方法...）
物事をスピードアップする
には：ヒューリスティックがあり、それが遅すぎると感じ、最適ではない場合でもより迅速なソリューションが必要な場合-A *Epsilonは通常A*よりも高速ですが、パスの最適性に限界があります（最適にどれだけ近いか）。
Dijkstra は A* の特殊なケースです (ヒューリスティックがゼロの場合)。
検索：
2 つのコスト関数があります。
g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.
各ノードの総コストは、f(n)=g(n)+h(n) で計算されます。
ダイクストラ:
ソースから各ノードまでの実際のコスト値である 1 つのコスト関数があります。 f(n)=g(n) 実際のコストのみを考慮して、ソースから他のすべてのノードへの最短経路を見つけます。
A*はDijkstraと同じですが、唯一の違いは、A* はヒューリスティック関数を使用してより良いパスを探そうとすることです。この関数は、他のノードよりも優れていると思われるノードを優先しますが、Dijkstra は可能なすべてのパスを探索します。
その最適性は使用されるヒューリスティック関数に依存するため、これにより最適ではない結果が返される可能性があり、同時に特定のレイアウトのヒューリスティックが改善され、結果 (およびおそらく速度) が改善されます。
ダイクストラよりも高速であることが意図されています。ノードごとに必要なメモリと操作が多くても、調査するノードがはるかに少なく、いずれにしてもゲインが良好であるためです。
リアルタイムの結果が必要で、グラフが非常に大きい場合は、パスを事前に計算することが唯一の方法かもしれませんが、通常、ルートをあまり頻繁にパス検索したくない場合があります (頻繁に計算する必要があると思います)。
簡単な答え: A* はヒューリスティックを使用して検索を最適化します。つまり、あるノードからターゲットまでのコストをある程度推定できる関数を定義できます。これは、たとえば、特定のグラフ ノードからターゲットまでの距離を推測できる地理的表現 (マップ) 上のパスを検索する場合に特に役立ちます。したがって、通常、A* はゲームなどでパス検索に使用されます。Djikstra はより一般的なケースで使用されます。
いいえ、A* が常に最適なパスを提供するとは限りません。ヒューリスティックが「地理的」距離である場合、次の例は最適でないパスを与える可能性があります。
[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
|----------------------------------------------------------------|