AI - Ch6 CSP(2), 相容性與邊相容性 Local consistency

In binary CSPs, various consistency techniques for constraint graphs were introduced to prune the search space. The consistency-enforcing algorithm makes any partial solution of a small subnetwork extensible to some surrounding network. Thus, the potential inconsistency is detected as soon as possible.


節點相容性 (Node Consistency)
如果變數的值域中的每一個值都滿足變數的一元限制，則稱這個變數於這個CSP中是邊相容的。

• E.g. For variable X, its original domain is $\{0,1,2\}$. Now under the unary constraint that$ X > 0$, we reduce the domain to $\{1,2\}$.
• It is always possible to satisfy all unary constraints by running node consistency.

邊相容性 (Arc Consistency)
如果變數的值域中的每一個值都滿足變數的二元限制，則稱這個變數於這個CSP中是邊相容的。注意邊相容性有方向性，也就是說，SA->NSW具邊相容性，並不代表NSW->SA具邊相容性。

• E.g. A binary constraint$ Y=X^2$, where$ X$ and$ Y$’s domain is $\{0,1,2,3,4,5,6,7,8,9\}$. The constraint is explicitly:$ <(X,Y), {(0,0),(1,1),(2,4),(3,9)}>$
• It is always possible to transform a CSP to a CSP with only binary constraints.

路徑相容 (Path-Consistency, 3-Consistency)
路徑相容藉由檢視三倍的變數所推論出的間接性限制來收緊二元限制 。

如果對每一個賦值$\{X_i = a, X_j = b\}$與在$\{X_i, X_j\}$上的限制，有一個賦值$X_m$滿足在$\{X_i, X_m\}$與$\{X_m, X_j\}$上的限制。則稱一個雙變數集合$\{X_i, X_j\}$對第三個變數$X_m$ 是路徑相容的。因為你可以想像成一條從 $X_i$ 到 $X_j$ 的路徑而 $X_m$ 位在路中間。

K-相容 (K-Consistency)
用k相容的概念可以定義更強的傳播形式。如果對於任何k-1個變數的相容賦值，第k個變數總能被賦予一個和前k-1個變數相容的值，那麼這個CSP問題就是k相容的。

AC-3演算法 (Algorithm For Arc‐Consistency #3)
最流行的邊相容性演算法是AC-3，該演算法的發明者 (Mackworth，1977)，使用「 AC-3」這個名字，是因為這是他論文中的第三個版本。要使每一個變數為邊相容的，AC-3演算法保留一個邊的集合(常以序列表示)供作考慮之用。

剛開始時，該佇列儲存了CSP中所有的邊。然後從佇列中隨意地挑出一個邊$(X_i, X_j)$並且讓$X_i$對$X_j$為邊相容的。如果這個操作對$D_i$沒什麼改變，該演算法就移到下一個$D_i$(使得該值域縮小些)。如果更動了$D_i$，那麼我們將所有$(X_k, X_i)$邊加進佇列之中，其中$X_k$是一個$X_i$的鄰居。要這樣做的原因是$D_i$的改變可能會讓$D_k$的值域進一步減縮，即使我們前面已經考慮過$X_k$了。

如果$D_i$被修改得一無所有，那麼我們知道整個CSP沒有相容的解答，而AC-3會立即地傳回失敗。否則，我們一直檢查，嘗試把數值從變數的值域移出，直到佇列中沒有任何邊。在那個時候，我們手上有個等價於原始CSP的CSP——它們兩個都有相同的解，在大多數情況下，邊相容的CSP的搜尋會快速些，因為它的變數有更小的值域。

AC-3複雜度分析
假設一個有$n$個變數的CSP，每個值域的大小最多是$k$，且具有$e$個二元限制(邊)。每個邊$(X_k, X_i)$可以被插入佇列最多$k$次(因為$X_i$最多有$k$個值可以刪除)。檢查一個邊的相容性可以在$O(k^2)$的時間內完成，所以我們得到最壞情況總時間是$O(ek^3)$。

procedure REVISE(Vi,Vj)
  DELETE <- false;
  for each X in Di do
    if there is no such Y in Dj such that (X,Y) is consistent,
    then
       delete X from Di;
       DELETE <- true;
    endif;
  endfor;
  return DELETE;
end REVISE

procedure AC-3
  Q <- {(Vi,Vj) in arcs(G),i#j};
  while not Q empty
    select and delete any arc (Vk,Vm) from Q;
    if REVISE(Vk,Vm) then
      Q <- Q union {(Vi,Vk) such that (Vi,Vk) in arcs(G),i#k,i#m}
    endif
  endwhile
end AC-3

Maintaining arc consistency removes many inconsistencies from the constraint graph but is any (complete) instantiation of variables from current (reduced) domains a solution to the CSP? If the domain size of each variable becomes one, then the CSP has exactly one solution which is obtained by assigning to each variable the only possible value in its domain. Otherwise, the answer is no in general. The following example shows such a case where the constraint graph is arc consistent, domains are not empty but there is still no solution satisfying all constraints.

Example:This constraint graph is arc consistent but there is no solution that satisfies all the constraints.

Reference

Consistency Techniques
http://ktiml.mff.cuni.cz/~bartak/constraints/consistent.html

github - satanupup
https://github.com/satanupup/epb/blob/master/0.Reference/ai/06148-06.txt

Speedup by Exploiting CSP Structures and Local Search
http://mooc.guokr.com/note/16533/