A* アルゴリズムの正しい定式化

Question

A* 経路探索アルゴリズムの定義を調べていますが、場所によっては多少異なる方法で定義されているようです。

違いは、ノードの後続ノードを調べて、後続ノードがクローズドリストにあることを発見したときに実行されるアクションにあります。

• 1 つのアプローチ (によって提案されています) ウィキペディア, 、 そして この記事） 言います：後継者が非公開リストに載っている場合は無視してください
• 別のアプローチ（提案 ここ そして ここ, 、たとえば）は次のように言います。後継者が非公開リストに載っている場合は、そのコストを調査します。現在計算されているスコアよりも高い場合は、今後の検査のためにその項目を非公開リストから削除します。

混乱しています - どの方法が正しいですか?直感的には前者のほうがわかりやすいと思いますが、定義の違いはどうなるのでしょうか。定義の 1 つが間違っているのでしょうか、それとも何らかの形で同型なのでしょうか?

Answer 1

最初のアプローチは、繰り返し状態への最適なパスが常に最初にたどられる場合にのみ最適です。この特性は、ヒューリスティック関数が次の特性を持つ場合に当てはまります。 一貫性 （とも呼ばれている 単調性）。ヒューリスティック関数は、すべてのノードについて一貫性がある場合に一致します。 n そしてすべての後継者 n' の n, 、目標に到達するための推定コスト n に到達するためのステップコストを超えない n' から n に目標を達成するための推定コストを加えたものです。 n.

2 番目のアプローチは、ヒューリスティック関数が単に許容可能な場合、つまり、目標に到達するためのコストを決して過大評価しない場合に最適です。

すべての一貫したヒューリスティック関数も許容されます。一貫性は許容性よりも厳しい要件ですが、許容可能ではあるが一貫性がないヒューリスティック関数をでっち上げるには、かなりの労力を費やす必要があります。

したがって、2 番目のアプローチはヒューリスティック関数の厳密に大規模なサブセットで機能するため、より一般的ですが、実際には通常は 1 番目のアプローチで十分です。

参照：サブセクション 検索：総推定ソリューションコストを最小限に抑える セクション内 4.1 情報に基づいた (ヒューリスティックな) 検索戦略 本の 人工知能：現代的なアプローチ.