当我阅读《人工智能：现代方法》中AC-3的伪代码时，我以为它不仅能解决弧一致性，还能解决路径一致性。但书中说路径一致性是由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 truefunction 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提前感谢:)
回答：
我想我已经找到了问题所在。我误解了路径一致性的含义。
我以为
(1) {Xi, Xj}与Xk路径一致
等同于
(2) Xi与Xj弧一致，Xi与Xk弧一致，Xj与Xk弧一致。
这就是为什么我认为AC-3足以解决路径一致性问题。但事实并非如此。
解释(1)和(2)的含义：
(1)表示，对于{Xi, Xj}上的每个一致的赋值对{a, b}，在Xk的域中存在一个值c，使得{a, c}和{b, c}满足{Xi, Xk}和{Xj, Xk}上的约束
(2)可以这样解释（这使得差异更容易看出）：对于{Xi, Xj}上的每个一致的赋值对{a, b}（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)，但对于解决路径一致性来说，它的要求太宽松了
这次谁能告诉我我的理解是否正确？谢谢:)
