A* パス検索アルゴリズムの定義を調べていますが、場所によって定義が多少異なっているようです。
違いは、ノードのサクセサーを通過するときに実行されるアクションと、サクセサーがクローズド リストにあることを見つけることです。
私は混乱しています - どの方法が正しいですか? 直感的には前者の方が分かりやすいのですが、定義の違いが気になります。定義の 1 つが間違っていますか、それとも何らかの形で同形ですか?
最初のアプローチは、繰り返される状態への最適なパスが常に最初にたどられる場合にのみ最適です。このプロパティは、ヒューリスティック関数に一貫性のプロパティ (モノティシティとも呼ばれます) がある場合に保持されます。nのすべてのノードとすべてのサクセサn'についてn、 からゴールに到達するための推定コストが から に到達するnためのステップ コストとn'からnゴールに到達するための推定コストを加えた値よりも大きくない場合、ヒューリスティック関数は一貫していますn。
2 番目のアプローチは、ヒューリスティック関数が単に許容できる場合、つまり、目標に到達するためのコストを過大評価しない場合に最適です。
すべての一貫したヒューリスティック関数も許容されます。一貫性は許容性よりも厳しい要件ですが、許容できるが一貫性がないヒューリスティック関数を作成するには、かなりの労力を費やす必要があります。
したがって、厳密に大きなヒューリスティック関数のサブセットで動作するため、2 番目のアプローチの方がより一般的ですが、実際には通常、最初のアプローチで十分です。
参照: サブセクションA* 検索:セクション4.1 Informed (Heuristic) Search Strategiesの総推定ソリューション コストの最小化人工知能: 最新のアプローチ。