Arc-Consistency Algorithm の複雑さはなぜ O(cd 3 ) なのですか?
3300 次
1 に答える
12
AC-3 一貫性アルゴリズムについて言及していると仮定します。このアルゴリズムについては、こちらでわかりやすく簡単に説明しています。このアルゴリズムの説明を参照します。
まず、メソッドの複雑さを計算してREVISEみましょう (メソッドは 2 つのドメイン間の 1 つのアークを修正します)。1 つのドメインの各値について、2 番目のドメインのすべての値を調べています。したがって、メソッドの複雑さはREVISEd 2 where d is maximum domain size.
さて、最悪何回REVISEコールされるでしょうか？最初は、キューにすべてのアークがあります。が呼び出されるたびREVISEに、1 つのアークがキューから削除されます。それはメソッドの e 呼び出しです。しかし、アークもキューに追加しています。私たちはそれを何回行うことができますか？アークが指しているドメインから値が削除された場合にのみ、アークをキューに追加します。1 つのアークは 1 つのドメインを指しているため、そのドメイン内の値の数だけ追加できます。したがって、最悪の場合、すべてのアークをキューに d 回追加し直しています。
REVISEは最大 e + ed 回呼び出されe is number of arcsます。
すべてをまとめると、アルゴリズム全体の複雑さは O((e+ed)d 2 )、つまり O(ed 3 ) であることがわかります。
于 2016-04-21T13:54:19.050 に答える