実際に使われているOPEN/CLOSEリストの実装
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 02:02 UTC 版)
「A*」の記事における「実際に使われているOPEN/CLOSEリストの実装」の解説
OPEN/CLOSEリストに登録されているノードの数が多い場合、ノードの展開ごとに子ノードmをOPENからCLOSEへ移動(あるいは逆)するのは非常に高価な操作である。たとえば、OPEN/CLOSEリストが2分探索木(赤黒木など)で実装されている場合、まずノードの探すのに O ( l o g N ) {\displaystyle O(logN)} かかり(ノードのIDで検索)、また削除にも O ( l o g N ) {\displaystyle O(logN)} かかる。配列の場合には削除により大きなコストがかかる。 しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードをOPEN/CLOSEリスト間で行ったり来たりさせる代わりに、以下のように実装する: それぞれのノードに、ノードの状態として OPEN, CLOSE の2種類のタグをもたせる。全てのノードは始めOPENである。 ノードに一意な整数IDをもたせる。 また、IDからノードを O ( 1 ) {\displaystyle O(1)} で参照できるハッシュテーブルを用意する。 OPENにノードを追加する際には、m が Openリストに含まれているかは検証せず、重複を許して追加する。かつ、このときノードではなくIDのみを追加する。ID は整数1つ分なので、重複のオーバーヘッドを最小化出来る。 OPENからノードをpopする際、popしたノードの状態がOPENであれば展開を行うが、CLOSEであれば単にスキップする。このことにより、重複があっても同じノードを無駄に展開しないようにできる。 このことにより、OPENリストは、f値による優先度付きキューの下に先入れ先出し/先入れ後出しのキューを用意することで実装できる。 ノードの検索がおこなわれず、かつ削除が先頭あるいは末尾にしかおこらないので、効率的な実装が可能である。 CLOSEリストは使用しない。 f値による優先度付きキューは、辺のコストが1である場合には単にf値ごとの可変配列にしたほうが高速な操作が可能である。辺のコストに大幅なばらつきがある場合には、ヒープとして実装したほうがよい。
※この「実際に使われているOPEN/CLOSEリストの実装」の解説は、「A*」の解説の一部です。
「実際に使われているOPEN/CLOSEリストの実装」を含む「A*」の記事については、「A*」の概要を参照ください。
- 実際に使われているOPEN/CLOSEリストの実装のページへのリンク
