RustでA*アルゴリズム 最短経路問題
TL;DR
- 探索は選択･展開･生成
- A*アルゴリズム: 探索候補の決定基準(コスト評価関数)に
-
g(n): 根から現在ノードまでのコスト -
h'(n): 現在ノードから目標ノードまでの見積もりコスト (∀n.h'(n) < h(n)) -
f(n) = g(n) + h'(n)で計算する
-
背景
講義でやったのでRustで実装する｡
コード
ヒューリスティック探索について
前の記事で説明した通り､探索は
- ノードの選択(select)
- 子ノードの展開(expand)
- オープンリストの生成(generate)
の3段階ができていれば良い｡
ただBFSやDFSのような｢情報のない｣探索法の場合､不得手な問題には時間がかかることや､BFS､反覆深化BFSなどでは空間計算量もかさんでしまう｡
そこで､問題からの情報を前提にする特化した探索を行うことで､情報のない探索の欠点を潰して効率的に探索問題を解くというのがヒューリスティックな探索である｡(日本語で表現するなら見込み探索?)
コスト評価関数の導入
無駄な探索の原因の一つは､解を含まない枝を持つノードを選択してしまうことで､DFSの場合はかなり時間を無駄にしてしまうし､BFSでも(分岐数が多いと)無駄な探索になる｡
そこで､｢解がふくまれそうなノード｣を選択できるように基準を導入する｡
コスト評価関数に採用できるのはおもに2つで､
-
g(n) -
h(n)
......なのだが､今から探索するというのに｢現在ノードからゴールまでのコスト｣などは基本的に求められない｡
そこで､正確ではないにせよある程度の精度のある､ゴールまでの大体のコストが出せるような関数を定義する｡
ただし､理想関数
最適性とかのあれこれのために必要な制約だが､証明は割愛する｡(実装には関係がないので)
A*アルゴリズム
さて､タイトルにもあるA*アルゴリズムは､コスト評価関数(ここではf(n))を､以下のように定義する｡
selectの段階において､オープンリストf(n)が最小､つまりゴールのノードまでの見込みコストが小さいものを採用するアルゴリズムになる｡
最短経路問題
今回取り扱う問題は､
- startとgoalがある(goalはないかもしれない)
- 通路と壁が存在して､壁の位置には進めない
- ノード展開は上下左右4方向の通路のみ
-
h'(n)
のように設定した｡
迷路自体はシンプルに回り道がある場合のパターンを挙げてある｡dungeonを編集すれば別の迷路を解くこともできる｡
ノードの構造
座標(Point)と壁か通路か(State)､コストを持つ｡(経路履歴用にcame_fromは用意してあるが今回は使っていない)
Pointの定義
グラフ本体はdungeonで､Vec<Vec<Field>としてある｡基本ノードを参照するときは､Pointから取得する｡
例えば､4行8列目のノードを参照する場合は(0-indexed)
node = &dungeon[4][8];
のようになる｡
展開(展開して､f(n)を設定する)
A*の肝で､今回は選択されたノードとゴールノード間のマンハッタン距離を採用した｡
選択
展開して､生成されたオープンリストのノードは､すべて
ここでは､昇順ソートから､先頭を取り出すことで選択を実装している｡
sort_by()には比較基準となるクロージャ(FnMut(&T, &T) -> Ordering)が必要で､今回は
|a, b| dungeon[a.y][a.x].f_cost.cmp(&dungeon[b.y][b.x].f_costとして､
実行例
少し分かりづらいが､00は未訪問､数字は
ゴールに近い行き止まりが先に探索され､近い方の壁を回り込むように探索されているのがわかる｡
St010203040506070809101112131415000000
01020304050607080910111213████00000000
02050407060908111013121514████00000000
03060508071009121114131615████00000000
04070609081110131215141716████00000000
05080710091211141316151817████00000000
0607██████████████████████████00000000
0708██████████████████████████00000000
10091011121314151617████00000000000000
11101112131415161718████Go000000000000
12111213141516171819████24000000000000
00121314151617181920212223240000000000
00000000000000000021222324000000000000
ただこれがドンピシャな実装というわけでもないので､参考はほどほどに｡
とにかく選択･展開･生成ができていて､コスト関数を用いて選択ができていればヒューリスティックな探索ができていれば実装としては好しでしょう｡
まとめ
A*アルゴリズムは､根から現在ノードまでのコストと､ゴールノードまでの見込みコストを用いた評価関数を基準に選択する｡
今回はヒューリスティック関数にマンハッタン距離を採用したが､これよりも更に近似できる関数を使うとより効率的に求まるだろう｡(ゴールまでの間に壁があればさらにコストを増やすなど)
おまけ
Pointは構造体なので､本来であればPoint同士の足し算などできない｡
今回のRepoでは､+演算子用のTraitであるstd::ops::AddをPointに実装することで直接足し算ができるようにして､実装として読みやすくなるようにしている｡
配列の添字はusizeだが､今回の問題上座標を減らすことが移動方向によっては起こり得る｡そこで､座標はusizeのまま､符号を表すpn: boolを用意した(正直安直でわかりにくい回避策なのでなんとかしたい)
Discussion