アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

 

A*

は、各地点からゴールまでの距離について、正確ではないまでも何らかのヒントが得ら

れている場合に有用です。もちろん、そのような情報がまったく得られない状況もあります

が、その場合は

A*

は使えません。

 ヒューリスティックコストは、現在地からゴールまでの実際のコストに近ければ近いほど、

探索の効率が良くなります。逆 に、実 際 のコストからかけ離れたコストをヒューリスティック

コストとして使ってしまうと、ダイクストラ法よりもかえって効率が悪くなってしまう場合

があります。さらにかけ離れたコストを使うと、正しい答えが求まらない場合すらあります。

 なお、ヒューリスティックコストが実際のコスト以下に設定されていれば、正 しい答えが求

まることは保証されています（ただし、設定により探索効率が悪くなることはあります）。



 

A*

は、ゲームプログラミングにおいて、プレイヤーを追いかける敵の動きの計算などによ

く使用されます。しかし、計算量が大きいため、ゲーム全体の進行速度に悪い影響を与えるこ

ともあり得ます。他のアルゴリズムと組み合わせたり、使 う場面を絞ったりと、使 用 にあたっ

ての工夫が必要となります。





