■
続き。
２点間の最短経路を求めるアルゴリズムについて。
A*が最も有名。ダイクストラ法に加えてヒューリスティック(目的地までの予想距離)を用いた探索を行う。
A*の簡単な解説。実際動いてるの見たほうがわかりやすいと思う。
http://www.generation5.org/content/2002/ase.asp
のがいい感じ。
http://www.intrafoundation.com/pathfinder2d.asp
のは見てて面白い。スピード調整が必要。
A*の説明。Game Programming Gems持ってるならそっち見たほうがわかりやすいかも。
f(x)=g(x)+ h(x)
g() は始点からｘまでにかかる実際のコスト(正確)
h() はxから終点までの予想距離(不正確)。
よって、この二つの和f()は地点xを通る経路の予想コストを表すことになる。
後はこのf()が小さい所から周辺ノードを展開してけばよい。
A*はh=「予想コスト」が実際のコストよりも小さい。という条件の下で数学的に完全、かつ最適であることが保障されている。要するに終点にたどり着く経路が存在すれば必ず見つけられて、かつそのような、他のどのアルゴリズムよりも効率的ってこと。
- ｈの見積もりが常に0ならダイクストラ法。これは見つかった経路は最適であることが保障されている。ただし探索は遅い。
- hが実際のコストよりも小さい場合。上記にあるように最適な経路が得られる。
- ｈが実際のコストとぴったり同じの場合。余計なノードは一切展開しないで最適な経路が見つかる。不可能だけど。最初からわかってたら経路探索する必要ないわけだし。
- ｈが実際のコストより過大な見積もりをしている場合。最適な経路は得られない。過大に見積もったε分まで最適経路からずれる可能性がある。ε-admissible(ε許容性)。探索は速い。
A*の利点としては
- ｈによって探索時間や得られる経路の精度を簡単に調整できる。
- 他のアルゴリズムより速い。
- 実装も楽。
ってことで大抵の用途はA*が適してます。欠点としては
- メモリを大量に使う
- 探索空間が大きくなると遅い
メモリの問題はIDA* (Iterative Deeping A*)とかSMA*(Simplified Memory-Bounded A*)を使うことによって解決できる。メモリを節約する代わりに計算時間が余計にかかりますが。
探索空間が大きくなると遅いって問題ははっきりいってどうしようもないんですが…２乗に比例して探索すべき空間が増えていくので。
最適な経路を得られるアルゴリズムのなかではA*が最も効率的。となると最適な経路を得るのは諦めて準最適な経路を高速に得ることが問題となる。探索空間の枝刈りとかそういった方面。
A*はｈの値で簡単に処理時間を調整できるので、探索初期はｈを適度な値、だんだんｈを過大に見積もってやることによって探索時間を減らして準最適な経路を求める、とかが有効です。
