csp[約束滿足問題]

CSP-Constraint Satisfaction Problem

基本信息

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),有ViVj

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是求解 約束滿足問題的一個主流搜尋技術.

相關詞條

相關搜尋

熱門詞條

聯絡我們