■

ダイクストラ法とA*の大きな違い。ダイクストラ法では基本的にOPENリストに入ったノードは近いうちに展開される。
それに対してA*ではh()が入ってるので無意味にfが悪化するようなノード、ゴールと反対方向に向かうようなノードはめったに展開されることはない。必要になるとしても、他が行き詰った時、要するにかなり後になってからになる。また、展開されたノードでコストがよい物は比較的すぐに続けて展開される可能性が高い。A*の場合、この辺に最適化の余地が。要するにコストがいいものとそうでないものでOPENリストのデータ構造を分ける。

前述の通り、計算量オーダーはOPENリストの中の要素数に影響される。よってOPENリストを小さく保つことが重要。よって、有望そうなノードだけで実際にDeleteMin,Insertを適用するOPENリストを構築し、当分使いそうもないノードはInsertがO(1)で行えるunsorted listに突っ込んでおいて、必要になってからここから取り出してOPENリストに追加することにする。
unsorted listの場合コストが最小のノードk個をまとめてO(N)で取り出すことができる。最小ノードを取り出すのに平均すれば１個当たりO(N/k)ってことになる。

http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
ではHOT queuesって書かれてる所。AI Game Programming Wisdom に載ってたのもこれの変種っぽい。Empire EarthっていうRTSゲームで使われた例で、上記の有望そうなノードだけで構成されたOPENリストを大体サイズ15程度のsorted listで実現したらしい。
サイズ小さすぎの気もするけど実際に使われた例だからそんなもんなんだろう。RTSの場合比較的、障害物が少ない＝展開されたノードが続けて展開されることが多い。ってのがこの理由なのかな。あまり大きくても、線形リストだと要素数がそのままInsertにかかる時間に影響してくるわけだし。