A* algorithm tutorial
以下のページの勝手な要約です。
( http://web.archive.org/web/2005/http://www.geocities.com/jheyesjones/astar.html )
State Space Search
A*はサーチアルゴリズムである。 A*アルゴリズムは、初期状態から、目標状態までの最短経路を導き出す。以下では、例題として簡単なパスファインディング、8-パズルの最短経路を導く。
(1) Some Terminology
ノード`
問題領域内の状態。 経路探索では、2D座標のこと、 8-パズルでは、すべてのタイルの位置のことを指す。
グラフ
問題を解く過程で、可能なノードの遷移を表したグラフ。
エッジ
遷移の線? 状態空間検索 初期状態からはじめ、各ノードに対して遷移可能なノードをグラフの下に拡張していくこと。
(2) Heuristics(発見的手法) and Algorithms
アルゴリズムは、問題をとくための決定的な方法である。一方、発見的手法は、問題を解く保証はないが、アルゴリズムがない問題に付いては有効である。
発見的手法は、探索空間を減らすことを助ける。各ノードがゴールからどれだけ離れているかの見積もりが必要になる。経路探索は単純に距離が求められる。 8-パズルでは、いくつかの方法があるが、Nilssonスコアがよく用いられる。
(3) Cost
発見的手法のアイデアとして、ゴールとの距離を基準にする方法を紹介した。もう一つの重要な方法が、その場所に至るまでのコストである。たとえば、経路探索では、各マスに移動コストがつけられる。
8-パズル
8-パズルは、3x3のマスに配置されたA-Hまでのタイルを正しい順番に直すパズルである。 8-パズルは、362,880個の状態を持つ。ほとんどのノードで、エッジは、2となる。たとえば18ステップ目のノードは、262,144個存在することになる。
経路探索
経路探索では、スタートからゴールまでの経路を探す。 A*は、ゴールまでの経路を探し出すだけではなく、最短経路を探し出すことができる。
A*の実装
まずは8-パズルを考える。最初の状態から、考えられるノードは2個(図はリンク先を参照)ある。しかし、盲目に探索していくだけでは、メモリを使い切る前に解を見つけることはできないだろう。前に調べたノードを覚えておく必要がある。
そこで、OPENリストと、CLOSEリストを使う。 OPENリストはまだ開けてないノードの、CLOSEリストはすでに開けたノードのリストである。初期状態では、スタートノードのみがOPENリストにある。次に、スタートノードから行けるノードをOPENリストに入れる。スタートノードの処理は終わったので、CLOSEリストに入れる。 (OPENリストに入れるものは、OPENリスト、CLOSEリストの中を見て、よりよい状態を持っているかを調べる。)
OPENリストの中から次に探索するノードを、より選択的にするために各ノードについて以下の式で求められる値を使う。
f = g + h
gは、スタートノードからそのノードに到着するまでのコストの合計である。 hは、そのノードからゴールノードまでのコストの予想値をあらわす。 fは、両者の合計である。 f, g, hを各ノードで計算する。これらの値が、A*アルゴリズムで、ゴールまでの道のりを目指すための指標となる。
手順
node_goal = ゴール状態
node_start = 初期状態
OPEN_listにnode_startを入れる
while ( OPEN_listが殻でない ) {
node_current <- OPEN_list内の最小のfを持つノード
node_currentがnode_goalと同じなら終了
foreach node_successor (node_currentからたどれるノード集合) [
node_successor.g = node_current.g + (node_currentからnode_successorまでのコスト)
if (OPENリスト内にnode_successorがあり、かつ、そちらgの方が小さい) {
// リスト内のノードのほうがbetterな経路をたどっている
node_successorを破棄し、次へ
}
if (CLOSEリスト内にnode_successorがあり、かつ、そちらのgの方が小さい) {
// リスト内のノードのほうがbetterな経路をたどっている
node_successorを破棄し、次へ
}
node_successorをOPENリストとCLOSEリストから削除する
node_successorの親ノードをnode_currentにする
node_successor.h = node_goal間での距離(発見的アルゴリズムで決定)
node_successorをOPENリストに入れる
}
}
hは、発見的アルゴリズムで求めなければならない。 hの値の求め方が、A*では重要となる。経路探索では、この点は地形を考慮すればよいので簡単である。 8-パズルでは、ニルソンの手法を使用する。
Nilsson's Sequence Score
タイルが、中央にある場合、スコア1。中央にない各タイルについて、タイルの時計回りにあるタイルが、時計回りにあるべきタイルでなかった場合、スコア2。ここまでのスコアを3倍する。最後に、各タイルが正しい位置に移動する時に必要な距離を足す。
C++での実装の詳細
A*サーチをSTLを使って書く話。
許容可能性(Admissibility)
A*サーチは、予想したhが実際のゴールまでの距離より大きくなければ、常に最適な解を返す、と言う話。
以下、リアルタイムストラテジーの話より:
A*の面白い特性。 移動コストの予想値が常に実際の最小コスト以下ならば、最短の移動経路を求めることができる。 例えば、予想値の重みを0(すなわち無視)にすると確実に最短移動経路が得られる。遅くて無駄も多いが。 だから、
・高速な検索をしたいときには予想値を素早く得て、重み付けも多くつける
・高精度な検索をしたいときにはなるべく正確な予想値を得て、あまり重み付けはあまり重くしない
ということやね。"アホな敵"をシミュレートしたいならこのあたりを工夫すればそれっぽくなりそう。
最適化
Gemsを読めという話？
コラム?