CSP-Constraint Satisfaction Problem
基本介紹
- 中文名：約束滿足問題
- 外文名：CSP
- 全稱：Constraint SatisfactionProblem
- 例如：圖中結點的值
- 關鍵字：人工智慧
基本信息,其他信息,
基本信息
CSP（約束滿足問題）：由一個變數集合和一個約束集合組成。問題的一個狀態是由對一些或全部變數的一個賦值定義的完全賦值：每個變數都參與的賦值。問題的解是滿足所有約束的完全賦值，或更進一步，使目標函式最大化。
CSP={V,D,C}
變數：V={V1,…,VN}
例如：圖中結點的值
域：每個變數能取的d個值的集
例如：D={R,G,B}
約束：C={C1,…,CK}
每個約束由一組變數與一列該組變數允許取的值組成
例如：[(V2,V3),{(R,B),(R,G),(B,R),(B,G),(G,R),(G,B)}]
通常隱式地定義約束，即，定義一個函式來測試一組變數是否滿足該約束
例如：對每條邊(i,j)，有ViVj
CSP的解：每個變數有一個滿足所有相關約束的值
特點：
狀態的分解代表：一組變數及其值
利用狀態的結構和通用啟發方式
通過確定違反約束的變數與值組合可取消大部分搜尋空間
其他信息
約束滿足問題(CSP-Constraint Satisfaction Problem)是人工智慧研究領域的一個重要分支,現實生活中的很多問題,都可以用約束滿足問題來建模,如視覺(Vision),調度中的資源分配(Resource allocation),時序推理(Temporal reasoning)等.約束滿足問題通常都是NP-hard問題,在其眾多求解算法中,基於回溯的搜尋算法(BT-backtracking algorithm)是一個完備的核心算法.該算法在選擇實例化變數時,採用深度優先策略,若相容性檢查失敗則啟動回溯機制,並通過引入展望(look-ahead)和回顧(look-back)兩種模式,顯著地提高了搜尋效率[1].基於衝突的向後跳轉[2]和動態的回溯算法[3]等是回顧模式類的搜尋算法;基於相容性技術的算法是展望模式類的搜尋算法.而弧相容(AC-arc consistency)則是眾多相容性算法中一個高效的相容性技術[4],如算法AC3[5],AC4[6],AC2001[7]等.由於弧相容維護(MAC-maintaining arc consistency)，具有高效的求解效率和低額空間代價的特點,所以MAC是求解約束滿足問題的一個主流搜尋技術.
