基于不同啟發式策略的約束滿足問題求解研究

摘要:約束滿足問題是人工智能的重要研究方向。約束傳播技術和啟發式策略是影響約束求解算法效率的關鍵。對于大規模和大型具有結構化特征的問題，設計并運用有效的值序、變量序啟發式策略將大大縮減搜索空間，極大提高問題求解效率。文中對現在流行的靜態啟發式、動態啟發式和沖突驅動的啟發式等不同類別的啟發式采用標準庫問題實例進行適應性求解測試，并對各種啟發式策略進行性能評估。

關鍵詞:人工智能;約束滿足問題;弧相容;啟發式策略

中圖分類號:TP18 文獻標識碼:A 文章編號:1674-7712 (2012) 12-0123-03

一、引言

近年來，作為人工智能領域最活躍的研究分支之一，約束程序(Constraint Programming，CP)研究方向得到蓬勃發展。約束程序研究的核心問題是約束滿足問題(Constraint Satisfaction Problem，CSP)。目前，該領域出現了以約束傳播技術和針對大規模應用問題的啟發式策略為代表的研究新熱點。

相容性技術是約束傳播的代表技術，它在加速求解效率和壓縮求解空間上發揮著不可估量的巨大作用0。目前主流技術是弧相容性和路徑相容性技術。弧相容技術是相容性技術中應用最為廣泛的。1977年，Mackworth提出了著名的實現弧相容性的算法AC30。為得到最優的時間復雜度，Mohr和Henderson提出AC40，但以較大的空間復雜度為代價。此后Bessière相繼提出算法AC60，AC70和AC20010。

對于變量啟發式，早期主要是靜態變量啟發式(SVO)，代表是最小寬度(min width)和最大度(max degree)啟發式0;2001年Bessiere提出帶選擇函數的動態變量啟發式的一般框架0;2004年Boussemart等提出了沖突驅動的變量啟發式策略0;2007年，2008年Grims和Wallace共同提出了將值刪除作為基本傳播事件及與加權約束相結合沖突驅動的變量啟發式00。但對于多種啟發式策略的全面性能評估和對于問題的適應性研究，以及各種啟發式策略混合應用方面還有很大的研究空間。

二、約束滿足問題

約束滿足問題(Constraint Satisfaction Problem)常表示成一個三元組 。其中X是變量的有限集合，表示成 ; = 是變量值域的集合，其中 是變量 的值域; 是一個有限約束集合。約束滿足問題的求解是為變量集 中的每個變量從其有限論域中尋找一個值，使得約束集 中的所有約束被滿足。

通常可將約束滿足問題用約束圖的形式表示。圖1為地圖著色問題實例的約束圖。其中，數字表示二元約束滿足問題的變量;字母表示變量的論域;變量之間的直線代表二元約束關系，含義為這兩個變量不能取相同的值。

三、弧相容技術

為了提高效率，常在約束滿足問題的求解過程中應用約束傳播技術或相容性技術。弧相容技術是相容性技術中最為著名的。對于二元約束圖中的弧 ，稱它是弧相容的(Arc Consistency)，當且僅當對于變量 的論域中的每一個值 ，在變量 的論域中都存在一個值 ，使得 滿足 上的一元約束，并且 滿足 和 上的二元約束 。一個CSP是弧相容的，當且僅當它的約束圖中每一條弧都是弧相容的0。

1977年Mackworth提出了著名的弧相容算法AC-30。AC-3長久以來被廣泛應用。下面我們給出AC-3的算法框架:

Algorithm 3.1 AC-3( )

while do

if revise( ) then

if then return 1

else

return true

Algorithm 3.2 revise( ):boolean

flag=1

for each a do

if not such that then

delete from

flag=true

end if

end for

return flag

AC-3算法的時間復雜度下界為 ，最壞情況下的時間復雜度為 ，其空間復雜度為 。其中 是約束的個數， 是變量域的規模， 是變量的個數。

四、啟發式策略

啟發式策略作為一種展望策略，引導或者決定接下來要實例化哪個變量或將論域中的哪個值賦給變量。對于大規模的約束滿足問題的求解，啟發式的應用能夠有效壓縮求解空間，快速得到問題的解或者指出問題無解。我們研究了當前流行的各種變量啟發式策略，將其分類為:靜態變量啟發式、動態變量啟發式和沖突驅動的變量啟發式。

(一)靜態變量啟發式

靜態變量啟發式策略(SVOs)中，變量在搜索的整個過程中保持不變的排序，僅僅使用問題初始狀態的結構化信息。最簡單的靜態啟發式策略是字典序(lexico)，即將變量按字典序排序。在約束圖中，相互間有約束關系的變量稱為彼此的鄰居。變量的度定義為鄰居的個數。啟發式策略deg(max degree)根據度的降序將變量排序。

其他的靜態變量啟發式策略有min width啟發式策略和min bandwidth啟發式策略等。

(二)動態變量啟發式

動態變量啟發式策略(DVOs)是非常高效的，因此受到更多的關注。這些啟發式策略考慮搜索過程中每一時刻問題當前狀態的信息。

最早廣為人知的動態啟發式策略是由Haralick和Elliott提出的dom啟發式，它選擇有著最小剩余域的變量。另一種常用動態啟發式是deg的一個動態變種叫做ddeg，它選擇有最大動態度的變量，即被最多的未被賦值的變量所約束的變量。將 和 (或ddeg)結合而衍生出的復合啟發式稱作 (或dom/ddeg)。這些啟發式選擇當前域大小與靜態度(動態度)的比值最小的變量。這兩種復合啟發式結合了變量的多重信息，可以顯著地提高搜索性能。

當應用啟發式時，經常見到這樣的現象:兩個或多個變量是等價的。如用dom啟發式時，會遇到有兩個變量 與 的域大小相等且最小。這時需要一種策略來打破這一關系。常見的能打破dom啟發式中這種關系的是lexico，(dom+lexico組合的啟發式)它選在同時有最小域的多個變量中按字典序排在第一位置的那個變量。

(三)沖突驅動的變量啟發式

2004年Boussemart等受SAT求解器的啟發，提出了沖突驅動的變量啟發式策略0。在啟發式中為每一個約束設置一個權重，并初始化為1。在搜索期間，當某個約束導致一個失敗(即變量的域為空DWO)時，該約束的權重加1。每個變量有一個動態變化的權度，定義為與該變量關聯的所有約束的權重之和。變量的權度由下式計算:

| (1)

其中， 表示約束 中未實例化的變量， 是約束 的權重， 是 所約束的變量。

權度變量啟發式(wdeg)選擇有最大權度的變量。同時，我們可以結合域的信息，進而產生一種復合啟發式 ，它選擇域大小與權度的比值最小的變量。

沖突驅動的啟發式wdeg和 為每個約束設置一個計數器，用于記錄權重。每當約束導致一個DWO，約束的權重加1。這個動態過程可由下述算法描述:

Algorithm 4.1 revice( ):boolean

for each a do

If not such that then

Delete from

responsibleConstraint[ ][ ]=

end if

end for

if then

Weight[ ]++

end if

return

經驗表明上述啟發式對大部分問題非常有效，但其權重的分配不總是合理的，它們沒有考慮到有的約束雖沒有直接導致DWO，但它起到間接作用。為此，Grims和Wallace共同提出了將值刪除作為基本傳播事件并與加權約束相結合的沖突驅動變量啟發式00。根據權重計算方法的不同，有三種沖突驅動的變量啟發式 。其權重的計算可由下述算法描述:

Algorithm 4.1 revice( ):boolean

for each a do

If not such that then

Delete from

responsibleConstraint[ ][ ]=

end if

end for

if then

//

for each

//

//

end for

end if

return

對于上述啟發式，我們可以定期的老化約束的權重，即讓約束的權重周期性的除以一個大于1的小常數。從而給予最近發現的沖突更大的影響力，這樣的策略有助于提高性能。

五、啟發式策略測試

為得到各種變量啟發式策略的適應性數據，我們采用標準庫問題對算法進行測試。主要通過執行效率(CPU時間)和搜索樹節點數來比較各種啟發式策略在不同規模問題上的性能。測試的環境為:Lenovo ideapad Y450，Inter Core(TM) Duo 2.13GHz CPU，2.00G RAM;Windows 7 home basic，Visual C++6.0。

從結果分析，靜態變量啟發式為弱啟發式，并不能很好地提高求解效率，甚至當問題規模太大時得不到解。動態啟發式策略(dom/deg、dom/ddeg等)對于提高求解效率有著不錯的效果。沖突驅動的變量啟發式(wdeg、dom/wdeg等)由于其算法中有冗余計算，在問題規模較小時并不能體現其優勢，效果有時不如其他啟發式;但當問題規模變大時，沖突驅動的變量啟發式能顯著提高求解效率。

六、結束語

相容性技術和啟發式策略在CSP求解過程之中發揮著巨大的作用，決定著求解算法的性能。本文論述了最具代表性的相容性技術——弧相容技術。對現在流行的變量啟發式進行了分類，并使用標準庫問題對不同啟發式策略進行測試，得到其適應性數據。未來的研究工作中，我們將應用更具結構化特征的隨機問題對各類啟發式進行效率評估，探索建立一個面向問題結構化特征結合多種啟發式策略的高效約束求解算法框架。

參考文獻:

[1]P.van Beek，F. Rossi，and T.Walsh editors. Handbook of constraint programming.Elsevier，2006

[2]A.K.Mackworth.Consistency in networks of relations.Artificial Intelligence，1977，8:99-118

[3]R.Mohr and T.C.Henderson.Arc and Path Consistency Revised，Artificial Intelligence，1986，28:225-233

[4]C.Bessière.Arc consistency and arc consistency again.Artificial Intelligence，1994，65:179-190

[5]C.Bessière，E.C.Freuder，and J.C.Régin.Using constraint metaknowledge to reduce arc consistency computation.Artificial Intelligence，1999，107:125-148

[6]C.Bessière and J.C.Régin.Refining the basic constraint propagation algorithm.In:Proceedings of IJCAI，2001:309-315

[7]E.C.Freuder.A sufficient condition for backtrack-free search.Journal of the ACM，1982，29(1):24-32

[8]C.Bessière，A.Chmeiss，and L.Sais.Neighborhood-based variable ordering heuristics for the contraint satisfaction problem.In Proceedings of the 7th Conference on Principles and Practice of Constraint Programming (CP-2001)，pages2001:61-75

[9]F.Boussemart，F.Hemery，C.Lecoutre，and L.Sais.Boosting systematic search by weighting constraints.In Proceedings of 16th European Conference on Artificial Intelligence (ECAI-2004)，pages 146-150，Valencia， Spain，2004

[10]D.Grimes and R.J.Wallace.Sampling strategies and variable selection in weighted degree heuristics.In Proceedings of the 13th Conference on Principles and Practice of Constraint Programming (CP-2007)，pages，2007，831-838

[11]R.J.Wallace and D.Grimes.Experimental studies of variable selection strategies based on constraint weights.Journal of Algorithms，2008，63(1-3):114–129

[12]M.Correia and P.Barahona.On the integration of singleton consistency and look-ahead heuristics.In Proceedings of the ERCIM workshop-CSCLP，pages，2007，47-60