A*
A* の性質は h の性質によって大きく左右される。
A* はダイクストラの一般化であり、ダイクストラと同様、グラフに負のコストの辺があれば完全性を失う。その場合にはベルマン–フォード法を用いる。
h(n) は常に非負でなくてはならない。
あるヒューリスティクス h(n) が 全てのノード n について 真のゴール距離 h*(n) を上回らない場合、h は Admissible/許容的であると言う。
∀ n , 0 ≤ h ( n ) ≤ h ∗ ( n ) {\displaystyle \forall n,0\leq h(n)\leq h^{*}(n)}
このとき、A*の返す経路は最適、つまり最短経路である。
あるヒューリスティクス h(n) について、全てのノード n と、それに隣接しているノード m について h ( n ) ≤ c o s t ( n , m ) + h ( m ) {\displaystyle h(n)\leq cost(n,m)+h(m)} である場合、その h はconsistent/無矛盾であるという。
OPEN にノードを追加する際には、m が Openリストに含まれているかは検証せず、重複を許して追加する。かつ、このときノードではなく ID のみを追加する。 ID は整数1つ分なので、重複のオーバーヘッドを最小化出来る。
OPEN からノードを pop する際、pop したノードの状態が OPEN であれば展開を行うが、CLOSE であれば単にスキップする。 このことにより、重複があっても同じノードを無駄に展開しないようにできる。 このことにより、OPENリストは、f値による優先度付きキューの下に先入れ先出し/先入れ後出しのキューを用意することで実装できる。 ノードの検索がおこなわれず、かつ削除が先頭あるいは末尾にしかおこらないので、効率的な実装が可能である。
CLOSEリストは使用しない。
f値による優先度付きキューは、辺のコストが1である場合には単にf値ごとの可変配列にしたほうが高速な操作が可能である。 辺のコストに大幅なばらつきがある場合には、ヒープとして実装したほうがよい。
“Generalized and/or graphs”. Artificial Intelligence 7 (3): 243-259. doi:10.1016/0004-3702(76)90006-0. http://www.sciencedirect.com/science/article/pii/0004370276900060.
↑ Vipin Kumar; Dana S. Nau; Laveen N. Kanal (August 1985). A General Paradigm for AND/OR Graph and Game Tree Search. http://www.cs.utexas.edu/ftp/AI-Lab/tech-reports/UT-AI-TR-85-9.pdf.
↑ Patrick A. V. Hall (July 1973). “Equivalence between AND/OR graphs and context-free grammars”. Communications of the ACM 16 (7): 444-445. doi:10.1145/362280.362302. http://dl.acm.org/citation.cfm?id=362302.