■

1日経ったら、何書こうと思ってたのか忘れた…前も同じことあったような・・・だめだな。
http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
の各データ構毎の比較がわかりやすくていい感じ。A*の動作を簡単に説明すると

1. OPENリストからコストが最小ののノードを取り出してOPENリストから削除(DeleteMin)→Closedリストに突っ込んでおく。
2. 取り出したノードに隣接するノードのコストを調べる。そのノードが既にOPENまたはCLOSEDに入ってるかどうか調べ(member)、もし入ってたらコストを比較、小さい方に置き換え(adjust)、CLOSEDの場合は再度OPENリストに突っ込む。入ってなかったらそのままOPENリストに入れる(Insert)。
3. 1に戻る

他にいろいろ書いてたけど、なんか間違ったこと書いてる気がしてきたので削除。オーダーの計算の所。memberを計算に入れたらおかしくなった・・・たぶん何か勘違いしてるんだろう。

追記:
結局、元々書こうと思ってたのはAI　Game Programmig Wisdomに載ってた、A*データのデータ構造にヒープじゃなくて、ただの線形リスト２つを工夫して使ってることについてだったのを思い出した。ここ2,3日、わざわざ計算量オーダーについて書いてるのもそのため。