1. 序章

最近、任意の2点間の最短ルートを見つける方法として、ダイクストラのアルゴリズムを調べました。 ここでは、これをより効率的に拡張したA*アルゴリズムを見ていきます。

2. A*アルゴリズム

A *は、ダイクストラのアルゴリズムに対する比較的単純な調整であり、代わりに最良優先探索になります。

これは、ノードごとに2つのスコアリングメカニズムを持つことで機能します。 1つは、ダイクストラのアルゴリズムで使用されるものと同じです。 2つ目は、ノードがターゲットノードにどれだけ近いかを示すヒューリスティックスコアです。 次に、これらを使用して、各ノードに対して2つの異なるスコアを保存します。現在のルートでノードに到達するためのスコアと、次にアクセスするノードを選択するためのスコアです。

これは、アルゴリズムの動作方法に微妙ですが重要な影響を及ぼします。 これは、ターゲットに近いノードを常に優先し、遠くにあるノードへのアクセスを避けることを意味します。 これにより、各ステップで正しい一般的な方向に向かうため、アルゴリズムがより効率的になります。

興味深いことに、常に0を返すヒューリスティックがある場合、A*アルゴリズムはダイクストラのアルゴリズムと同じです。 この1つのスコアは、2つの間の唯一の違いです。

2.1. 擬似コード

アルゴリズムのコアは、ダイクストラのアルゴリズムで見たものと非常によく似ています。 追加のスコアリングヒューリスティックを考慮する必要があります。

nodeWithLowestScore アルゴリズムは、前の記事のアルゴリズムと同じですが、代わりにheuristicScoreで動作します。 次に、ヒューリスティックに基づいて、次の最良のノードであると思われるノードを選択します。 calculateScoreとbuildPathも以前と同じであり、各ノードに到達するための実際のスコアに基づいてグラフを通る最適なルートを提供します。

2.2. ヒューリスティックスコア

欠落している唯一の部分は、ヒューリスティックです。 これは、パスを見つけているグラフのタイプに関連しているため、簡単に説明できるものではありません。 唯一の要件は、ヒューリスティックスコアと実際のスコアが互いに一致していることです。

たとえば、地理グラフでは、これはグラフ内のノード間の物理的な距離に基づいている場合があります。 実際のスコアは、2つのノード間のルート上のメートル数であり、ヒューリスティックスコアは、2つのノード間の直線上のメートル数である可能性があります。

これにより、より効率的なパスが生成されることを期待して、ターゲットに近づくステップに優先順位が付けられます。 より良い選択がない場合にのみ、目標から離れ始めます。

3. A*のプロパティ

A *アルゴリズムにはいくつかの特性があり、汎用のパスファインディングアルゴリズムに最適です。

3.1. 終了と完全性

終了の特性は、アルゴリズムが停止状態に到達することを意味します。つまり、解決策を見つけるか、進行できなくなるポイントに到達します。

完全性の特性は、解決策が見つかった場合、アルゴリズムが常に解決策を見つけることを意味します。

ノード間のすべての接続に負でないコストがかかる有限グラフで作業している場合、A*アルゴリズムは終了と完了の両方が保証されます。

無限グラフで作業している場合、解が見つかることが保証される特定の条件がありますが、これらが満たされない場合、アルゴリズムは決して終了しない可能性があります。

3.2. 許容性

ヒューリスティックは、同じルートの最適なコストよりも高いコストを返さない場合に許容されると見なされます。 たとえば、2つのノード間の最も効率的なルートのコストが n の場合、許容されるヒューリスティックはこれを超えるコストを返すことはありません。

A *内で、使用されるヒューリスティックが許容可能であり、アルゴリズムが解を返す場合、この解が最適な解であることが保証されます。 ヒューリスティックが許容されない場合、アルゴリズムは最適でないルートを優先する可能性がありますが、これによって解決策が見つかるのを防ぐことはできません。

ヒューリスティックが許容できる場合は、最適なソリューションを見つけることが保証されます。 ただし、すべて同じコストのパスが複数ある場合は、それらすべてが調査されるため、全体的な処理コストが高くなります。 許容基準を緩和することで、この状況を回避できますが、全体的に悪い解決策になるリスクがあります。

代わりに、許容基準を緩和することができますが、それは特定の範囲内に限られます。 これにより、十分に最適なパスを見つけることができますが、より効率的な方法で見つけることができます。

4. 複雑

A *の時間計算量は、ヒューリスティック関数の品質によって異なります。 最悪の場合、アルゴリズムは O（b ^ d）になります。ここで、 b は分岐係数、つまり各ノードからのエッジの平均数、および d は、結果のパス上のノードの数です。

ヒューリスティック関数が優れているほど、これらのノードにアクセスする必要が少なくなるため、複雑さが低下します。 ヒューリスティック関数の結果は、有効な分岐係数、つまりアクセスする必要のある各ノードからのエッジの平均数として説明できます。

ダイクストラのアルゴリズムには、全体的な分岐係数とまったく同じ有効な分岐係数があります。 完全に最適なヒューリスティック関数により、 1 の有効な分岐係数が得られます。つまり、すべてのノードから、アクセスできるエッジは1つだけになります。 現実はおそらくその間のどこかにあり、このスケールのどこが検索の時間計算量を決定するでしょう。

標準A*のスペースの複雑さは、常に O（b ^ d）です。これは、グラフ内のすべてのノードを常に追跡する必要があるためです。 これを回避するための最適化があります。これは、関連性が高くなったときにアルゴリズムにノードを追加するか、関連性が低くなったときにノードを忘れることによって行うことができます。 それでも、これらはすべて、全体的な出力に潜在的な影響を及ぼします。

5. 結論

ここでは、A *アルゴリズムがどのように機能するかを調査しました。これには、場合によっては機能を改善または悪化させる要因の詳細も含まれます。 これまでに実用的な実装を見てきました。