0

这是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

我正在研究《人工智能 - 现代方法》（第 4 版）一书，这就是它关于该算法的时间复杂度的说法：

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

  • 我知道每条弧(Xi, Xj)只能在队列中插入d次（因为Xi最多有d个值要删除，在最坏的情况下可以一个一个删除）。
  • 我不明白如何在O(d^2). 相反，我认为它可能是O(cd)，因为在最坏的情况下，它可以从所有变量的域中一一删除所有值。
  • 我不明白它给出的最坏情况总时间，即O(cd^3). 在这种情况下，在我看来，它本来可以是O(cd^2).

您将如何计算该算法的时间复杂度？我哪里错了？

谢谢你。

4

1 回答 1

0

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

如果我们查看 AC-3 算法中的 REVISE 函数，它会说：

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

如果我们必须搜索 Dj 中的每个值以找到满足约束的分配 (x, y)（或确定没有满足的分配），我们在第一行执行for循环 d 次以上，第二行执行循环可能的）。

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

于 2022-02-23T23:43:16.143 回答