1、約束滿足問題(Constraint Satisfaction Problem-CSP)是人工智能中的一個重要研究領域,是近年來很多學者所研究的一個非常活躍的內(nèi)容和方向。實踐證明,在我們周圍的世界里,“約束”廣泛的存在于生活和科研的各個領域當中,比如地圖著色問題、生產(chǎn)調(diào)度問題、產(chǎn)品配置、路由選擇、物流規(guī)劃、人力資源管理問題等等。但在實際應用的時候,常常會遇到約束條件過多的情況,這種情況往往會使得問題無解。此時需要求出一個最優(yōu)解使其最好的滿

2、足所有約束,即代價最少。因此研究者們便提出了加權約束滿足問題(Weighted Constraint Satisfaction Problem, WCSP)的概念。CSP是WCSP的一個特例。對于經(jīng)典CSP的求解是NP難的,因為在對CSP的求解時產(chǎn)生結果的階段往往因過度回溯而陷入困境。減少回溯次數(shù)甚至實現(xiàn)無回溯搜索變得意義重大。而對WCSP的求解也是NP難的,在利用單純遺傳算法(GA)對WCSP的求解時,由于WCSP自身的結構特點使得遺

3、傳算法向最優(yōu)解收斂的速度低,對最優(yōu)解的搜索能力不強。鑒于此,本文針對CSP與WCSP的求解進行了研究,取得的主要成果如下:
　　(1)ZBDD是描述和操作稀疏二進制向量的一種高效技術,是OBDD的一種擴展形式,其更適用于高效的處理組合集合問題。以零壓縮二叉決策圖(ZBDD)作為存儲結構,基于樹分解思想給出了CSP的一種新的求解方法。通過對CSP的ZBDD描述,將CSP的求解轉(zhuǎn)變成對組合集合的交、并、補等基本操作,在一次操作內(nèi)實現(xiàn)多

4、條約束的并行處理,大大的提高了算法的效率。
　　(2)給出了基于弧相容的ZBDD符號求解方法,首先提出的是一種求解最小環(huán)切割集的Get_CutSet算法,來構造原CSP的樹形結構并實現(xiàn)無回溯搜索,該算法能夠找到目前最小的環(huán)切割集。并且在單弧相容(Singleton AC)的基礎之上提出了比弧相容強度更大的環(huán)相容(LC)的概念;然后通過環(huán)相容技術對環(huán)切割集中的變量進行實例化,得到原問題的局部解,并證明了該局部解一定可以擴展為原CSP