AC-3算法的时间复杂度

Question

这是AC-3算法的(伪)代码：

function AC-3(csp) returns false if an inconsistency is found and true otherwise
    queue ← a queue of arcs, initially all the arcs in csp
    while queue is not empty do
        (Xi ,Xj ) ← Pop(queue)
        if Revise(csp,Xi ,Xj ) then
            if size of Di = 0 then return false
            for each Xk in Xi .Neighbors− {Xj } do
                add (Xk,Xi) to queue
    return true

function Revise(csp,Xi ,Xj ) returns true iff we revise the domain of Xi
    revised ← f alse
    for each x in Di do
        if no value y in Dj allows (x, y) to satisfy the constraint between Xi and Xj then
            delete x from Di
            revised ← true
    return revised

我正在研究“”一书，它是关于这个算法的时间复杂性的：

假设具有n个变量的CSP，每个变量的域大小最多为d，并且具有二进制约束(arcs)。每个弧(Xi，Xj)只能插入队列d次，因为X_i最多有d值要删除。在O(d^2)时间内可以对弧的一致性进行检验，从而得到O(cd^3)总最坏情况时间。

• I理解每个弧(Xi, Xj)只能插入队列d次(因为Xi最多可以删除d值，在最坏的情况下可以逐个删除)。
• --我不明白如何在O(d^2)中检查单个弧的一致性。我认为它可能是O(cd)，因为在最坏的情况下，它可以逐个删除所有变量域的所有值。
• ，我不明白它给出的最坏情况的时间，也就是O(cd^3)。在这种情况下，在我看来，它可能是O(cd^2).

你将如何计算这个算法的时间复杂度？我哪里错了？

谢谢。

Answer 1

我不明白在O(d^2)中如何检查单个弧的一致性。

如果我们看一下AC-3算法中的修正函数，它会说：

for each value x in Di:
   if no value y in Dj allows ...

我们在d次以上的第1行执行for循环，在最坏的情况下执行第2行，如果我们必须搜索Dj中的每个值来为约束找到满意的赋值(x，y) (或确定不满足的赋值可能)。

所以这使得O(d^2)用AC-3来检查每个弧。