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

關(guān)鍵詞:人工智能;約束滿足問題;弧相容;啟發(fā)式策略

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

一、引言

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

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

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

二、約束滿足問題

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

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

三、弧相容技術(shù)

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

1977年Mackworth提出了著名的弧相容算法AC-30。AC-3長久以來被廣泛應(yīng)用。下面我們給出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算法的時間復(fù)雜度下界為 ，最壞情況下的時間復(fù)雜度為 ，其空間復(fù)雜度為 。其中 是約束的個數(shù)， 是變量域的規(guī)模， 是變量的個數(shù)。

四、啟發(fā)式策略

啟發(fā)式策略作為一種展望策略，引導(dǎo)或者決定接下來要實例化哪個變量或?qū)⒄撚蛑械哪膫€值賦給變量。對于大規(guī)模的約束滿足問題的求解，啟發(fā)式的應(yīng)用能夠有效壓縮求解空間，快速得到問題的解或者指出問題無解。我們研究了當(dāng)前流行的各種變量啟發(fā)式策略，將其分類為:靜態(tài)變量啟發(fā)式、動態(tài)變量啟發(fā)式和沖突驅(qū)動的變量啟發(fā)式。

(一)靜態(tài)變量啟發(fā)式

靜態(tài)變量啟發(fā)式策略(SVOs)中，變量在搜索的整個過程中保持不變的排序，僅僅使用問題初始狀態(tài)的結(jié)構(gòu)化信息。最簡單的靜態(tài)啟發(fā)式策略是字典序(lexico)，即將變量按字典序排序。在約束圖中，相互間有約束關(guān)系的變量稱為彼此的鄰居。變量的度定義為鄰居的個數(shù)。啟發(fā)式策略deg(max degree)根據(jù)度的降序?qū)⒆兞颗判颉?/p>

其他的靜態(tài)變量啟發(fā)式策略有min width啟發(fā)式策略和min bandwidth啟發(fā)式策略等。

(二)動態(tài)變量啟發(fā)式

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

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

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

(三)沖突驅(qū)動的變量啟發(fā)式

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

| (1)

其中， 表示約束 中未實例化的變量， 是約束 的權(quán)重， 是 所約束的變量。

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

沖突驅(qū)動的啟發(fā)式wdeg和 為每個約束設(shè)置一個計數(shù)器，用于記錄權(quán)重。每當(dāng)約束導(dǎo)致一個DWO，約束的權(quán)重加1。這個動態(tài)過程可由下述算法描述:

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

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

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

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

五、啟發(fā)式策略測試

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

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

六、結(jié)束語

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

參考文獻:

[1]P.van Beek，F(xiàn). 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(xiàn).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