Dijkstraのアルゴリズムからのステップアップはa*（読み：”A Star”）です。 経路探索の面では、Dijkstraのアルゴリズムは、すべてのパスとすべての頂点を試して、出発点と目的地の間の最短パスを見つけたいと考えていますが、a*には、すべてのパスと頂点をチェックすることなく最短パスを見つけることを可能にするヒューリスティックな属性があります。 各アルゴリズムにはユースケースがありますが、一般的に言えば、DijkstraとA*の両方が最短経路を見つけることができますが、A*はそれをより速く行います。比較のポイントがたくさんあるので、この記事に入る前にDijkstraのアルゴリズムについて少し知っておくことをお勧めします。
またはいっそのこと、主題の私の最後の記事を読んで下さい! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629
私は私の例のためにいくつかのことをセットアップする必要がありますし、ヒューリスティックが何であるか 開始するには、私はあなたに私の例のために使用したいグラフのタイプをお見せしましょう。
たとえば、中心の正方形/頂点Eを見てみましょう。 それは8つの隣接する頂点を持っているので、上、下、左、右、そしてそれぞれのすべての対角の組み合わせで移動することができます。 そして、それは本当に私がここでセットアップしようとしていたすべてです：私は市松板を使用するつもりです、と私は八方向の動きを可能にします。 少し長い目で見たが、今の動きと動きのコストを見てみましょう。単純なことから始めて、上、下、左、右に移動すると移動コストが1になると言います。
単純なことから始めて、上、下、左、右に移動すると、移動コストが1にな ボードが忙しくなっているので、私はグラフを抽出し、エッジの重みとしてその動きのコストを追加します。p>
これらの重みが距離であり、関係と隣人がこのようにレイアウトされている場合、ジオメトリは対角移動のコストを教えてくれま ピタゴラスの定理を使用して、我々は取得する必要があります√(12 + 12) = √2, これはおよそ1.41421356237です…これは非常に良い数字ではありません。 だから、私はアイデアを盗むでしょう（そして私の情報源を引用してください！）、および費用を掛け、切り捨てる。 両方のタイプの動きについて、私はそれらを10倍にしてから、小数点以下の桁数を切り捨てます。 これにより、上、下、左、右の動きには10、斜めの動きには14の最終的なコストが得られます。p>
ヒューリスティックス
私はこれらを定義するのが難しいと感じているので、私は主題に関するWikipediaのオープニングラインから始めます:
コンピュータサイエンス、人工知能、数学的最適化において、ヒューリスティック（ギリシャ語のσ ω”i find,discover”から）は、古典的な方法が遅すぎるときに問題をより迅速に解決したり、古典的な方法が厳密な解を見つけられなかったときに近似解を見つけるために設計された技術である。 これは、最適性、完全性、正確性、または速度の精度を取引することによって達成されます。 ある意味では、それは近道と考えることができます。p>
それは便利ですか？ 分かったか? 私はそれを取得していないので。 つまり、私はちょっとそれを得て、それは正確な説明ですが、これがヒューリスティックについて聞いたことがある最初のものであれば、ヒューリスティックがこれから何であるかの完全な画像を得るかどうかはわかりません。 私はちょうどA*の経路発見ヒューリスティックについて教えている場合多分、あなたはより良い把握を得るでしょう。
Dijkstraのアルゴリズムでは、焦点は1つの値、つまり開始インデックスからの最短距離にありました。 あなたがそれについて考えるとき、それは一種の奇妙です。 このアルゴリズムは、ある目的地への新しい短いパスを見つけようとしていますが、その焦点は常に開始場所にあります。 誰かが食料品のために出かけるが、店に着くまで彼らの家に目を離さないようにしようとすると、全体の道を後方に歩いて想像してみてください。 実際の生活では、これはおそらく動作しませんが、あなたは彼らにすべての町に行く時間を与えた場合、多分、それは最終的に動作するかもしれません。
この間抜けな類推から外れると、A*はDijkstraのものとは異なります。 A*は、Dijkstraのように、家からどれくらい離れているかを追跡しますが、そのユニークな特徴は、目的地からどれくらい離れているかを追跡することです。 次のステップを実行するとき、Dijkstra’sは現在どのパスが最短であるかを調べますが、a*はさらに一歩進み、そのステップが目標に近づいているかどうか より簡単に言えば、A*は目標までの残りの距離の概算を持ち、その推定値がゼロに近づくと、正しい方向に移動していることがわかります。 これは、私たちの例で使用するヒューリスティックです。
アルゴリズムをステップスルー
これはかなり簡単な例になりますが、アルゴリズムの基本的な流れと繰り返しを示す必要があります。 私は他の、より複雑な例への私の参照にリンクを提供することを確認しますが、これはそれらのための良い入門書でなければなりません。 私はDijkstraのデモンストレーションと同様のセットアップを使用します。
これが開始点であり、Aの近傍を見て、その値をテーブルに追div>
最初に、b、e、およびfをオープンセットに追加します。 次に、開始からの最短距離を見つけることができ、すべてが開始から一歩であるため、BとEの場合は10秒、Fへの対角移動の場合は14秒になります。 最後に、それらの合計を取得し、前の頂点列のそれぞれに「A」を追加します。この時点で、必要なすべてをAで実行したので、閉じたセットに移動され、新しい現在の頂点が必要になります。 次にどの頂点を調べる必要があるかを判断するために、開いているセットを見て、合計が最も低い頂点を見つけます。 今のところ、それは36.1の合計を持つFです。 そこで、それを現在の頂点にし、その近傍の値の計算を開始します。div>
Fは持っています八人の隣人が、唯一の五人はここで変更されようとしています。 まず、Aは現在閉じたセットにあるので、今は変更できません。 残りの7つについては、それらを開いているセットに追加し（すでにその一部でない限り）、最初からそれらの距離を調べてみましょう。 これはDijikstraのアルゴリズムのようにうまくいくでしょう、そして我々はfからの近隣の距離のそれぞれに開始からのFの距離を追加するでしょう.私たちのテーブル上では、開始からのFの距離は14であるので、我々はこれらのために14+10=24または14+14=28を埋めることになるでしょう。 ただし、BとEはすでに開始までの距離が短くなっているため、テーブルレコードは更新されません。 これにより、更新される5つの頂点が残り、C、I、およびKは28を取得し、GおよびJは開始からの距離に対して24を取得します。 次に、これらの頂点の発見的距離ごとにピタゴラスの定理を使用し、それらの合計を計算し、最後に更新された頂点の前の頂点列に”F”を追加します。
Fは完全であり、閉じたセットに移動され、開いているセット内のどの頂点が最小の合計を持つかに基づいて新しい現在の頂点が選択されます。
Fは完全であり、閉じたセットに移動され、新しい現在の頂点が選択されます。 それは非常に近いですが、Kは10分の1です（そして、はい、これは丸めの違いのためですが、この場合、それは良いタイブレーカーであることが判明します）。 Kは調べる新しい頂点になるので、その近傍を見てみましょう。/div>
そのうちの3つはすでに開集合に含まれているので、最後の2つのhとLも開集合に追加されます。 今、私たちは開始からの距離を計算します。 Kの開始からの距離は28であるため、G、J、およびLの場合は28+10=38、Hの場合は28+14=42で作業しますが、GとJはすでに開始までの距離が小さいため、更新 それぞれのヒューリスティック距離を見つけ、それらの合計を計算し、更新された以前の各頂点に”K”を追加します。
Kは完全で閉じたセットに移動され、最小の合計を持つオープンの次の頂点はL、私たちの目的地です！Div>は現在の頂点であり、アルゴリズムは終了し、テーブルを使用して開始点までのパスをトレースできます。
- lの前の頂点はk
- kの前の頂点はf
- f’前の頂点はa、始したがって、これは最短パスがa>F>K>Lであることを意味します。
結果を分析する
Dijkstraのアルゴリズムと比較すると、A*はその背後にかなり混乱を残しています。 いくつかの奇妙な点を見てみましょう。 まず、頂点Cとその開始点までの距離を見てください：28。 AとCは互いに2つの水平方向の移動しかないため、最短距離は20でなければならないため、これは奇妙に思えます。 今、CはAへの最短経路がFを通る2つの対角移動であると考えているようです。
Dijkstraのアルゴリズムが終了すると、開始点からの距離の非常に完 逆に、A*のテーブルには間違った値があり、頂点Dが完全に欠落していますが、Dijkstraのものと同じ答えが得られ、はるかに高速でした。 Dijkstra’sは、最短経路を見つけたと宣言する前に12個の頂点をすべて見たいと思っていました。a*は正しい経路を見つける前に4を見る必要がありました。 この速度の変化は、私たちが使用していたヒューリスティックのためです：できるだけ頻繁に、私たちは目的地との距離を閉じたいと思っていました。 Wikipediaのヒューリスティックの定義に戻ると、A*は完全性を速度と交換しました。
別の小さな例を試してみましょうが、目的地への途中で障害物があります。Div>
開始点は左上の頂点であり、*右下の頂点への最短パスを見つけようとしています。 黒い四角はグラフ内のギャップを表しており、横断することはできません。 A*が”常に目的地に近づく”というヒューリスティックに従っている場合、それらの黒い四角はそれを行き止まりに導くでしょう。div>
この時点で、A*は最小の合計を探しますこれは、開始頂点のすぐ下と右側の正方形になります。 *は両方のパスを探索しますが、下向きのパスは別の行き止まりに実行され、右向きのパスは黒い正方形の周りの道を見つけるでしょう。 これとは少し違った方法で再生されるかもしれませんが、これがa*がこのシナリオをどのように処理したかを仮定しましょう。 行き止まりに引っ張られても、戻って別のパスを見つけることができ、すべての頂点を見る必要はありませんでした（右上の頂点は再びスキップされ これは、*starが絶対最悪の状態で実行されている場合、基本的にDijkstraの通常のパフォーマンスと同じくらい高速であることを意味します。 各アルゴリズムには完全に有効なユースケースがありますが、経路探索と最短経路の検索の点では、A*がより良い選択です。