AI - Ch5 CSP(1), 限制滿足問題 Constraint Satisfaction Problems

滿足條件限制的問題 (Constraint satisfaction problem ,CSP)為一組狀態必須滿足於若干約束或限制的目標，這個問題有很多可能的解。CSPs經常表現出高複雜性，需要結合啟發式搜索和搜索方法來在一個合理的時間內解決問題。

與CSP有密切的關連性的學科有Linear programming(LP; 線性規劃)、Integer Linear Programming(ILP; 整數規劃)、NonLinear Programming(NLP; 非線性規劃)、數值分析理論等。CSP模型可用於作業研究(Operations Research , OR)、網路流量(network flows)、最佳化問題(optimization problems)等。

CSP的形式定義
CSP問題定義為一個3-tuple$( X, D, C )$, $X$是一組變量, $D$值域, $C$ 是一個約束組。

$X_1,...,X_n$ : 變數，Finite set of variables.
$D_{x_{1}},...,D_{x_{n}}$ :值域，Nonempty domain of possible values for each variable.
$C_1,...C_m$ : 限制，Finite set of constraints, Each constraint $C_i$ limits the values that variables can take.

ex : 將map coloring公式化(正規劃)為CSP

我們將各區域定義成變數(Variables)

Variables : $V = \{WA, NT, Q, NSW, V, SA, T\}$

每個變數的值域(Domains)

Domains : $D_i = \{ red, green, blue \}$

將值賦予變數時的限制(Constraints)相鄰區域必須不同顏色, $WA \neq NT$

$(WA, NT) = \{ (red, green), (red, blue), (green, red), … \}$

CSP著名例子

八皇后問題 (8-Queens problem)
數獨(Sudoku)
地圖著色 (map coloring)
排班問題
資源配置最佳化問題

CSP的圖形表示法

a node per variable
a arc per constraint

限制的種類

Unary constraints involve a single variable. e.g. $SA \neq green$
Binary constraints involve pairs of variables. e.g. $SA \neq WA$
Higher-order constraints involve 3 or more variables. – 可以將其轉換為二元限制(binary constraints)

CSP問題轉換成一般搜尋問題的原因(想法)

一開始的暴力法：以下圖地圖著色為例，總共有$6! \times 3^6 $個樹葉節點，在每個樹葉節點檢查其配置的合法性(是否違反限制)。
暴力法中考慮可交換性(Commutativity)：順序不重要，一次只需考慮一個變數的值域配置，因此總共有$3^6$個樹葉節點。
暴力法中考慮空間複雜度：依序為每個區域配置顏色，每次考慮配置顏色時，必須符合限制的要求。此方法可自動縮減很多搜尋的狀態空間(state space)。

原路返回搜尋 Backtracking search

Similar to Depth-first search (DFS)

想法：Chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.

Uninformed algorithm

效率不好 (時間複雜度為指數)
需用啟發式搜尋改善

增加CSP效率的方法(啟發式)
和深度優先搜尋類似，此法時間複雜度為指數，因此常搭配啟發式搜尋法使用

挑選變數(Variable)的順序

最少剩餘值 (Minimum remaining value, MRV) : 選擇合法取值最少的變數

鄰接度啟發式(degree heuristic) : 選擇對其它變數限制最大的變數來降低未來選擇其它變數的分支度，以限制圖來說，即以分支度最大的節點為搜尋的初始節點。

挑選值(Value)的順序

最少限制值(Least constraining value) : 對於後續變數的配置，預留最大的彈性

限制傳播(Constraint Propagation) : 搜尋前先進行檢查

前向檢驗(Forward checking, Restricted arc consistency) : 早一步偵測到某個狀態下無法避免的失敗。對於未配置值的變數，保持其合法值的追蹤，當某一個狀態下，有任何一個變數已經沒有任何一個合法值時，即中斷搜尋。

雖然前向檢驗能檢驗出許多矛盾，它還是不能檢驗出所有的矛盾。原因是它使得目前變數是邊相容的，但是不向前看而使得所有其他變數變得邊相容的。例如，下圖中的第三行。它顯示出當WA是red、Q是green的時候，NT和SA都被迫是blue。前向檢驗向前看得不夠遠而沒能注意到這是個不相容(NT及SA為相鄰)，所以不能有相同值。

進階用法，Arc-consistency, Path-consistency, i-consistency，下一章詳述。

[舉例] 4-Queens，此例來說，利用Forward checking即可找到一組解，連搜尋都不需要。

Reference
wiki - Constraint satisfaction problem
http://en.wikipedia.org/wiki/Constraint_satisfaction_problem

AI課程投影片及作業
http://www.csie.ntu.edu.tw/~ai2007s/slides.html

限制滿足問題
http://www.afl.fit.edu.tw/Kuei/Slides_AI/6-Constraint%20Satisfaction%20Problems-101-03-30.pdf

Pages

2015年4月19日星期日