約束編程(CP)是用于建模和求解組合約束問題的通用且靈活的框架。表約束(也稱為擴展約束)明確表示它們所涉及的變量的值的允許組合作為元組序列,稱為表。表約束理論上可以編碼任何類型的約束,并且是約束編程中最有用的約束之一。這些約束可以從已經(jīng)從配置問題中的數(shù)據(jù)庫讀取的數(shù)據(jù)生成,或者可以編碼用戶的偏好以及其他應(yīng)用程序。表約束將任意約束明確定義為一組解(元組)或非解。因此,表約束的空間與元組的數(shù)量成比例。簡單表縮減(STR)通過維護有效元組的表來動態(tài)地縮減表大小,已被證明可以有效地維持廣義弧一致性(GAC)�；赟TR改進的STR2和STR3算法是當(dāng)前主流的廣義弧一致性算法,STR2和STR3在不同類型的實例下各有優(yōu)勢。該領(lǐng)域最近的一個重大改進是在表約束中使用比特向量來表示元組的有效性,在為變量值尋找支持時使用高效的比特并行操作。算法STRbit和Compact-Table都是結(jié)合了STR和比特向量操作的優(yōu)點,已經(jīng)顯示出比過去十年中開發(fā)的最佳GAC算法快一個數(shù)量級。表約束有一個主要的缺點:存儲它們所需的內(nèi)存空間可能會隨著約束元數(shù)而呈指數(shù)增長,為了解決這個問題,相繼提出各種表壓縮方法。當(dāng)表約束規(guī)模...

【文章頁數(shù)】：54 頁

【學(xué)位級別】：碩士

圖2.3MAC算法求解一個四皇后問題過程

圖3.1稀疏集表示

圖3.2STR2算法偽代碼

圖3.4Greedy-Compress算法Greedy-Compress算法以全長支持（即提及所有r變量）開始，并嘗試使用上述基本步驟將它們壓縮為大小為r-1變量的短支持

本文編號：3882829