A*検索アルゴリズム

クラス	検索アルゴリズム
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|E|\log |V|)=O(b^{d})}$
最悪の場合の 空間複雑度	${\displaystyle O(|V|)=O(b^{d})}$

A*（「エースター」と発音）は、その完全性、最適性、最適効率性により、コンピュータサイエンスの多くの分野で使用されているグラフトラバーサルおよび経路探索アルゴリズムです。 ^[1]重み付きグラフ、ソースノード、およびゴールノードが与えられた場合、アルゴリズムはソースからゴールまでの最短パス（指定された重みに関して）を見つけます。

実用的な大きな欠点の 1 つは、空間計算量です。ここで、dはソリューションの深さ (最短経路の長さ)、bは分岐係数(状態ごとの後続ノードの平均数)であり、生成されたすべてのノードをメモリに格納するためです。したがって、実用的な旅行ルーティング システムでは、グラフを前処理してパフォーマンスを向上させるアルゴリズムやメモリ制限アプローチの方が一般的に優れています^が、A* は多くの場合依然として最適なソリューションです。^[3]${\displaystyle O(b^{d})}$

スタンフォード研究所（現SRIインターナショナル）のピーター・ハート、ニルス・ニルソン、バートラム・ラファエルは1968年に初めてこのアルゴリズムを発表しました。 ^[4]これはダイクストラのアルゴリズムの拡張と見ることができます。A*は、探索を導くために ヒューリスティックスを使用することで、より良いパフォーマンスを実現します。

ダイクストラのアルゴリズムと比較すると、A* アルゴリズムは、指定されたソースから指定されたゴールまでの最短パスのみを検索し、指定されたソースからすべての可能なゴールまでの最短パス ツリーを検索しません。これは、特定のゴールに向けたヒューリスティックを使用するために必要なトレードオフです。ダイクストラのアルゴリズムでは、最短パス ツリー全体が生成されるため、すべてのノードがゴールとなり、特定のゴールに向けたヒューリスティックは存在しません。

A*は、自らの行動を計画できる移動ロボットを作ることを目的としたShakey プロジェクトの一環として作成された。Nils Nilsson は、Shakey の経路計画にGraph Traverserアルゴリズム^{[5]を使用することを最初に提案した。 [6] Graph Traverser は、ノード}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* は開始からゴールまでの最小コストのパスを返すことが保証されます。

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

これまで説明したアルゴリズムは、最短パスの長さのみを示します。実際のステップのシーケンスを見つけるには、パス上の各ノードがその前のノードを追跡するようにアルゴリズムを簡単に修正できます。このアルゴリズムを実行すると、終了ノードはその前のノードを指し、いずれかのノードの前ノードが開始ノードになるまで続きます。

たとえば、地図上で最短ルートを検索する場合、h ( x ) は、物理的に任意の 2 点間の最短距離であるため、目的地までの直線距離を表すことがあります。ビデオ ゲームのグリッド マップの場合、利用可能な移動のセット (4 方向または 8 方向) に応じて、タクシー距離またはチェビシェフ距離を使用する方が適切になります。

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

次の疑似コードはアルゴリズムを説明しています。

関数reconstruct_path ( cameFrom , current ) total_path := {current} while current in cameFrom . Keys : current := cameFrom [ current ] total_path . prepend ( current ) return total_path  
      
       
          
        
     

// A* はスタートからゴールまでのパスを見つけます。
// h はヒューリスティック関数です。h(n) はノード n からゴールに到達するためのコストを推定します。
function A_Star ( start , goal , h ) // 発見されたノードのセットは (再) 拡張する必要がある可能性があります。// 最初は、スタートノードのみがわかっています。// これは通常、ハッシュセットではなく、最小ヒープまたは優先キューとして実装されます。openSet := {start}   
    
    
    
      

    
// ノード n の場合、 cameFrom [n] は、現在知られている開始からn までの最も安価なパス上の直前のノードです。cameFrom :=空のマップ    
        

    
// ノード n の場合、 gScore [n] は開始から n までの最も安価なパスの現在わかっているコストです。gScore :=デフォルト値がInfinityのマップgScore [ start ] := 0           
      

    // ノード n の場合、fScore[n] := gScore[n] + h(n) です。fScore[n] は、
n を通過するパスが開始から終了までどのくらい安くなるかについての現在の最善の推測を表します。fScore : = map 、デフォルト値はInfinity fScore [ start ] := h ( start )    
           
      

    openSetが空でないとき// この操作は、openSet が最小ヒープまたは優先度キューの場合、O(Log(N)) 時間で実行できます。current := openSet内でfScore []値が最も低いノード。current = goalの場合、reconstruct_path ( cameFrom 、current )を返します。    
        
                  
           
              

        openSet . Remove ( current )を
currentの各近傍に対して実行します// d(current,neighbor) は、current から近傍へのエッジの重みです// tentative_gScore は、start から近傍まで、current を通って距離ですtentative_gScore := gScore [ current ] + d ( current , neighbor ) if tentative_gScore < gScore [ neighbor ] // この近傍へのパスは、以前のパスよりも優れています。記録してください。cameFrom [ neighbor ] := current gScore [ neighbor ] := tentative_gScore fScore [ neighbor ] := tentative_gScore + h ( neighbor ) if neighbor がopenSetにない場合openSet . add ( neighbor )            
            
            
                 
               
                
                  
                  
                    
                    
                    

    // オープンセットは空ですが、目標には到達しませんでした。
失敗を返します。     

注意:この擬似コードでは、あるパスでノードに到達し、openSet から削除され、その後、より安価なパスで到達した場合、そのノードは再び openSet に追加されます。これは、ヒューリスティック関数が許容されるが 一貫性がない場合に、返されるパスが最適であることを保証するために不可欠です。ヒューリスティックが一貫している場合、ノードが openSet から削除されると、そのノードへのパスが最適であることが保証されるため、そのノードに再び到達すると、テスト ' tentative_gScore < gScore[neighbor]' は常に失敗します。

A* アルゴリズムの実行例。ノードは道路で接続された都市で、h(x) はターゲット ポイントまでの直線距離です。

キー:緑: スタート; 青: ゴール; オレンジ: 訪問済み

A* アルゴリズムは現実世界で応用できます。この例では、エッジは鉄道で、h(x) はターゲットまでの大圏距離(球面上の最短距離) です。このアルゴリズムは、ワシントン DC とロサンゼルス間の経路を検索します。

A* 実装のパフォーマンスに大きく影響する可能性のある、単純な最適化や実装の詳細がいくつかあります。最初に注意すべき詳細は、優先キューが同点を処理する方法が、状況によってはパフォーマンスに大きな影響を与える可能性があるということです。同点が解消され、キューがLIFO方式で動作する場合、A* は等コスト パス間の深さ優先探索のように動作します(複数の同等に最適なソリューションを探索することを回避します)。

検索の最後にパスが必要な場合、各ノードにそのノードの親への参照を保持するのが一般的です。検索の最後に、これらの参照を使用して最適なパスを回復できます。これらの参照が保持されている場合、同じノードが優先キューに複数回表示されないことが重要になります (各エントリはノードへの異なるパスに対応し、それぞれコストが異なります)。ここでの標準的なアプローチは、追加しようとしているノードがすでに優先キューに表示されているかどうかを確認することです。表示されている場合、優先度と親ポインタは、より低コストのパスに対応するように変更されます。標準的なバイナリ ヒープベースの優先キューは、その要素の 1 つを検索する操作を直接サポートしていませんが、要素をヒープ内の位置にマップするハッシュ テーブルで拡張して、この優先度を下げる操作を対数時間で実行できるようにすることができます。あるいは、フィボナッチ ヒープは、同じ優先度を下げる操作を一定の償却時間で実行できます。

均一コスト探索アルゴリズムの別の例として、ダイクストラのアルゴリズムは、すべてのxに対して⁠ ⁠ と${\displaystyle h(x)=0}$なる A* の特殊なケースと見なすことができます。^{[12] [13]}非常に大きな値で初期化されたグローバルカウンターCがあることを考慮すると、A* を使用して一般的な深さ優先探索を実装できます。ノードを処理するたびに、その新しく発見されたすべての隣接ノードにC を割り当てます。割り当てが 1 つ終わるたびに、カウンターC を1 つ減らします。したがって、ノードが早く発見されるほど、その⁠ ⁠値は高くなります。ダイクストラのアルゴリズムと深さ優先探索はどちらも、各ノードに⁠ ⁠値を含めずに、より効率的に実装できます。 ${\displaystyle h(x)}$${\displaystyle h(x)}$

非負の辺の重みを持つ有限グラフでは、A* は終了することが保証されており、完全です。つまり、解（スタートからゴールまでのパス）が存在する場合は常にそれを見つけます。有限の分岐係数と、ゼロから制限された辺コスト（ある固定値に対して）を持つ無限グラフでは、解が存在する場合にのみ A* が終了することが保証されます。^[1]${\textstyle d(x,y)>\varepsilon >0}$${\displaystyle \epsilon }$

検索アルゴリズムは、最適なソリューションを返すことが保証されている場合、許容可能と言われます。A* で使用されるヒューリスティック関数が許容可能であれば、A* は許容可能です。この直感的な「証明」は次のとおりです。

ノードが訪問済みで、開集合にない場合は、そのノードは閉じていると呼びます。開集合からノードを削除すると、そのノードは閉じます。以下で証明する A* アルゴリズムの基本的な特性は、⁠ ⁠${\displaystyle n}$が閉じている場合、⁠ ⁠ は${\displaystyle f(n)}$スタートからゴールまでの実際の距離の楽観的な推定値 (下限) であるということです。したがって、ゴールノード⁠ ⁠${\displaystyle g}$が閉じている場合、⁠ ⁠ は${\displaystyle f(g)}$実際の距離以上ではありません。一方、これはゴールまでのパスの長さにヒューリスティック項を加えたものなので、実際の距離以上です。

ここで、ノード⁠ ⁠${\displaystyle n}$が閉じている場合は常に、⁠ ⁠ が${\displaystyle f(n)}$楽観的な推定値であることがわかります。開集合が空でない場合は常に、ゴールへの最適パス上に少なくとも 1 つのノード⁠ ⁠があり、その場合${\displaystyle n}$⁠ ⁠ が${\displaystyle g(n)}$スタートからの実際の距離であることがわかります。その場合、⁠ ⁠${\displaystyle g(n)}$ + ⁠ ⁠ は${\displaystyle h(n)}$ゴールまでの距離を過小評価し、したがって閉じた頂点に選択された小さい値も過小評価されるためです。⁠ ⁠ を${\displaystyle P}$スタートからゴールまでの最適パスとします。⁠ ⁠ を${\displaystyle p}$⁠ ⁠${\displaystyle P}$上の最後の閉じたノードとします。その場合⁠ ⁠ ⁠ が${\displaystyle g(p)}$スタートからゴールまでの実際の距離です (スタートはそのような頂点の 1 つです)。⁠ ⁠内の次のノードは、 ${\displaystyle P}$⁠ ⁠が閉じたときに更新されたため正しい⁠ ⁠${\displaystyle g}$値を持ち、閉じていないため開いています。 ${\displaystyle p}$

アルゴリズム A が問題集合P上の代替アルゴリズム集合Altsに関して最適に効率的であるとは、問題集合P内のすべての問題 P とAlts内のすべてのアルゴリズム A′に対して、問題集合 P を解決するために A によって拡張されるノード集合が問題集合 P を解決するために A′ によって拡張されるノード集合のサブセット (等しい可能性もある) である場合をいう。A* の最適効率に関する決定的な研究は、Rina Dechter と Judea Pearl によるものである。^{[10]彼らは、} AltsとP のさまざまな定義を、 A* のヒューリスティックが単に許容可能であるか、一貫性があり許容可能であるかと組み合わせて検討した。彼らが証明した最も興味深い肯定的な結果は、一貫性のあるヒューリスティックを持つ A* は、すべての「非病的な」検索問題に対するすべての許容可能な A* のような検索アルゴリズムに関して最適に効率的であるということである。大まかに言えば、彼らの非病的な問題の概念は、現在「タイブレークまで」という意味である。この結果は、A* のヒューリスティックが許容可能だが一貫性がない場合には成立しません。その場合、Dechter と Pearl は、いくつかの非病理学的問題で A* よりも任意の少ないノードを拡張できる許容可能な A* のようなアルゴリズムが存在することを示しました。

最適な効率は、ノード拡張の数（A* のメインループの反復回数）ではなく、拡張されるノードのセットに関するものです。使用されているヒューリスティックが許容可能だが一貫性がない場合、ノードが A* によって何度も拡張される可能性があり、最悪の場合は指数関数的に拡張される可能性があります。 ^[14] このような状況では、ダイクストラのアルゴリズムは A* を大幅に上回る可能性があります。ただし、最近の研究では、この異常なケースは、検索グラフのエッジの重みがグラフのサイズに対して指数関数的である特定の不自然な状況でのみ発生し、一貫性のない（ただし許容可能な）特定のヒューリスティックによって、A* 検索でのノード拡張の数が減少する可能性があることがわかりました。^{[15] [16]}

許容基準は最適なソリューション パスを保証しますが、同時に、A* は最適なパスを見つけるために、同等に価値のあるパスをすべて調べる必要があることも意味します。近似的な最短パスを計算するには、許容基準を緩和することで、最適性を犠牲にして検索を高速化することができます。多くの場合、この緩和を制限して、ソリューション パスが最適なソリューション パスの (1 + ε ) 倍よりも悪くないことを保証できるようにします。この新しい保証は、 ε許容と呼ばれます。

ε許容アルゴリズムは多数存在します。

• 重み付きA*/静的重み付け。^[17] h _a ( n ) が許容されるヒューリスティック関数である場合、重み付きバージョンのA*検索では、ヒューリスティック関数としてh _w ( n ) = ε h _a ( n )、ε > 1を使用し、通常どおりA*検索を実行します（展開されるノードが少ないため、最終的にはh _{a を}使用する場合よりも速くなります）。検索アルゴリズムによってこのようにして見つかったパスのコストは、グラフ内の最小コストパスのコストのε倍以下になります。 ^[18]
• 動的重み付け^[19]はコスト関数⁠ ⁠${\displaystyle f(n)=g(n)+(1+\バレプシロン w(n))h(n)}$を使用します。ここで、⁠ ⁠は探索の深さ、Nは予想される解のパスの長さです。${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$${\displaystyle d(n)}$
• サンプル動的重み付け^[20]は、ノードのサンプリングを使用して、ヒューリスティックエラーをより正確に推定し、バイアスを軽減します。
• ${\displaystyle A_{\varepsilon }^{*}}$^[21]は2つのヒューリスティック関数を使用する。1つ目は候補ノードを選択するために使用されるFOCALリストであり、2つ目は_FOCALリストから最も有望なノードを選択するために使用されるhFである。
• A _ε ^[22]は関数⁠ ⁠${\displaystyle Af(n)+Bh_{F}(n)}$（AとBは定数）を使用してノードを選択します。ノードを選択できない場合、アルゴリズムは関数⁠ ⁠${\displaystyle Cf(n)+Dh_{F}(n)}$（CとDは定数）を使用してバックトラックします。
• AlphA* ^[23]は、最近拡張されたノードを優先することで深さ優先の利用を促進しようとします。AlphA*はコスト関数を使用します。ここで、λとΛは定数で、π ( n )はnの親、ñは最も最近拡張されたノードです。${\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 }$

A*の時間計算量はヒューリスティックに依存する。探索空間が無制限の最悪のケースでは、拡張されるノードの数はソリューション（最短経路）の深さd : O ( b ^d ) の指数関数的増加となる。ここでbは分岐係数（状態ごとの後続ノードの平均数）である。 ^[24]これは、目標状態が存在し、開始状態から到達可能であることを前提としている。目標状態が存在しない場合、状態空間が無限大であれば、アルゴリズムは終了しない。

ヒューリスティック関数はA*探索の実際のパフォーマンスに大きな影響を与えます。優れたヒューリスティック関数は、情報のない探索では拡張されるb ^dノードの多くをA*が取り除くことを可能にするからです。その品質は、実効分岐係数b *で表現できます。これは、問題インスタンスに対して、拡張によって生成されるノードの数Nと解の深さを測定し、次に^{[25]を解くことで経験的に決定できます。}

${\displaystyle N+1=1+b^{*}+(b^{*})^{2}+\dots +(b^{*})^{d}.}$

優れたヒューリスティックとは、有効分岐係数が低いものです（最適値はb * = 1です）。

探索空間がツリーで、目標状態が 1 つあり、ヒューリスティック関数h が次の条件を満たす場合、 時間の計算量は多項式になります。

${\displaystyle |h(x)-h^{*}(x)|=O(\log h^{*}(x))}$

ここで、 h ^*は最適なヒューリスティック、つまりxからゴールまでの正確なコストです。言い換えると、hの誤差は、 xからゴールまでの真の距離を返す「完璧なヒューリスティック」h ^*の対数よりも速く増加することはありません。^{[18] [24]}

A*の空間計算量は、生成されたすべてのノードをメモリ内に保持するため、他のすべてのグラフ検索アルゴリズムとほぼ同じです。 ^{[1]実際には、これがA*検索の最大の欠点であることが判明し、}反復深化A*、メモリ制限A*、SMA*などのメモリ制限ヒューリスティック検索の開発につながりました。

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

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

ダイクストラ法の一般的な変種は、すべてのノードのヒューリスティックであるA*の特殊なケースと見なすことができます。^{[12] [13]}また、ダイクストラ法とA*はどちらも動的計画法の特殊なケースです。 ^{[28] A*自体は}分岐限定法 の一般化の特殊なケースです。^[29]${\displaystyle h(n)=0}$

A*はビームサーチに似ていますが、ビームサーチでは探索しなければならないパスの数に制限がある点が異なります。^[30]

• いつでもA* ^[31]
• ブロックA*
• D*
• フィールドD*
• フリンジ
• フリンジ貯蓄A* (FSA*)
• 一般化適応型 A* (GAA*)
• 増分ヒューリスティック検索
• 減少したA* ^[32]
• 反復深化 A* (IDA*)
• ジャンプポイント検索
• 生涯計画A*（LPA*）
• 新しい双方向A*（NBA*）^[33]
• 簡易メモリ制限 A* (SMA*)
• シータ*

A*は双方向探索アルゴリズムにも適応できるが、停止基準には特別な注意が必要である。^[34]

• 任意角度のパス計画、グラフのエッジに沿った移動に限定されず、任意の角度を取ることができるパスを検索します。
• 幅優先探索
• 深さ優先探索
• ダイクストラのアルゴリズム – 最短経路を見つけるアルゴリズム

• ニルソン、 NJ (1980)。人工知能の原理。カリフォルニア州パロアルト：Tioga Publishing Company。ISBN 978-0-935382-01-3。

• A* のバリエーションである階層的経路探索 A* (HPA*)
• Brian Grinstead. 「JavaScript の A* 検索アルゴリズム (更新)」。2020 年 2 月 15 日時点のオリジナルよりアーカイブ。2021年2 月 8 日閲覧。