蔣李鳴 呂佳宇 何哲華 馮澤斌

摘 要：約束滿足問題是人工智能領域中一個重要的研究方向，其研究結(jié)果在符號推理、系統(tǒng)診斷、真值維護系統(tǒng)、資源分配和產(chǎn)品配置等問題中有廣泛的應用。局部相容性定義了約束滿足問題在約束傳播過程中必須滿足的性質(zhì)，是約束傳播發(fā)展的主要方向。而對于較為復雜的相容性問題中的AC系列算法的改進可謂難上之難。本文圍繞著以弧相容、Singleton弧相容為代表的相容性技術(shù)和求解算法展開，主要針對AC-2001算法、SAC算法等進行優(yōu)化改進，重點基于啟發(fā)式進行改進，使之獲得了更快的篩選速度。尤其對于SAC算法，大大減少了約束檢查次數(shù)，獲得了較為成功的基于啟發(fā)式的改進結(jié)果。

關鍵詞：人工智能；約束滿足問題；啟發(fā)式；AC系列算法；約束檢查次數(shù)

中圖分類號：TP3-0 文獻標識碼：A

Abstract：In the field of artificial intelligence，the Constraint Satisfaction Problem （CSP） is an important research direction，whose study results are widely used in Symbolic Reasoning，System Diagnosis，Truth Maintenance System，Resource Allocation，and Product Configuration and so on.Local consistency，which defines the properties that CSP must satisfy in the process of constraint propagation，is the main development direction of constraint propagation.It is much more difficult to improve the performance of the complex series of AC algorithms about consistency problems.Based on the algorithms and consistency technology represented by arc consistency and singleton arc consistency，the paper focuses on the improvement of AC-2001 algorithm and SAC algorithm.The improvement is based on the heuristic algorithm to achieve higher filtering speed.Especially，the improvement of SAC algorithm is quite successful because of its obvious reduction of constraint checking times.

Keywords：artificial intelligence；Constraints Satisfaction Problem；heuristic；AC algorithms；constraint checking times

1 引言（Introduction）

約束滿足問題（Constraints Satisfaction Problem）[1]是人工智能領域中一個重要的研究方向，目前已廣泛地應用于人工智能的各個領域，包括定性推理、基于模型的診斷、自然語言理解、景物分析、任務調(diào)度等方面。局部相容性[2]定義了約束滿足問題在約束傳播過程中必須滿足的性質(zhì)，是約束傳播發(fā)展的主要方向。一方面，運用相容性技術(shù)對約束問題[3]進行預處理，刪除大量局部不相容的值，可以極大地壓縮問題的解空間[4]；另一方面，在搜索過程中保持局部相容性，可以有效地修剪搜索樹[5]，以一定的時空代價換取合理的問題規(guī)模的壓縮。

本文圍繞以弧相容、Singleton弧相容[6]為代表的相容性技術(shù)和求解算法展開，研究各個相容性算法?；∠嗳菟惴ň哂邢鄬^少的檢查次數(shù)，但其運行時間還可以進一步降低。而Singleton弧相容的SAC[1]算法，運行時間較長，并且檢查次數(shù)較多，尤其在檢查次數(shù)方面有很大的改進空間。

本文主要針對AC-2001[7]算法、SAC算法等進行優(yōu)化改進，重點基于啟發(fā)式進行改進，使之獲得更快的篩選速度。尤其對于SAC算法，我們在力圖優(yōu)化其運行時間的同時，大大減少其約束檢查次數(shù)，獲得較好的改進效果。

2 相關背景及工作（Backgrounds and tasks）

一個約束滿足問題（CSP）涉及對一個約束網(wǎng)絡[8]（Constraint Network，縮寫為CN）進行求解，即滿足CN中所有約束的那些參數(shù)論域賦值指派。約束確定了給定參數(shù)集的子集中被允許的賦值組合。

定義2.1（約束）[9]一個約束c是定義在稱為參數(shù)域的參數(shù)序列X（c）=（xi1，xi2，…，xi|X（c）|）上的關系，c是滿足其參數(shù)值元組?|X（c）|的?|X（c）|的子集。|X（c）|稱為c的元數(shù)，而?|X（c）|是?的|X（c）|次笛卡兒積。

定義2.2（解）[10]一個CSP的任務是為一個約束網(wǎng)絡找到一個或多個解。一個解是使得CN中所有約束都得到滿足的一組變量序列的賦值。一個解保證了對所有的約束都存在一個支持。

定義2.3（廣義弧相容，（G）AC[11]給定一個約束網(wǎng)絡N=（X，D，C），一個約束cC和一個參數(shù)xiX（c）。

（1）一個值viD（xi）是與D中c相容的iff存在一個值元組（vi=[{xi}]）滿足c。值元組稱為對c上（xi，vi）的一個支持。

（2）定義域D是c上xi（廣義）弧相容的iff D（xi）中所有的值與D中c是相容的（也就是，D（xi）{xi}（c∩X（c）（D）））。

（3）網(wǎng)絡N是（廣義）弧相容的iff D對C中所有約束上的X中的所有參數(shù)是（廣義）弧相容的。

定義2.4（Singleton弧相容，SAC）[1]標準約束網(wǎng)絡[6]N=（X，D，C）是singleton弧相容的（SAC）iff對所有的xiX，對所有的viD（xi），子問題N|xi=vi是弧相容的。如果子問題N|xi=vi是弧不相容的，則說（xi，vi）不是SAC的。

在此給出一些符號的定義：AC（P）表示問題P中所有弧不相容的值已被刪除，即對P執(zhí)行了弧相容后的問題；AC（P） =⊥表示P是弧不相容的； SAC（P）表示問題P中所有不是SAC的值已被刪除，即P是SAC的。

3 幾種AC系列經(jīng)典算法的改進（Improvement of AC Algorithms）

本文主要針對AC-2001算法、SAC算法等進行優(yōu)化改進，重點基于啟發(fā)式進行改進，使之獲得了更快的篩選速度。相關算法在Microsoft Visual C++ 6.0平臺下給出其具體實現(xiàn)，并制作清晰、合理、友好的界面，顯示測試結(jié)果，方便進行數(shù)據(jù)統(tǒng)計。保留實現(xiàn)原代碼，并提出啟發(fā)式改進和其他相關算法的改進技巧，優(yōu)化原代碼。生成大量的隨機測試用例及標準的Benchmark測試用例對其進行性能測試。最后通過統(tǒng)計數(shù)據(jù)并畫出相應柱狀圖對相關算法改進前后的性能進行對比，以評估算法改進的價值和成功與失敗的方面。

3.1 數(shù)據(jù)結(jié)構(gòu)隊列優(yōu)化原理

據(jù)我們觀察，原程序中幾乎所有的數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)都是用鏈表list實現(xiàn)的。然而，在代碼實現(xiàn)中，大多只用到了對數(shù)據(jù)結(jié)構(gòu)最前部和最尾部的操作。于是，我們比較了queue和list的性能和實現(xiàn)。代碼調(diào)試過程中，debug退出后，輸出面板會輸出大量內(nèi)存泄漏的信息。經(jīng)過排查，我們發(fā)現(xiàn)原因是使用了std：：list！進而，如果把list換成vector或者queue，所有內(nèi)存泄漏的問題都消失了。list的push_back的實現(xiàn)會導致內(nèi)部使用大量動態(tài)內(nèi)存分配，而vector也會在動態(tài)增長連續(xù)內(nèi)存長度的同時進行內(nèi)存復制。

然后我們對頻繁進行的插入操作進行測試，發(fā)現(xiàn)queue的性能明顯優(yōu)于list（無論是運行流暢度還是運行效率），可見queue是更好的選擇。我們又針對STL中的queue，list，vector頻繁訪問，即插入（尾部）與取出（頭部）操作時的效率進行了對比。從時間消耗上來看，queue最少，list與vector消耗相對較大，二者之間差別不大。

查找了相關資料后，了解到queue的底層是對dequeue的適配，那么也就是分段內(nèi)存實現(xiàn)存儲，這樣就不會像vector那樣需要重新分配內(nèi)存以及復制元素的操作了。但是list是雙向鏈表，按說實現(xiàn)首尾的插入與刪除應該也會很快，為何也相對queue而言很慢呢？

事實上，list的push_back的實現(xiàn)會導致內(nèi)部使用大量動態(tài)內(nèi)存分配，這個過程也相對耗時，所以導致了相對queue的較慢的結(jié)果。

這個數(shù)據(jù)結(jié)構(gòu)的優(yōu)化可以運用于所有AC系列算法中。

3.2 針對AC_2001：：revise2001算法的啟發(fā)式算法改進

2001年，Bessiere和Regin提出了對AC-3的改進算法AC-2001。AC-2001遵循AC-3同樣的框架，但是像AC-6[1]一樣，通過對約束上每個值存儲一個最小支持[12]實現(xiàn)了最優(yōu)性。然而，信息存儲和使用方式不同于AC-6，AC-2001不使用列表S[xj，vj]來存儲以vj作為cij上最小支持的那些（xi，vi），而是使用包含vj的指針Last[xi，vi，xj]。

AC-2001僅在 Revise函數(shù)和初始化階段不同于AC-3算法。初始化階段，AC-2001將Last[xi，vi，xj]初始化為某個比minD（xj）更小的虛擬值。在Revise2001中（算法3.4），當D（xj）中一個值vj發(fā)現(xiàn)支持cij上的（xi，vi）時，AC-2001把vj指派給Last[xi，vi，xj]（第4行）。下次（xi，cij）將被修改，僅當Last[xi，vi，xj]不在D（xj）中時為（xi，vi）尋找支持（第2行）。更重要的是，最優(yōu)性達到了因為D（xj）中小于Last[xi，vi，xj]的值不再檢查，它們以前已經(jīng)在被調(diào)用Revise2001時被檢查失敗了（第3行）。

算法AC2001：function Revise for AC2001

function Revise2001（in xi：variable； cij：constraint）：Boolean；

begin

1 CHANGEfalse；

2 foreach vi D（xi） s.t.Last[xi，vi，xj] D（xj） do

3 vj smallest value in D（xj）greater than Last[xi，vi，xj] s.t.（xi，vi） cij；

4 if vj exists then Last[xi，vi，xj]vj；

5 else

6 remove vi from D（xi）；

7 CHANGEtrue；

8 return CHANGE；

end

事實上，我們可以采用“每次記錄上次處理到的值，下次從該值開始遍歷”的思想，通過Last數(shù)據(jù)結(jié)構(gòu)記錄下標，下次遍歷不再檢查無用信息，而是“智能”地選擇合適的位置開始搜索，是一種啟發(fā)式算法的思想。

3.3 檢查次數(shù)優(yōu)化原理

經(jīng)過進一步分析，我們發(fā)現(xiàn)，對于那些不滿足某一xi的值vi，甚至不需要再第二重循環(huán)內(nèi)部對其進行檢查，我們可以在第一重循環(huán)之前對其進行預處理，將其存于新開的一個數(shù)組中（vector也可，新數(shù)組在效率上更佳）。這樣，在值分布密度并不那么大的時候，可以極其明顯地減少約束檢查次數(shù)，大幅降低時間復雜度。但此時必須注意Last數(shù)據(jù)結(jié)構(gòu)中記錄的內(nèi)容發(fā)生了改變，并不記錄上一次檢查到的值本身，而是記錄其對應在新的數(shù)組中的位置，否則算法運行會出錯。這個思想在第二重循環(huán)減少檢查次數(shù)，使得該啟發(fā)式算法更加“智能”地提高了運行效率。這個思想可以同時運用于AC-2001算法、SAC算法中。

3.4 二分啟發(fā)式優(yōu)化原理

另外，我們甚至還可以更進一步改進。在某些特定情況下，如約束滿足偏序關系，如簡單大于、小于關系時（事實上有時確實常遇到這種情況），約束便滿足了二分的性質(zhì)，即“第一個滿足約束的位置”前必然不會存在其他滿足約束的位置，并且在之前的值未滿足某一約束時，往后遍歷的值必然不會滿足之前較小的約束。于是這種情況下，我們在查找“下一個的第一個滿足約束的位置”的時候，可以采用二分查找的思想，這樣相對于普通遍歷地檢查可以大大減少檢查次數(shù)，可以將時間復雜度從O（d2）降低至O（d*log（d））！

運用二分的思想時，在數(shù)據(jù)規(guī)模較大、約束分布相對稀疏時，尤其奏效，可以大大減少檢查次數(shù)，降低時間復雜度。另外，由于SAC算法用到了不少AC-2001算法的方法，事實上對AC-2001算法的優(yōu)化也是對SAC算法的優(yōu)化，而SAC算法中可以進一步加入數(shù)據(jù)結(jié)構(gòu)隊列優(yōu)化和檢查次數(shù)優(yōu)化，進一步降低時間復雜度。而原本較慢的SAC算法，更加能體現(xiàn)出我們改進算法的成效，見后實驗及結(jié)果分析算法改進前后的對比。

3.5 時空復雜性分析

我們針對AC-2001算法、SAC算法進行改進，綜合運用上述四種改進方法。

對于這兩種算法來說，空間復雜度并不會發(fā)生改變，都以O（ed）的空間復雜度在二元標準約束網(wǎng)絡上實現(xiàn)弧相容性。

運用數(shù)據(jù)結(jié)構(gòu)隊列優(yōu)化原理，可以減少大量動態(tài)分配內(nèi)存的時間。尤其在插入刪除操作比較頻繁時，可以大大地降低時間復雜度。而檢查次數(shù)優(yōu)化原理，可以減少不必要的約束檢查次數(shù)，僅針對滿足某變量論域的值進行檢查而不考慮無關的值，尤其對于變量論域中值的分布較為稀疏時尤其適用，可以超越常數(shù)優(yōu)化地降低時間復雜度。接著，加入啟發(fā)式算法改進后，至此總的時間復雜度為O（ed2），以此來實現(xiàn)二元標準約束網(wǎng)絡上的弧相容性。而對于大多數(shù)實際情況，約束一般滿足一定的偏序關系，此時我們可以再在這兩個算法中加入二分啟發(fā)式優(yōu)化[13]，對于變量論域中的值的約束檢查不再采用單純的遍歷，而用二分的方式去進行檢查，可以使這一部分的時間復雜度從O（d2）降低至O（d*log（d））。此時，總的時間復雜度從O（ed2）降為O（ed*log（d）），實現(xiàn)了算法改進上的突破。

4 實驗及結(jié)果分析（Experiment and Result Analysis）

4.1 實驗測試說明

我們使用了兩類測試用例，分別是隨機生成的二元約束滿足問題和可供用戶選擇的Benchmark測試用例組。

對于隨機生成的數(shù)據(jù)的輸入：， 其中N表示變量的個數(shù)， D表示所有變量論域中的最大值，C表示約束個數(shù)，T表示每個約束中不相容的值對，p1表示約束的密度（Destiny）（p1=2C/N（N-1）），p2表示每個約束的松緊度（Tightness）（p2=1-T/DD）。選用以下4個隨機問題作為預處理過程中弧相容算法的例子。

P1：〈150， 50， 500 /0.045， 1250 /0.5〉 P2：〈150， 50， 500 /0.045， 2350 /0.06〉

P3：〈150， 50， 500 /0.045， 2296 /0.082〉 P4： 〈50， 50， 1225 /1.0， 2188 /0.125〉

另外，合法的輸入條件為：N！=0， D！=0， 0

4.2 AC-2001算法改進前后測試對比

AC-2001算法運行時間、檢查次數(shù)改進前后對比如圖1和圖2所示。

結(jié)果分析：AC-2001算法的改進，針對數(shù)據(jù)結(jié)構(gòu)優(yōu)化、啟發(fā)式算法優(yōu)化、二分優(yōu)化、檢查次數(shù)優(yōu)化，運行時間明顯減少，檢查次數(shù)只有少量減少。但由于該算法本身優(yōu)化水平已相當顯著，此結(jié)果在預期范圍之內(nèi)。更為顯著的優(yōu)化結(jié)果，可參照后SAC算法的測試對比。

4.3 SAC算法改進前后測試對比

由于SAC算法在某種程度上依賴于AC-2001算法的實現(xiàn)（可參考基礎知識和其他相關資料介紹），故對AC-2001算法的改進在SAC算法中體現(xiàn)得更為明顯?？梢哉f對SAC算法的改進與優(yōu)化是最為成功的。

SAC算法運行時間、檢查次數(shù)改進前后對比如圖3和圖4所示。

結(jié)果分析：可見，本系統(tǒng)最為成功之處便在于對SAC算法的優(yōu)化。實際上是對AC-2001算法的優(yōu)化影響到了SAC算法。由于SAC算法對AC-2001算法的部分依賴性，導致對AC-2001算法的優(yōu)化性能在此處得到放大。通過AC-2001算法的數(shù)據(jù)結(jié)構(gòu)隊列優(yōu)化、啟發(fā)式算法優(yōu)化、二分優(yōu)化、檢查次數(shù)優(yōu)化，以及對SAC算法自身的數(shù)據(jù)結(jié)構(gòu)優(yōu)化，使SAC算法本身的運行時間大大減少。而圖表顯示的結(jié)果反映了SAC算法不同于其他算法的一個更為明顯的優(yōu)化之處：修改后SAC算法的檢查次數(shù)大致為修改前的1/10—1/3，最低甚至僅為修改前的1/20不到，平均情況下大約為修改前1/5！這是對當前已經(jīng)較為完善的約束滿足問題的AC系列算法改進的十分令人滿意的結(jié)果！

5 結(jié)論（Conclusion）

本文圍繞著以約束滿足問題中弧相容、Singleton弧相容為代表的相容性技術(shù)和求解算法展開，研究各個相容性算法，并主要針對AC-2001算法、SAC算法等進行優(yōu)化改進，重點基于啟發(fā)式進行改進，使之獲得了更快的篩選速度，運行時間大幅減少。尤其對SAC算法大大減少了約束檢查次數(shù)，修改后SAC算法的檢查次數(shù)大致為修改前的1/10—1/3，最低甚至僅為修改前的1/20不到，平均情況下大約為修改前1/5。另外，AC系列算法的效率都得到了大大的提高，獲得了較為成功的基于啟發(fā)式的改進結(jié)果。

多年來，眾多專家和學者一直致力于提高相容性技術(shù)對于約束滿足問題的求解效率，他們研究的重心大多是不斷地提出局部相容性逐漸增強的技術(shù)。未來，隨著計算機硬件的快速發(fā)展，多核并行是個相當可觀的發(fā)展趨勢，實現(xiàn)各種已有的相容性算法的并行算法對求解約束滿足問題有很好的效率，這是個值得研究的新思路。

參考文獻（References）

[1] Freuder E C，Mackworth A K.Constraint satisfaction：Anemerging paradigm[J].Foundations of Artificial Intelligence，2006（2）：13-27.

[2] Bessiere C.Constraint propagation[J].Foundations of Artificial Intelligence，2006（2）：29-83.

[3] Kask K，Dechter R，Gogate V.Counting-based look-ahead schemes for constraint satisfaction[J].Principles and Practice of Constraint Programming CP 2004，2004：317-331.

[4] 朱興軍.約束求解的推理技術(shù)研究[D].吉林大學，2009.

[5] Boussemart F，Hemery F，Lecoutre C，et al.Boosting systematic search by weighting constraints[C].Proceedings of the 16th European Conference on Artificial Intelligence.IOS Press，2004：146-150.

[6] Van Hentenryck P，Van Hentenryck P.Constraint satisfaction in logic programming[M].Cambridge：MIT press，1989.

[7] Lecoutre C，Sas L，Tabary S，et al.Reasoning from last conflict（s）in constraint programming[J].Artificial Intelligence，2009，173（18）：1592-1614.

[8] Grimes D，Wallace R J.Learning from failure in constraint satisfaction search[C].Learning for Search：Papers from the 2006 AAAI Workshop，2006：24-31.

[9] Tsang E.Foundations of constraint satisfaction[J].London： Academic，1993.

[10] 郭勁松.約束滿足問題（CSP）的求解技術(shù)研究[D].吉林大學， 2013.

[11] 徐均哲，孫吉貴，張永剛.弧相容算法性能比較[J].吉林大學學報：信息科學版，2007，25（2）：177-182.

[12] Debruyne R，Bessiere C.From restricted path consistency to max-restricted path consistency[J].Principles and Practice of Constraint Programming-CP97，1997：312-326.

[13] 劉春暉.基于約束傳播的約束求解方法研究[D].長春：吉林大學，2008.

作者簡介：

蔣李鳴（1997-），男，本科生.研究領域：計算機算法理論.

呂佳宇（1996-），男，本科生.研究領域：計算機算法理論.

何哲華（1998-），女，本科生.研究領域：計算機算法理論.

馮澤斌（1996-），男，本科生.研究領域：計算機算法理論.