AC-3 是否解决了路径一致性问题？

Question

我看AC-3 in Artificial Intelligence: A Modern Approach的伪代码的时候，我以为它解决了路径一致性和弧一致性。但是书上说路径一致性是通过一个算法PC-2来解决的。我错过了什么？

为什么AC-3不足以解决路径一致性问题？

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

提前致谢:)

Answer 1

我想我已经找到问题所在了。我误解了路径一致性的含义。

我以为

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

等同于

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

这就是为什么我认为 AC-3 足以解决路径一致性问题。但事实并非如此。

给出(1)和(2)的含义：

(1) 表示，对于每一对符合{Xi, Xj}约束的赋值{a, b}，在Xk的域中都有一个值c这样 {a, c} 和 {b, c} 满足 {Xi, Xk} 和 {Xj, Xk}

的约束

(2) 可以这样解释（这样更容易看出差异）：对于每对赋值 {a, b} 与 {Xi, Xj} 上的约束一致（Xi 是弧-与 Xj 一致，这个可能不准确，但可以凑合），在 Xk 的域中有一个 c 使得 {a, c} 满足 {Xi, Xk 的约束} （Xi 与 Xk 弧一致），Xk 的域中有一个 d 使得 {b, c} 满足对 {Xj, Xk} 的约束（Xj 是弧-与Xk一致)

现在很容易看出区别：在 (2) 的解释中，c 和 d 可能是 Xk 域中的不同值。只有当c等于d时，(2)才等价于(1)

所以AC-3只够解决(2)，解决路径一致性就太松了

谁能告诉我这次我的理解对不对？谢谢 :)

Answer 2

应该是{b,d}满足对{xj,xk}的约束。（xj与xk弧一致）

AC-3 是否解决了路径一致性问题？

Does AC-3 solve path consistency?

artificial-intelligence

constraints