7

ウィキペディアは、A*の複雑さについて次のように述べています。

A *の時間計算量は、ヒューリスティックに依存します。最悪の場合、展開されるノードの数は解の長さ（最短経路）で指数関数的ですが、探索空間がツリーの場合は多項式になります...

そして私の質問は、「A *の時間計算量は指数関数的ですか？それとも時間計算量ではなく、メモリ複雑さですか？」です。それがメモリの複雑さである場合、A *にはどの時間計算量がありますか？

4

3 に答える 3

5

最悪の場合、A*時間計算量は指数関数的です。

ただし、h(n) 推定距離とh*(n)残りの正確な距離を考慮してください。条件| h(n) - h*(n) | < O(log *h(n) )が成立する場合、つまり、推定関数の誤差が指数関数的に大きくなる場合、A*時間計算量は多項式になります。

悲しいことに、ほとんどの場合、推定誤差は線形になります。したがって、実際には、より高速な代替案が好まれます。支払われる代償は、最適性がもはや達成されていないという事実です。

于 2012-08-30T08:01:36.337 に答える
3

拡張された各ノードは、同じノードに何度もアクセスしないように格納されるため、拡張されたノードの数が指数関数的に増加することは、時間と空間が指数関数的に複雑になることを意味します。

必要な指数空間の複雑さは、指数時間の複雑さを意味することに注意してください。逆は真ではありません。

于 2012-06-17T09:38:43.220 に答える
0

A *の時間計算量は指数関数的ですか、それともメモリの複雑さですか？

ウィキペディアからのその抜粋は、それが時間計算量に言及していることを示唆しています

于 2012-06-17T09:30:21.173 に答える