2015年4月19日 星期日

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



沒有留言:

張貼留言

技術提供:Blogger.