AC-3解決路徑一致性問題嗎？

Question

當我讀取AC-3 in Artificial Intelligence: A Modern Approach的僞代碼時，我認爲它解決了路徑一致性和弧一致性問題。但是這本書說路徑一致性是通過算法PC-2解決的。我錯過了什麼？

爲什麼AC-3不足以解決路徑一致性問題？

下面是提前:)

Answer 1

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 

感謝的代碼，我想我已經找到了問題的所在。我誤解了路徑一致性的含義。

我想

(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）意味着，對於每一對分配{a, b}與{Xi, Xj}約束一致的，有一個值c在Xk這樣的域該{a, c}和{b, c}滿足於{Xi, Xk}和{Xj, Xk}約束

（2）可以以這種方式（這使得它更容易看到的差）來解釋：每對分配{a, b}與{Xi, Xj}約束一致（Xi與Xj弧形一致，這個可能不準確，但可以做），Xk的域中存在c，使得{a, c}滿足約束條件（X1與Xk是弧一致的），並有在Xk這樣{b, c}滿足制約{Xj, Xk}域中的d（XJ是弧一致XK系列）

可以很容易看到現在的區別：在（2），c和d解釋在Xk的域中可以是不同的值。只有當c等於d，（2）等價於（1）

所以AC-3僅用於解決足夠的（2），但它太鬆懈解決路徑的一致性

誰能告訴我是否我理解是正確的，這個時候？ Thx :)