CODEWITHSUNDEEP
algorithmartificial-intelligenceconstraint-satisfaction
Enrico Cortinovis
Enrico Cortinovis

Reputation: 861

Time complexity of AC-3 algorithm

This is the AC-3 algorithm's (pseudo) code:


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

I'm studying on the book Artificial Intelligence - A Modern Approach (4th edition) and this is what it says regarding this algorithm's time complexity:

Assume a CSP with n variables, each with domain size at most d, and with binary constraints (arcs). Each arc (Xi, Xj) can be inserted in the queue only d times because X_i has at most d values to delete. Checking consistency of an arc can be done in O(d^2) time, so we get O(cd^3) total worst-case time.

How would you go about calculating the time complexity of this algorithm? Where was I wrong?

Thank you.

Upvotes: 0

Views: 1164

Answers (1)

May
May

Reputation: 1

I don't understand how checking consistency of a single arc can be done in O(d^2).

If we look at the REVISE function in the AC-3 algorithm, it says:

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

We execute the for loop in the 1st line above d times and the 2nd line also d times in worst case if we had to search every value in Dj to find a satisfying assignment (x, y) for the constraint (or to determine no satisfying assignment possible).

So that makes O(d^2) to check each arc using AC-3.

Upvotes: 0

Related Questions