A*

探索 > 最良優先探索 > A*

A*探索アルゴリズム

A*︵A-star、エースター︶探索アルゴリズム︵エースターたんさくアルゴリズム︶は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として﹁現時点までの距離﹂gと﹁ゴールまでの推定値﹂hの和を採用したもの。hは ヒューリスティック関数と呼ばれる。

概要

A* アルゴリズムは、﹁グラフ上でスタートからゴールまでの道を見つける﹂というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 ${\sqrt {x^{2}+y^{2}}}$${\sqrt {x^{2}+y^{2}}}$を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、15パズルにおいてはマンハッタン距離やパターンデータベース、STRIPSプランニングにおいてはFFヒューリスティック、Merge-and-Shrink、Landmark-Cut などがある。

A* アルゴリズムは、ダイクストラ法を推定値付きの場合に一般化したもので、hが恒等的に 0 である場合はもとのダイクストラ法に一致する。

A* の探索効率はhの正確さに左右される。 もしもhがまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内︵一時間、一週間、一年︶では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある︵完全性︶。 一方、hが常に正しい値 h* を返す場合、計算機は﹁迷うこと無く=分岐をすること無く﹂グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ。 現実に用いられる有用なhは、これらの中間の位置にある。

歴史

A* アルゴリズムは1968年に Peter E. Hart、Nils J. Nilsson、Bertram Raphael の三人が発表した論文の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的︵英: admissible︶と呼び、論文の数式中に 許容的なアルゴリズムの集合を Aと表し、そのAの中でも評価回数が最適になる物を A^* と表記していたためである。

A*の考え方

スタートノードから、あるノード nを通って、ゴールノードまでたどり着くときの最短経路を考える。このときこの最短経路のコストを f* (n) とおくと、

f* (n)= g* (n) + h* (n)

と置くことが出来る。ここで g* (n) はスタートノードから nまでの最小コスト、h* (n) は nからゴールノードまでの最小コストである。もし g* (n) の値と h* (n)の値を知っていれば、全体の最短経路 f* (n) は容易に求まる。しかしながら実際には g* (n) と h* (n) をあらかじめ与えることは出来ない。そこで f* (n) を次のような推定値 f (n) に置き換えることを考える。

${\displaystyle f($n)=g(n)+h(n)} $f(n)=g(n)+h(n)$
ここで g(n) はスタートノードから nまでの最小コストの推定値、h(n) は nからゴールノードまでの最小コストの推定値である。この場合 gに関しては探索の過程で更新を加えることにより g* に近づけてゆくことができるが、h* は、実際にゴールに辿り着くまでは誰にもわからない。そこで、h(n) には人間が︵ある程度妥当性を持つように︶設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、h (n) をヒューリスティック関数という。

アルゴリズムの流れ

A* のアルゴリズムの実装を以下に示す。この OPENリスト実装は後に述べるように遅いことを記しておく。

(一)スタートノード︵$S$$S$︶を作成する。また計算中のノードを格納しておくための優先度付きキュー OPENリストと、計算済みのノードを格納しておくCLOSEリストを用意する。︵名前は﹁リスト﹂だが、これらの実際のデータ構造は必ずしも連結リストである必要はない。︶

(二)ゴールは必ずしも1つである必要はないので、ゴール条件を満たすノード集合を $G$$G$と呼ぶことにする。

(三)スタートノードを Openリストに追加する、このとき ${\displaystyle g($S)} $g(S)$= $0$$0$であり ${\displaystyle f($S)} $f(S)$= ${\displaystyle h($S)} $h(S)$となる。また Closeリストは空にする。

(四)Openリストが空なら探索は失敗とする︵スタートからゴールにたどり着くような経路が存在しなかったことになる︶。

(五)Openリストに格納されているノードの内、最小の ${\displaystyle f($n)} $f(n)$を持つノード $n$$n$を1つ取り出す。同じ ${\displaystyle f($n)} $f(n)$を持つノードが複数ある場合、タイブレーク手法によりどれかのノードを選択する。

(六)$n\in G$$n\in G$ であるなら探索を終了する。それ以外の場合は $n$$n$を Close リストに移す。

(七)$n$$n$ に隣接している全てのノード︵ここでは隣接ノードを $m$$m$とおく︶に対して以下の操作を行う
(一)${\displaystyle f'($m)=g(n)+COST(n,m)+h(m)} $f'(m)=g(n)+COST(n,m)+h(m)$ を計算する、ここで $COST(n,m)$$COST(n,m)$はノードnからmへ移動するときのコストである。また ${\displaystyle g($n)} $g(n)$は ${\displaystyle g($n)=f(n)-h(n)} $g(n)=f(n)-h(n)$で求めることができる。

(二)mの状態に応じて以下の操作を行う
●mが Openリストにも Closeリストにも含まれていない場合 ${\displaystyle f($m)\leftarrow f'(m)} $f(m)\leftarrow f'(m)$としmを Openリストに追加する。このときmの親をnとして記録する。

●mが Openリストにある場合、${\displaystyle f'($m)<f(m)} $f'(m)<f(m)$ であるなら、mを Open から削除し、${\displaystyle f($m)\leftarrow f'(m)} $f(m)\leftarrow f'(m)$ に置き換え、再び Open に挿入する︵Open が正しくソートされていることを保証するため︶。また、記録してあるmの親をnに置き換える。

●mが Closeリストにある場合、${\displaystyle f'($m)<f(m)} $f'(m)<f(m)$ であるなら ${\displaystyle f($m)\leftarrow f'(m)} $f(m)\leftarrow f'(m)$としてmを Openリストに移動する。また記録してあるmの親をnに置き換える。

(八)3以降を繰り返す。

(九)探索終了後、発見されたゴール $n_{G}$$n_{G}$から親を順次たどっていくとSから ゴール $n_{G}$$n_{G}$までの最短経路が得られる。

以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では HDA*、PBFS などの並列手法が開発され、特に HDA* は768コア以上の大規模並列計算環境にもスケールすることが実証されている。

実際に使われているOPEN/CLOSEリストの実装

OPEN/CLOSEリストに登録されているノードの数が多い場合、ノードの展開ごとに子ノードmをOPENから CLOSE へ移動︵あるいは逆︶するのは非常に高価な操作である。 たとえば、OPEN/CLOSEリストが2分探索木︵赤黒木など︶で実装されている場合、まずノードの探すのに $O(logN)$$O(logN)$かかり︵ノードのIDで検索︶、また削除にも $O(logN)$$O(logN)$かかる。配列の場合には削除により大きなコストがかかる。

しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードを OPEN/CLOSEリスト間で行ったり来たりさせる代わりに、以下のように実装する:

(一)それぞれのノードに、ノードの状態として OPEN, CLOSE の2種類のタグをもたせる。全てのノードは始めOPENである。

(二)ノードに一意な整数IDをもたせる。

(三)また、IDからノードを ${\displaystyle O($1)} $O(1)$で参照できるハッシュテーブルを用意する。

(四)OPEN にノードを追加する際には、mが Openリストに含まれているかは検証せず、重複を許して追加する。かつ、このときノードではなくIDのみを追加する。
(一)IDは整数1つ分なので、重複のオーバーヘッドを最小化出来る。

(五)OPEN からノードを pop する際、pop したノードの状態が OPEN であれば展開を行うが、CLOSE であれば単にスキップする。
(一)このことにより、重複があっても同じノードを無駄に展開しないようにできる。

(二)このことにより、OPENリストは、f値による優先度付きキューの下に先入れ先出し/先入れ後出しのキューを用意することで実装できる。

(三)ノードの検索がおこなわれず、かつ削除が先頭あるいは末尾にしかおこらないので、効率的な実装が可能である。

(六)CLOSEリストは使用しない。

(七)f値による優先度付きキューは、辺のコストが1である場合には単にf値ごとの可変配列にしたほうが高速な操作が可能である。
(一)辺のコストに大幅なばらつきがある場合には、ヒープとして実装したほうがよい。

性質

A* の性質はhの性質によって大きく左右される。

●A* はダイクストラの一般化であり、ダイクストラと同様、グラフに負のコストの辺があれば完全性を失う。その場合にはベルマン–フォード法を用いる。

●h(n) は常に非負でなくてはならない。

●あるヒューリスティクス h(n) が 全てのノードnについて 真のゴール距離 h*(n) を上回らない場合、hは Admissible/許容的であると言う。

${\displaystyle \forall n,0\leq h($n)\leq h^{*}(n)} $\forall n,0\leq h(n)\leq h^{*}(n)$
このとき、A*の返す経路は最適、つまり最短経路である。

●あるヒューリスティクス h(n) について、全てのノードnと、それに隣接しているノードmについて ${\displaystyle h($n)\leq cost(n,m)+h(m)} $h(n)\leq cost(n,m)+h(m)$である場合、そのhはconsistent/無矛盾であるという。

●consistent なhは、常に admissible である。

●ある2つのヒューリスティック関数 h1, h2 について、${\displaystyle \forall n,h_{1}($n)\leq h_{2}(n)} $\forall n,h_{1}(n)\leq h_{2}(n)$ が成り立つ時、 h2 は h1 を支配する (dominate) とよぶ。このとき、特に両者が許容的な場合、h2 を用いた探索はより効率的だろうと考えられている。しかし、いくつかのコーナーケースではこのことは成り立たない。

このアルゴリズムはCPUの使用率、メモリの使用率など、計算負荷は高いが、問題に応じた適切なヒューリスティック関数を用いることにより、問題に対しての最適化が可能である。

部分問題に分割する場合

分割統治法のように、部分問題に分割したうえで全体問題を解いた方が効率的な問題もある。A^* 同様の通常の状態遷移はどれかがゴールに到達すれば良いのでORと呼び、部分問題に分割する場合は全ての部分問題が解けないといけないので AND と呼ぶと、探索木が AND/OR 木になる。AND で状態を分割する際、ゴールも分割する必要がある。

同じ状態が2度出現した場合に1つのノードにまとめると AND/OR グラフになる。閉路のない AND/OR グラフに対するA^* アルゴリズムに対応する物が1968年に開発され、1980年に AO^*アルゴリズム と命名された。閉路のある AND/OR グラフに対するA^* アルゴリズムに対応する A₀アルゴリズム は1976年に開発された。AND ノードのコストを﹁辺のコスト＋部分問題のコストの最大値﹂や﹁辺のコスト＋部分問題のコストの総和﹂などの単調非減少関数で定義すると、ヒューリスティック関数が許容的であれば、A^* 同様、最適解が求まる。なお、閉路のない AND/OR グラフは文脈自由文法︵タイプ-2 文法︶、閉路のある AND/OR グラフは制限のない文法︵タイプ-0 文法︶に1対1対応することが証明されている。

関連項目

• 最良優先探索
• ダイクストラ法
• 均一コスト探索
• 双方向探索
• シェーキー