Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Does AC-3 solve path consistency? – Artificial Intelligence

When I read the pseudocode of AC-3 in Artificial Intelligence: A Modern Approach, I thought it solves path consistency as well as arc consistency. But the book says path consistency is solved by an algorithm PC-2. Did I miss something?

Why is AC-3 not sufficient enough for solving path consistency?

Here’s code for AC-3

function AC-3(csp) returns false if an inconsistency is found and true otherwise 
    inputs: csp, a binary CSP with components (X, D, C)
    local variables: queue, a queue of arcs, initially all the arcs in csp

    while queue is not empty do
        (Xi, Xj)←REMOVE-FIRST(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 ← false
    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

Thanks in advance:)

Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    I think I've figured out where the problem is. I misunderstood the meaning of path consistency.

    I thought

    (1) {Xi, Xj} is path-consistent with Xk

    is equivalent to

    (2) Xi is arc-consistent with Xj, Xi is arc-consistent with Xk, and Xj is arc-consistent with Xk.

    That's why I thought AC-3 was sufficient for solving path consistency. But it turns out not.

    Give the meaning of (1) and (2):

    (1) means that, for every pair of assignment {a, b} consistent with the constraint on {Xi, Xj}, there is a value c in the domain of Xk such that {a, c} and {b, c} satisfy the constraints on {Xi, Xk} and {Xj, Xk}

    (2) could be explained in this way (which makes it easier to see the difference): for every pair of assignment {a, b} consistent with the constraint on {Xi, Xj} (Xi is arc-consistent with Xj, this one may not be accurate, but could make do), there is a c in the domain of Xk such that {a, c} satisfies the constraints on {Xi, Xk} (Xi is arc-consistent with Xk), and there is a d in the domain of Xk such that {b, c} satisfies the constraints on {Xj, Xk} (Xj is arc-consistent with Xk)

    It's easy to see the difference now: in the explanation of (2), c and d could be different values in the domain of Xk. Only when c is equal to d, (2) is equivalent to (1)

    So AC-3 is only sufficient for solving (2), but it's too lax to solve path consistency

    Who can tell me whether my understanding is right, this time? Thx :)


  2. 0

    It should be {b,d}satisfies the constraint on {xj,xk} .(xj is arc-consistent with xk).

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search