ここにある私の本（人工知能現代のアプローチ）は、均一コスト探索アルゴリズムの最悪の場合の時間と空間の複雑さは O（b [C * / e]） であると述べています。ここで、bは分岐係数、C*は最適なソリューションのコスト、およびすべてのアクションのコストは少なくともeです。しかし、なぜこれがそうなのですか？
質問する
4700 次
2 に答える
3
まず、複雑さはO(B^(C/e))[指数関数的C/e]です。
それを理解するために、最初に簡単な例を考えてみてください。
G=(V,E)分岐係数を持つグラフにしましょうB。グラフは重み付けされていません（w(e) = 1それぞれについてe）。
SからTへの最短パスを見つけることを検討してください。
この場合、アルゴリズムは実際にはBFSであり、パス内の長さまでのすべてのノードを検出しますSOL。ここSOLで、は最短パスの長さです。O(B^|SOL|)
一般的なケースの場合-同じ考えが当てはまり、コストまでのすべてのノードを検出する必要がありますC。したがって、深さまでノードを検出し、探索する必要のあるノードの総数C/eを示します。O(B^(C/e))
指数因子は次の理由によるものです。第1レベル（ルート）にはB^0=1ノードがあり、第2レベルにはBノードがあります。Bこれらのそれぞれからノードを発見し、あなたB^2に、...を与えます。
編集：これまでのところ見逃していましたが、タイトルは
時間の複雑さではなく、スペースの複雑さ
を求めています。ただし、すでに訪問したノードについては、均一コスト検索がセットを保持するため、答えは同じままです。発見した各ノードもそれに追加されるので、答えは残りますvisitedO(B^(C/e))
于 2012-08-15T10:33:39.693 に答える
1
C*/eは、検索中にアクセスする必要があるノードの平均数を意味します。この各ノードにアクセスするには、考えられるすべてのbブランチ（少なくともルートノード）を確認する必要があるため、検索でb [C */e]ノードを確認する必要があります。これは検索時間の複雑さです。これは、各ノードのプロセスがO（1）を取ると仮定することによるものです。
PS：最悪の場合はΩ（b [C * / e] ）です
于 2012-08-15T10:33:47.117 に答える