A*

探索たんさく > 最良さいりょう優先ゆうせん探索たんさく > A*

A*（A-star、エースター）探索たんさくアルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索たんさくアルゴリズムの一ひとつ。 最良さいりょう優先ゆうせん探索たんさくを拡張かくちょうしたZ*に、さらにf値ちとして「現時点げんじてんまでの距離きょり」g と「ゴールまでの推定すいてい値ち」h の和わを採用さいようしたもの。h は ヒューリスティック関数かんすうと呼よばれる。

A*探索たんさくアルゴリズム

概要がいよう

A* アルゴリズムは、「グラフ上じょうでスタートからゴールまでの道みちを見みつける」というグラフ探索たんさく問題もんだいにおいて、 ヒューリスティック関数かんすう h(n) という探索たんさくの道標どうひょうとなる関数かんすうを用もちいて探索たんさくを行おこなうアルゴリズムである。h は各かく頂点ちょうてん n からゴールまでの距離きょりのある妥当だとうな推定すいてい値ちを返かえす関数かんすうで、解とくグラフ探索たんさく問題もんだいの種類しゅるいに応おうじてさまざまな h を設計せっけいすることが出来できる。 例たとえば、カーナビなどで用もちいられる単純たんじゅんな二に次元じげんの地図ちずでの探索たんさくでは、h としてユークリッド距離きょり ${\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) に置おき換かえることを考かんがえる。

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

ここで g(n) はスタートノードから n までの最小さいしょうコストの推定すいてい値ち、h(n) は n からゴールノードまでの最小さいしょうコストの推定すいてい値ちである。この場合ばあい g に関かんしては探索たんさくの過程かていで更新こうしんを加くわえることにより g* に近ちかづけてゆくことができるが、h* は、実際じっさいにゴールに辿たどり着つくまでは誰だれにもわからない。そこで、h(n) には人間にんげんが（ある程度ていど妥当だとう性せいを持もつように）設計せっけいした推定すいてい値ちを与あたえることにする。このアルゴリズムを A*探索たんさくアルゴリズムといい、h (n) をヒューリスティック関数かんすうという。

アルゴリズムの流ながれ

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

1. スタートノード（$S$）を作成さくせいする。また計算けいさん中ちゅうのノードを格納かくのうしておくための優先ゆうせん度ど付つきキュー OPENリストと、計算けいさん済ずみのノードを格納かくのうしておくCLOSEリストを用意よういする。（名前なまえは「リスト」だが、これらの実際じっさいのデータ構造こうぞうは必かならずしも連結れんけつリストである必要ひつようはない。）
2. ゴールは必かならずしも１ひとつである必要ひつようはないので、ゴール条件じょうけんを満みたすノード集合しゅうごうを $G$ と呼よぶことにする。
3. スタートノードを Openリストに追加ついかする、このとき $g(S)$ = $0$ であり $f(S)$ = $h(S)$ となる。また Closeリストは空そらにする。
4. Openリストが空そらなら探索たんさくは失敗しっぱいとする（スタートからゴールにたどり着つくような経路けいろが存在そんざいしなかったことになる）。
5. Openリストに格納かくのうされているノードの内うち、最小さいしょうの $f(n)$ を持もつノード $n$ を1つ取とり出だす。同おなじ $f(n)$ を持もつノードが複数ふくすうある場合ばあい、タイブレーク手法しゅほうによりどれかのノードを選択せんたくする。
6. $n\in G$ であるなら探索たんさくを終了しゅうりょうする。それ以外いがいの場合ばあいは $n$ を Close リストに移うつす。
7. $n$ に隣接りんせつしている全すべてのノード（ここでは隣接りんせつノードを $m$ とおく）に対たいして以下いかの操作そうさを行おこなう
   1. $f'(m)=g(n)+COST(n,m)+h(m)$ を計算けいさんする、ここで $COST(n,m)$ はノード n から m へ移動いどうするときのコストである。また $g(n)$ は $g(n)=f(n)-h(n)$ で求もとめることができる。
   2. m の状態じょうたいに応おうじて以下いかの操作そうさを行おこなう
      • m が Openリストにも Closeリストにも含ふくまれていない場合ばあい $f(m)\leftarrow f'(m)$ とし m を Openリストに追加ついかする。このとき m の親おやを n として記録きろくする。
      • m が Openリストにある場合ばあい、$f'(m)<f(m)$ であるなら、m を Open から削除さくじょし、$f(m)\leftarrow f'(m)$ に置おき換かえ、再ふたたび Open に挿入そうにゅうする（Open が正まさしくソートされていることを保証ほしょうするため）。また、記録きろくしてある m の親おやを n に置おき換かえる。
      • m が Closeリストにある場合ばあい、$f'(m)<f(m)$ であるなら $f(m)\leftarrow f'(m)$ として m を Openリストに移動いどうする。また記録きろくしてある m の親おやを n に置おき換かえる。
8. 3 以降いこうを繰くり返かえす。
9. 探索たんさく終了しゅうりょう後ご、発見はっけんされたゴール $n_{G}$ から親おやを順次じゅんじたどっていくと S から ゴール $n_{G}$ までの最短さいたん経路けいろが得えられる。

以上いじょうの流ながれを見みれば、アルゴリズムが手続てつづき的てきで、並列へいれつ化かが非常ひじょうに難むずかしいことがわかる。しかし、近年きんねんでは HDA*、PBFS などの並列へいれつ手法しゅほうが開発かいはつされ、特とくに HDA* は768コア以上いじょうの大だい規模きぼ並列へいれつ計算けいさん環境かんきょうにもスケールすることが実証じっしょうされている。

実際じっさいに使つかわれているOPEN/CLOSEリストの実装じっそう

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

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

1. それぞれのノードに、ノードの状態じょうたいとして OPEN, CLOSE の2種類しゅるいのタグをもたせる。全すべてのノードは始はじめOPENである。
2. ノードに一意いちいな整数せいすう ID をもたせる。
3. また、ID からノードを $O(1)$ で参照さんしょうできるハッシュテーブルを用意よういする。
4. OPEN にノードを追加ついかする際さいには、m が Openリストに含ふくまれているかは検証けんしょうせず、重複じゅうふくを許ゆるして追加ついかする。かつ、このときノードではなく ID のみを追加ついかする。
   1. ID は整数せいすう1つ分ぶんなので、重複じゅうふくのオーバーヘッドを最小さいしょう化か出来できる。
5. OPEN からノードを pop する際さい、pop したノードの状態じょうたいが OPEN であれば展開てんかいを行おこなうが、CLOSE であれば単たんにスキップする。
   1. このことにより、重複じゅうふくがあっても同おなじノードを無駄むだに展開てんかいしないようにできる。
   2. このことにより、OPENリストは、f値ねによる優先ゆうせん度ど付つきキューの下したに先入さきいれ先出さきだし/先入さきいれ後ご出だしのキューを用意よういすることで実装じっそうできる。
   3. ノードの検索けんさくがおこなわれず、かつ削除さくじょが先頭せんとうあるいは末尾まつびにしかおこらないので、効率こうりつ的てきな実装じっそうが可能かのうである。
6. CLOSEリストは使用しようしない。
7. f値ねによる優先ゆうせん度ど付つきキューは、辺あたりのコストが1である場合ばあいには単たんにf値ねごとの可変かへん配列はいれつにしたほうが高速こうそくな操作そうさが可能かのうである。
   1. 辺あたりのコストに大幅おおはばなばらつきがある場合ばあいには、ヒープとして実装じっそうしたほうがよい。

性質せいしつ

A* の性質せいしつは h の性質せいしつによって大おおきく左右さゆうされる。

• A* はダイクストラの一般いっぱん化かであり、ダイクストラと同様どうよう、グラフに負まけのコストの辺あたりがあれば完全かんぜん性せいを失うしなう。その場合ばあいにはベルマン–フォード法ほうを用もちいる。
• h(n) は常つねに非負ひふでなくてはならない。
• あるヒューリスティクス h(n) が 全すべてのノード n について 真しんのゴール距離きょり h*(n) を上回うわまわらない場合ばあい、h は Admissible/許容きょよう的てきであると言いう。

$\forall n,0\leq h(n)\leq h^{*}(n)$

このとき、A*の返かえす経路けいろは最適さいてき、つまり最短さいたん経路けいろである。

• あるヒューリスティクス h(n) について、全すべてのノード n と、それに隣接りんせつしているノード m について $h(n)\leq cost(n,m)+h(m)$ である場合ばあい、その h はconsistent/無矛盾むむじゅんであるという。
• consistent な h は、常つねに admissible である。
• ある2つのヒューリスティック関数かんすう h1, h2 について、$\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対応たいおうすることが証明しょうめいされている。

関連かんれん項目こうもく

• 最良さいりょう優先ゆうせん探索たんさく
• ダイクストラ法ほう
• 均一きんいつコスト探索たんさく
• 双方向そうほうこう探索たんさく
• シェーキー