A* search algorithm

A* (pronounced "A-star") is a graph traversal and pathfindingalgorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency.^[1] Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal.

One major practical drawback is its ${\displaystyle O(b^{d})}$space complexity where d is the depth of the shallowest solution (the length of the shortest path from the source node to any given goal node) and b is the branching factor (the maximum number of successors for any given state). In practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance,^[2] as well as by memory-bounded approaches; however, A* is still the best solution in many cases.^[3]

Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.^[4] It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.

The A* algorithm terminates once it finds the shortest path to a specified goal, rather than generating the entire shortest-path tree from a specified source to all possible goals.

A* は、自身の行動を計画できる移動ロボットを構築することを目的としたShakey プロジェクトの一環として作成されました。Nils Nilsson は当初、 Shakey の経路計画にグラフ トラバーサー アルゴリズム^{[ 5 ]を使用することを提案しました。 [ 6 ]}グラフ トラバーサーは、ノードnから目標ノードまでの推定距離であるヒューリスティック関数h ( n )によってガイドされます。開始ノードからnまでの距離であるg ( n )は完全に無視されます。Bertram Raphael は、合計g ( n ) + h ( n )を使用することを提案しました。^{[ 7 ]} Peter Hart は、現在ヒューリスティック関数の許容性と一貫性と呼ばれる概念を発明しました。A* は当初、経路のコストがそのコストの合計である場合に最小コスト経路を見つけるために設計されましたが、コスト代数の条件を満たすあらゆる問題に対して最適な経路を見つけるために A* を使用できることが示されています。^{[ 8 ]}

1968年のオリジナルのA*論文^{[ 4 ]}には、ヒューリスティック関数が一貫性があり、A*のタイブレーク規則が適切に選択されていれば、A *のようなアルゴリズム^{[ a ]はA*よりも少ないノードを展開することはできないという定理が含まれていました。数年後に「訂正」 [ 9 ]}が発表され、一貫性は必要ないという主張がなされましたが、これは1985年にDechterとPearlによるA*の最適性（現在は最適効率と呼ばれている）に関する決定的な研究で誤りであることが示されました。この研究では、許容可能だが一貫性のないヒューリスティックを持つA*が、別のA*のようなアルゴリズムよりも任意に多くのノードを展開する例が示されました。^{[ 10 ]}

A*アルゴリズムは、情報に基づく探索アルゴリズム、または最良優先探索アルゴリズムであり、重み付きグラフを用いて定式化されます。グラフの特定の開始ノードから出発し、与えられた目標ノードまでの経路のうち、コストが最小（移動距離が最小、所要時間が最短など）となる経路を見つけることを目指します。このアルゴリズムは、開始ノードから始まる経路のツリーを維持し、目標ノードに到達するまで、一度に1つのエッジずつ経路を拡張していくことでこれを実現します。

メインループの各イテレーションで、A* はどのパスを延長するかを決定する必要があります。これは、パスのコストと、パスを目標まで完全に延長するために必要なコストの推定値に基づいて行われます。具体的には、A* は、コストを最小化するパスを選択します。

${\displaystyle f(n)=g(n)+h(n)}$

ここで、 nはパス上の次のノード、g ( n )は開始ノードからnまでのパスのコスト、h ( n )はnから目標までの最も安いパスのコストを推定するヒューリスティック関数です。ヒューリスティック関数は問題固有のものです。

A* の典型的な実装では、優先度付きキューを使用して、展開する最小 (推定) コストのノードを繰り返し選択します。この優先度付きキューは、オープン セット、フリンジ、またはフロンティアとして知られています。アルゴリズムの各ステップで、 f ( x )値が最も低いノードがキューから削除され、その隣接ノードのf値とg値がそれに応じて更新され、これらの隣接ノードがキューに追加されます。削除されたノード (つまり、すべてのフリンジ ノードの中でf値が最も低いノード) が目標ノードになるまで、アルゴリズムは続きます。^{[ b ]}目標のf値は、許容ヒューリスティックでは目標でのhがゼロであるため、最短経路のコストにもなります。

これまで説明したアルゴリズムは、最短経路の長さしか示しません。実際の手順の順序を求めるには、経路上の各ノードが先行ノードを追跡するようにアルゴリズムを簡単に修正できます。このアルゴリズムを実行すると、終了ノードは先行ノードを指し示すようになり、あるノードの先行ノードが開始ノードになるまで、このプロセスが繰り返されます。

例えば、地図上で最短ルートを探す場合、h ( x )はゴールまでの直線距離を表すことがあります。これは、物理的に見て任意の2点間の最小距離だからです。ビデオゲームのグリッドマップの場合、利用可能な移動方法（4方向または8方向）に応じて、タクシー距離またはチェビシェフ距離を使用する方が適しています。

ヒューリスティックh が、グラフのすべてのエッジ( x , y )に対して追加条件h ( x ) ≤ d ( x , y ) + h ( y )を満たす場合 (ここでd はそのエッジの長さを表す)、hは単調または一貫性があると呼ばれます。一貫性のあるヒューリスティックを使用すると、A* はどのノードも 1 回以上処理することなく最適なパスを見つけることが保証され、A* はコストを削減したDijkstra アルゴリズムd' ( x , y ) = d ( x , y ) + h ( y ) - h ( x )を実行することと同等になります。^{[ 11 ]}

擬似コード

以下の擬似コードは、そのアルゴリズムを説明するものです。

function reconstruct_path ( came_from , current ) total_path := {current} while current in came_from . keys : current := came_from [ current ] total_path . prepend ( current ) return total_path// A* は開始ノードから目標ノードまでの経路を見つけます。// h はヒューリスティック関数です。h(n) はノード n から目標ノードに到達するまでのコストを推定します。function a_star ( start , goal , h ) // 再拡張が必要になる可能性のある発見されたノードのセット。// 最初は開始ノードのみがわかっています。// これは通常、ハッシュセットではなく、最小ヒープまたは優先度キューとして実装されます。open_set := {start}// ノード n の場合、came_from[n] は、現在知られている開始ノードから n までの最短経路で、nの直前のノードです。came_from :=空のマップ// ノード n の場合、g_score[n] は、start から n までの最も安いパスの現在わかっているコストです。g_score :=デフォルト値がInfinityのマップg_score [ start ] := 0// ノード n の場合、f_score[n] := g_score[n] + h(n) となります。f_score[n] は、n を経由する場合に開始から終了までのパスがどれだけ安価になるかについての現在の最良の推測を表します。f_score : =デフォルト値がInfinityのマップf_score [ start ] := h ( start )while open_set is not empty // open_set が最小ヒープまたは優先度キューの場合、この操作は O(Log(N)) 時間で実行できますcurrent : = open_set内でf_score []値が最も低いノードif current = goal return reconstruct_path ( came_from , current )open_set.remove ( current ) for each neighbor of current // d(current,neighbor) is the weight of the edge from current to neighbor // tentative_g_score is the distance from start to the neighbor through current tentative_g_score := g_score [ current ] + d ( current , neighbor ) if tentative_g_score < g_score [ neighbor ] // this path to neighbor is better than which previous one. Record it! came_from [ neighbor ] : = current g_score [ neighbor ] : = tentative_g_score f_score [ neighbor ] := tentative_g_score + h ( neighbor ) if neighbor not in open_set open_set.add ( neighbor )// オープンセットは空だが、目標は達成されなかったため、失敗を返す

注記:この擬似コードでは、ノードが 1 つのパスで到達され、 から削除されopen_set、その後、より安価なパスで到達された場合、再び に追加されます。これは、ヒューリスティック関数が許容可能だが 一貫性open_setがない場合に返されるパスが最適であることを保証するために不可欠です。ヒューリスティックが一貫性がある場合、へのパスからノードが削除されると、それが最適であることが保証されるため、ノードに再び到達すると、テスト ' ' は常に失敗します。ここで実装されている擬似コードは、 A* のグラフ探索バージョンと呼ばれることがあります。^{[ 12 ]}これは、ノードを に戻すための' ' テストがないバージョンとは対照的です。このバージョンは、A* の木探索バージョンと呼ばれることがあり、最適性を保証するために一貫性のあるヒューリスティックが必要です。open_settentative_g_score < g_score[neighbor]tentative_g_score < g_score[neighbor]open_set

許容基準は最適な解経路を保証する一方で、A*アルゴリズムが最適な経路を見つけるために、同等に優れたすべての経路を検証する必要があることも意味します。近似最短経路を計算するには、許容基準を緩和することで最適性を犠牲にして探索を高速化できます。多くの場合、この緩和に制限を設けて、解経路が最適な解経路の (1 + ε ) 倍よりも悪くならないことを保証したいと考えます。この新しい保証は、 ε許容と呼ばれます。

ε許容アルゴリズムはいくつか存在する。

• 重み付き A*/静的重み付け。^{[ 18 ]} h _a ( n ) が許容可能なヒューリスティック関数である場合、重み付き A* 探索では、ヒューリスティック関数としてh _w ( n ) = ε h _a ( n )、ε > 1を使用し、通常どおり A* 探索を実行します (展開されるノードが少ないため、最終的にはh _{a を}使用するよりも高速になります)。したがって、探索アルゴリズムによって見つかったパスのコストは、グラフ内の最小コストパスの最大ε倍になります。 ^{[ 19 ]}
• 凸上向き/下向き放物線 (XUP/XDP)。^{[ 20 ]}重み付きA*のコスト関数を修正して、最適性をスタート地点またはゴール地点に近づける。XDPはスタート地点に近いほぼ最適なパスを生成し、XUPパスはゴール地点に近いほぼ最適なパスを生成する。どちらも${\displaystyle \epsilon }$全体的に見て最適な経路。

  ${\displaystyle f_{\text{XDP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+(2\epsilon -1)+{\sqrt {(g(n)-h(n))^{2}+4\epsilon g(n)h(n)}}\ \right]}$。

  ${\displaystyle f_{\text{XUP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+h(n)+{\sqrt {(g(n)+h(n))^{2}+4\epsilon (\epsilon -1)h(n)^{2}}}\ \right]}$。

• 区分的上昇/下降曲線 (pwXU/pwXD)。^{[ 21 ]} XUP/XDP に似ていますが、放物線の代わりに区分的関数を使用します。解の経路も${\displaystyle \epsilon }$最適。

  ${\displaystyle f_{\text{pwXD}}(n)={\begin{cases}g(n)+h(n),&{\text{if }}h(n)>g(n)\\g(n)+(2\epsilon -1)h(n)/\epsilon ,&{\text{if }}h(n)\leq g(n)\end{cases}}}$

  ${\displaystyle f_{\text{pwXU}}(n)={\begin{cases}g(n)/(2\epsilon -1)+h(n),&{\text{if }}g(n)<(2\epsilon -1)h(n)\\(g(n)+h(n))/\epsilon ,&{\text{if }}g(n)\geq (2\epsilon -1)h(n)\end{cases}}}$

• 動的重み付け^{[ 22 ]}はコスト関数を使用します${\displaystyle f(n)=g(n)+(1+\バレプシロン w(n))h(n)}$⁠、そこで${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{それ以外の場合}}\end{cases}}}$、そして、$d(n)$は探索の深さであり、 Nは解の経路の予想される長さです。
• サンプリングされた動的重み付け^{[ 23 ]}は、ノードのサンプリングを使用してヒューリスティックエラーをより適切に推定し、バイアスを取り除きます。
• ${\displaystyle A_{\varepsilon }^{*}}$^{[ 24 ]}は2つのヒューリスティック関数を使用する。1つ目は候補ノードを選択するために使用されるFOCALリストであり、2つ目はFOCALリストから最も有望なノードを選択するために使用されるh _{Fである。}
• A _ε ^{[ 25 ] は}、関数 ⁠ でノードを選択します。${\displaystyle Af(n)+Bh_{F}(n)}$⁠、ここでAとBは定数です。ノードを選択できない場合、アルゴリズムは関数を使用してバックトラックします。${\displaystyle Cf(n)+Dh_{F}(n)}$ここで、 CとDは定数である。
• AlphA* ^{[ 26 ]}は、最近拡張されたノードを優先することで深さ優先探索を促進しようとします。AlphA* はコスト関数を使用します。${\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}$、 どこ${\displaystyle w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}}$λとΛは定数で、${\displaystyle \lambda \leq \Lambda }$π ( n )はnの親であり、ñは最近展開されたノードです。

ヒューリスティック探索アルゴリズムであるA*の性能は、ヒューリスティック関数の質に大きく左右される。${\textstyle h(n)}$ヒューリスティックが目標に対する真のコストに近似していれば、A*アルゴリズムはノード展開の数を大幅に削減できる。一方、不適切なヒューリスティックは、多くの不必要な展開につながる可能性がある。

最悪の場合

最悪の場合、A*はすべてのノードを展開します${\textstyle n}$そのために${\textstyle f(n)=g(n)+h(n)\leq C^{*}}$、 どこ${\textstyle C^{*}}$これは最適な目標ノードのコストです。

これ以上悪くなることはない

ノードがあると仮定します${\textstyle N'}$オープンリストで${\textstyle f(N')>C^{*}}$、そしてそれは次に展開されるノードです。目標ノードには${\textstyle f(goal)=g(goal)+h(goal)=g(goal)=C^{*}}$、 そして${\textstyle f(N')>C^{*}}$目標ノードはf値が低くなり、展開される前に${\textstyle N'}$したがって、A* はノードを拡張しません。${\textstyle f(n)>C^{*}}$。

これ以上良くできない理由

より少ないノードを展開する最適なアルゴリズムが存在すると仮定します。${\textstyle C^{*}}$最悪の場合、同じヒューリスティックを使用します。つまり、何らかのノードが存在する必要があります。${\textstyle N'}$そのため${\textstyle f(N')<C^{*}}$しかし、アルゴリズムはそれを展開しないことを選択する。

次に、コストの新しいエッジが追加された修正グラフを考えてみましょう。${\textstyle \varepsilon }$（と${\textstyle \varepsilon >0}$) が追加されます${\textstyle N'}$目標に向かって。もし${\textstyle f(N')+\varepsilon <C^{*}}$すると新しい最適経路は${\textstyle N'}$しかし、アルゴリズムは依然として拡張を回避しているため${\textstyle N'}$そうすると、新たな最適経路を見失い、最適性を損なうことになる。

したがって、A* を含む最適なアルゴリズムでは、ノード数を減らすことはできません。${\textstyle C^{*}}$最悪の場合。

数学的表記法

A*の最悪ケースの複雑さは、しばしば次のように表現されます。${\textstyle O(b^{d})}$、 どこ${\displaystyle b}$は分岐係数であり、${\textstyle d}$は最も浅いゴールの深さです。これは大まかな直感にはなりますが、A* の実際の動作を正確に捉えているわけではありません。

より正確な境界では、ノードの数を考慮します。${\textstyle f(n)\leq C^{*}}$。 もし${\displaystyle \varepsilon }$は、${\textstyle f}$-異なるノード間のコストを考慮すると、A*は最大で以下まで拡張される可能性があります。

${\displaystyle O\left({\frac {C^{*}}{\varepsilon }}\right)}$

これは、最悪の場合における時間計算量と空間計算量の両方を表しています。

A* は、ビデオゲームなどのアプリケーションにおける一般的な経路探索問題によく使用されますが、元々は汎用グラフ探索アルゴリズムとして設計されました。 ^{[ 4 ]}自然言語処理における確率的文法を用いた構文解析 問題など、さまざまな問題に応用されています。^{[ 27 ]} その他には、オンライン学習を用いた情報検索などがあります。^{[ 28 ]}

A*が貪欲な最良優先探索アルゴリズムと異なる点は、既に移動したコスト/距離g ( n )を考慮に入れることです。

ダイクストラ法の一般的な変種の中には、ヒューリスティックがA*アルゴリズムの特殊なケースと見なせるものがある。${\displaystyle h(n)=0}$すべてのノードについて。^{[ 13 ] [ 14 ]}ダイクストラ法とA*法はどちらも動的計画法の特殊なケースである。^{[ 29 ]} A*法自体は分岐限定法 の一般化の特殊なケースである。^{[ 30 ]}

A*はビームサーチと似ていますが、ビームサーチは探索するパスの数に制限を設けています。^{[ 31 ]}

• いつでもA* ^{[ 32 ]}
• ブロックA*
• D*
• フィールドD*
• フリンジ
• 福利厚生貯蓄口座A*（FSA*）
• 一般化適応型A*アルゴリズム（GAA*）
• 漸進的ヒューリスティック探索
• 縮小A* ^{[ 33 ]}
• 反復深化A*（IDA*）
• ジャンプポイント検索
• 生涯プランニング A* (LPA*)
• 新しい双方向A*（NBA*）^{[ 34 ]}
• 簡略化されたメモリ制限付きA*（SMA*）
• シータ*

A* は双方向探索アルゴリズムにも適用できますが、停止基準には特別な注意が必要です。^{[ 35 ]}

• 任意の角度での経路計画– グラフのエッジに沿って移動するだけでなく、任意の角度をとることができる経路を探索します。
• 幅優先探索– グラフのノードを探索するアルゴリズム 
• 深さ優先探索– グラフのノードを探索するアルゴリズム 
• ダイクストラ法– 最短経路を見つけるためのアルゴリズム 

• Nilsson, NJ (1980).人工知能の原理. パロアルト、カリフォルニア州: Tioga Publishing Company. ISBN 978-0-935382-01-3。
• ウォルシュ、トビー。『人工知能の最短の歴史』

• A*アルゴリズムの派生アルゴリズムで、階層型経路探索A*（HPA*）と呼ばれる。
• Brian Grinstead。「JavaScript による A* 探索アルゴリズム (更新版)」。2020 年 2 月 15 日のオリジナルからアーカイブ済み。2021年2 月 8 日取得。