3

A* 検索アルゴリズムが検索空間内のすべての状態を探索するのは、どのような条件下ですか? これは最悪のケースですか？

私によると、ゴールまでのルート上の各ノードの f(n) が同じレベルの他のノードよりも高い場合、検索空間全体を検索する必要があります。生成されたすべてのノードを展開してゴールに到達する必要があるため、これは最悪のケースです。

これは正しいです？

4

1 に答える 1

1

ウィキペディアから：

A* の時間計算量はヒューリスティックに依存します。最悪の場合、展開されるノードの数は、解の長さ (最短経路) で指数関数的になりますが、探索空間が木で、単一のゴール状態があり、ヒューリスティック関数 h が a を満たす場合、多項式になります。特定の基準:

于 2012-11-17T10:29:54.840 に答える