algorithm - 为什么 Arc-Consistency 算法的复杂度是 O(cd^3)？

Question

为什么弧一致性算法复杂度为 O(cd ³ )？

Answer 1

我假设您指的是 AC-3 一致性算法。这个算法在这里得到了很好的和简单的描述。我将参考这个算法的描述。

首先，让我们计算方法的复杂性REVISE（方法修改两个域之间的一条弧线）。对于一个域中的每个值，它正在检查第二个域的所有值。所以该REVISE方法的复杂度将是 d ² where d is maximum domain size。

现在，在最坏的情况下，会被REVISE调用多少次？最初，队列中有所有弧。每次REVISE调用时，都会从队列中删除一条弧线。那将是方法的调用。但我们也将弧线添加回队列。我们可以这样做多少次？好吧，只有当从弧指向的域中删除了一个值时，我们才会将弧添加回队列。一条弧指向一个域，因此我们只能将它添加到该域中值的数量。所以在最坏的情况下，我们将每条弧添加回队列 d 次。

REVISE最多调用 e + ed 次，其中e is number of arcs.

当我们把它们放在一起时，我们发现整个算法的复杂度是 O((e+ed)d ² )，也就是 O(ed ³ )。