15/07/24 01:27:56.31 n+CXZn5k.net
>>645
まず、優先度キュー(順位キュー)を勉強する。
次に優先度キューを使った、ダイクストラを勉強する。
その後に、A*
ダイクストラとは例えば、優先度キューに、
10,35,6,23,14と入ると、
6,10,14,23,35と並べ替えられ、一番小さい6から、
探索されるので、解を速く見つけられる
A*はその応用で、ヒューリスティックをプラスして考える。
ヒューリスティックは普通、距離を使う
例えば、右に3マス・上に4マスのセルを調べる場合、
3+4=7 または、ピタゴラスの定理、a^2 + b^2 = c^2
を使って直線距離で、9+16=25=5*5、
つまり5を使ってもよい
つまり、距離をプラスしてから、優先度キューに入れるので、
距離の近いセルから探索されるため、解を速く見つけられる