基于啟發式的約束滿足問題AC系列算法改進研究

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

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

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

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

本文圍繞以弧相容、Singleton弧相容[6]為代表的相容性技術和求解算法展開，研究各個相容性算法。弧相容算法具有相對較少的檢查次數，但其運行時間還可以進一步降低。而Singleton弧相容的SAC[1]算法，運行時間較長，并且檢查次數較多，尤其在檢查次數方面有很大的改進空間。

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

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

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

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

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

定義2.3（廣義弧相容，（G）AC[11]給定一個約束網絡N=（X，D，C），一個約束cC和一個參數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）網絡N是（廣義）弧相容的iff D對C中所有約束上的X中的所有參數是（廣義）弧相容的。

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

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

3 幾種AC系列經典算法的改進（Improvement of AC Algorithms）

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

3.1 數據結構隊列優化原理

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

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

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

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

這個數據結構的優化可以運用于所有AC系列算法中。

3.2 針對AC_2001：：revise2001算法的啟發式算法改進

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

AC-2001僅在 Revise函數和初始化階段不同于AC-3算法。初始化階段，AC-2001將Last[xi，vi，xj]初始化為某個比minD（xj）更小的虛擬值。在Revise2001中（算法3.4），當D（xj）中一個值vj發現支持cij上的（xi，vi）時，AC-2001把vj指派給Last[xi，vi，xj]（第4行）。下次（xi，cij）將被修改，僅當Last[xi，vi，xj]不在D（xj）中時為（xi，vi）尋找支持（第2行）。更重要的是，最優性達到了因為D（xj）中小于Last[xi，vi，xj]的值不再檢查，它們以前已經在被調用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數據結構記錄下標，下次遍歷不再檢查無用信息，而是“智能”地選擇合適的位置開始搜索，是一種啟發式算法的思想。

3.3 檢查次數優化原理

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

3.4 二分啟發式優化原理

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

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

3.5 時空復雜性分析

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

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

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

4 實驗及結果分析（Experiment and Result Analysis）

4.1 實驗測試說明

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

對于隨機生成的數據的輸入：， 其中N表示變量的個數， D表示所有變量論域中的最大值，C表示約束個數，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算法運行時間、檢查次數改進前后對比如圖1和圖2所示。

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

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

由于SAC算法在某種程度上依賴于AC-2001算法的實現（可參考基礎知識和其他相關資料介紹），故對AC-2001算法的改進在SAC算法中體現得更為明顯。可以說對SAC算法的改進與優化是最為成功的。

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

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

5 結論（Conclusion）

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

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

參考文獻（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] 朱興軍.約束求解的推理技術研究[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）的求解技術研究[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-），男，本科生.研究領域：計算機算法理論.