400
Post/Edit Page
課題でA*アルゴリズムを実装した。A*はエースターと読む。ちょっと変わった名前のこのアルゴリズムは、グラフ上の二点間の最短距離を効率的に求める手法で、グラフ理論では有名なダイクストラ法の拡張版である。▼ダイクストラ法は、次のように最短経路を求める手法だ。「到達済の場所でもっとも移動コストの小さい場所を選ぶ。そこから次の場所へ進み、そこまでの移動コストを計算する。その場所に既知の移動コストがあれば比較し、こちらの方が小さければ「自分→相手」経路を暫定的に確定する。以上をゴール発見まで繰り返す。」▼この方法は「全経路が最適経路であれば、その部分経路も最適経路である」という最適性の原理を前提としている。そうして部分最適経路を手近なところから順次確定していくことで、全体最適経路を求めている。このような「臨機応変な」手法を一般に動的計画法という。計算時間が短く最適解が保証される点、便利な手法である。
pass:
Draft