AI 筆記27 - Constraint Propagation with Arc Consistency

Forward checking不夠早發現failure

forward checking無法避免以下的case:

可以看到第三次的assignment使得SA和NT同時都只剩下藍色，但是兩者是相鄰的，所以不能只剩下同一種顏色來assign，這條assignment路徑必定是錯的，這在forward checking無法知道，因爲forward checking只在assignment後檢查是否造成其他variable沒有任何可以assign的value（其實當然也可以檢查這個，但仍然無法檢查其他的constraint是否被違反了）。

Maintain Consistency

擴充forward checking的範圍也無事無補，除非每次assignment都能maintain constraint 成立。所以一個系統性的方法稱為consistency產生了。

我們之前說會把CSP畫成hypergraph，所以就是要graph上的所有node/arc 都符合目前所有的constraint，這樣稱為consistent。

Node consistency: 如果某個constraint只對某個variable產生作用，稱為unary constraint，則我們在graph上只需要maintain "node consistency"，因為只對某一個node（variable）發揮作用。

所謂maintain consistency意指“所有domain values Di for variable Xi"都必須要符合constraint!

Arc consistency: 如果constraint同時牽涉到兩個variables，稱為binary constraint，則我們在graph上要maintain "arc consistency"，意思是如果arc某一端的所有domain values，都必須在另一端找到符合constraint的value。

這邊應該是為了先固定某一個variable X，所以assign value給 X的時候，我們要確保Y還有可以assign的value。

Path consistency: 這是arc consistency的generalization。

Arc Consistency Propagation

如果我們現在檢查兩個相鄰的區塊SA和NSW，其在hypergraph上會有一條arc連接，因為我們有鄉鄰不能同色的constraint：

要maintain SA -> NSW arc consistency，我們檢查所有可能的domain values for SA，發現如果SA選了藍色，NSW可以選紅色來達成arc consistency，所以的確SA -> NSW是arc consistent的。

反過來看 NSW -> SA並非arc consistent，因為藍色在NSW中並沒有合法的SA 顏色可以對應！這時候要幹嘛？？？？ 把藍色從NSW中拿掉！ 這樣在search時候就保證NSW -> SA是 arc consistency，就不會在後面遇到需要backtrack：

這個過程可以對所有的arc施作，可以看到這其實就是一種propagation。

AC3 Algorithm

這是接受一個binary CSP:

可以看到這是一個一直revise的過程，直到所有的arc都consistent為止。如果某個arc被revised了，則要把端點的所有neighbor都加入queue中，做constraint propagation，因為revised arc代表某個domain value在Xi中被消除了，這可能影響到與此Xi連接的nodes。

running time complexity如下：

Expand BTS with constraint propagation (inference)

之前提到BTS就是一個DFS，把constraint propagation (inference)部分加入BTS過程中，可以大大減少backtrack的數目：