結(jié)合look-ahead值排序的自適應(yīng)分支求解算法

王海燕，歐陽丹彤，張永剛，張良

（1.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；2.吉林大學(xué) 符號計算與知識工程教育部重點實驗室，吉林 長春 130012；3.吉林師范大學(xué) 計算機學(xué)院，吉林 四平 136000）

1 引言

約束滿足問題(CSP, constraint satisfaction problems)是人工智能領(lǐng)域研究的熱點問題。而 CSP的經(jīng)典求解方法是將回溯搜索與約束傳播相結(jié)合。搜索過程是基于某種分支策略，并由變量和值排序啟發(fā)式引導(dǎo)。當(dāng)前，在CSP的回溯搜索中，搜索的分支選擇有多種策略，其中2-way和d-way[1]是2種最標準的分支策略。在2-way分支策略下，在選擇了變量x和x域中的某個值ai后，建立2個分支，一個分支是將x=ai加入到問題中進行傳播，另一個分支是將x<>ai加入到問題中進行傳播。在2個分支都失敗時，算法回溯。在傳播x<>ai時，可以選擇不同于x的變量y的某個值繼續(xù)傳播，也可以選擇變量x的不同于ai的其他值進行傳播。如果將問題限定為后一種情況，則稱其為受限的 2-way分支[2]。而在d-way分支策略下，變量x被選擇之后，建立d（d>2）個分支，每個分支對應(yīng)x的一個值分配。在第一個分支中，x分配值a1，并引發(fā)約束傳播，如果這個分支失敗了，則從x論域中移去a1，然后給x分配a2，以此類推，即，在x=ai失敗后，算法必須選擇x的下一個可用值。如果d個分支都失敗，算法回溯。受限的2-way在某種程度上近似于d-way分支。

Kostas通過實驗證實[2]，不同的變量排序啟發(fā)式對2-way分支策略和d-way分支策略的影響是不同的。當(dāng)從簡單的變量排序啟發(fā)式dom[3]一直測試到更經(jīng)典的啟發(fā)式如dom/ddeg[4]時，2-way分支策略要優(yōu)于d-way分支策略。但采用當(dāng)前公認最好的dom/wdeg[4]變量排序啟發(fā)式時，d-way分支卻比2-way分支更有效。而且實驗結(jié)果表明，受限的2-way分支策略與d-way分支策略效果很接近。基于不同分支策略的不同表現(xiàn)，Kostas提出2個啟發(fā)式，在搜索中的某些點應(yīng)用它們，根據(jù)啟發(fā)式的決定在完全的2-way分支和受限的2-way之間進行選擇。從根本上實現(xiàn)自適應(yīng)分支選擇。

本文首先在dom/wdeg變量啟發(fā)式下，對受限的2-way分支和完全的2-way分支策略進行了詳細的對比實驗。結(jié)果表明，在不同實例上，受限的2-way和完全2-way表現(xiàn)出不同的性能。然后，將4種自適應(yīng)分支方法與上面2種分支方法在標準測試庫 Benchmark中的 composed、bqwh、domino、graph進行了求解效率的對比，實驗結(jié)果充分展示了自適應(yīng)分支策略的優(yōu)勢。同時，由于相關(guān)研究中沒有充分考慮值啟發(fā)式對自適應(yīng)分支策略的影響，而 look-ahead[5]值啟發(fā)式能夠有效引導(dǎo)搜索到更可能成功的分支。為進一步提高算法效率，將自適應(yīng)分支策略與look-ahead兩者結(jié)合起來，提出一種新算法AdaptBranchLVO，該算法在自適應(yīng)分支的基礎(chǔ)上加入look-ahead值啟發(fā)式，在有效避免誤用不合適分支策略的基礎(chǔ)上，考慮到每個值對未來情況的影響，選擇最有可能成為解一部分的值優(yōu)先實例化，以更快求出最終解。在sat和unsat兩大類問題的多個標準類實例上進行實驗，結(jié)果表明，新提出算法在效率上明顯優(yōu)于已有的自適應(yīng)分支方法，即加入look-ahead值啟發(fā)式的自適應(yīng)分支求解效率有更大幅度的提高。

2 背景知識

一個CSP表示為一個三元組（X,D,C），其中，X={x1,…,xn}，是一組n個變量的集合；D={D(x1) ,…,D(xn)}是對應(yīng)于每個變量的一組論域；C={c1,…,ce}是e個約束的集合。每個約束c表示為有序?qū)Γ╲ar(c),rel(c)），其中，var(c)={x1,…,xk}是X的一個有序子集，而 rel(c)是D(x1)×…×D(xk)的子集[7]。驗證一個元組是否滿足約束c的過程稱為一次約束檢查。

回溯搜索與約束傳播的結(jié)合方法是求解 CSP的經(jīng)典方法。搜索過程是基于某種分支策略，并由變量和值排序啟發(fā)式引導(dǎo)。

在經(jīng)典的變量排序啟發(fā)式（VOH, variable ordering heuristic）中，dom/wdeg以其普適性及高效性受到研究者的廣泛重視。它是基于fail-first原則，為每個約束分配一個權(quán)值，初始設(shè)置為 1。每次約束引發(fā)一個沖突（例如一次 DWO），它的權(quán)值就加 1。每個變量都與一個加權(quán)度相關(guān)，它是包含此變量和至少一個未實例化變量的所有約束的權(quán)的總和。Dom是現(xiàn)有論域的大小，dom/wdeg啟發(fā)式選擇現(xiàn)有域大小與帶權(quán)的度比值最小的變量。在后文中，都默認使用dom/wdeg變量排序啟發(fā)式。

值實例化的順序?qū)s束求解效率有著深刻的影響。而搜索中向前看（look-ahead）是提高求解效率的關(guān)鍵技術(shù)，它能在搜索中盡早導(dǎo)致失敗節(jié)點產(chǎn)生，從而為變量排序提供有價值信息。當(dāng)前，look-ahead技術(shù)已成功用于值排序啟發(fā)式，特別是針對難解CSP。典型look-ahead值排序(LVO, lookahead value ordering)啟發(fā)式[5]有：最小沖突(MC,min-conflicts)啟發(fā)式，最大論域(MD, max-domainsize)啟發(fā)式，加權(quán)最大論域(WMD, weighted-maxdomain-size)啟發(fā)式和論域大小分值(PDS, point-domain-size)啟發(fā)式等4種。其中，MC是針對當(dāng)前變量論域中每個值，考慮與當(dāng)前變量相關(guān)的未實例化變量的論域中與這個值不相容值的個數(shù)，并按此個數(shù)的升序?qū)Ξ?dāng)前變量的值排序。即總是優(yōu)先選擇沖突值最少的值；MD是針對當(dāng)前變量論域中每個值，考慮所有與當(dāng)前變量相關(guān)的未實例化變量移去不相容值的剩余子論域，優(yōu)先選擇在未實例化變量中產(chǎn)生最大的最小剩余子論域的值；WMD是MD的一個改進版本，目的是解決第3種啟發(fā)式中，當(dāng)前變量論域中可能有幾個值產(chǎn)生相同大小的剩余子域集合而導(dǎo)致“結(jié)”的產(chǎn)生的問題。WMD優(yōu)先選擇剩下更大子論域的值，這點和MD相似，只是打破“結(jié)”的方法不同。它是根據(jù)具有給定剩余子論域大小的未實例化變量的數(shù)目來打破“結(jié)”的；PDS給當(dāng)前變量論域中每個值打分。依據(jù)是所有與當(dāng)前變量相關(guān)的未實例化變量移去不相容值的剩余子論域。每個大小為1的子論域給8分，每個大小為2的子論域給4分，每個大小為3的子論域給2 分，每個大小為4的子論域給1分。優(yōu)先選擇具有最小總分的值。已有實驗表明[5]，MC啟發(fā)式是LVO啟發(fā)式中效果最好的，所以選擇它進一步實驗。后文中提到的LVO均指MC。

3 分支策略性能對比

2-way和d-way[1]這2種標準的分支策略在不同實例上的表現(xiàn)不同。時而2-way分支策略勝出，時而受限的2-way分支策略勝出，時而兩者持平。研究者考慮在搜索的不同位置選擇更合適的分支策略，即自適應(yīng)分支策略。實現(xiàn)的基本思想是根據(jù)具體問題的結(jié)構(gòu)將不同分支組合到一起，借助于啟發(fā)式和傳播函數(shù)，達到壓縮搜索空間的目的，進而提高求解效率。代表工作為2010年Kostas提出的自適應(yīng)分支策略[2]，其中提到2種啟發(fā)式策略：Hsdiff(e)和Hcadv(VOH2)。前者是基于變量排序啟發(fā)式分值差異的自適應(yīng)分支啟發(fā)式，其工作原理是：假如當(dāng)前變量是x，且VOH建議去選擇一個其他變量y，當(dāng)|score(y)-score(x)|>e時，接受這個建議。其中，score(x)和score(y)是VOH分配給變量x和y的值，而e是一個可變的閾值參數(shù)。后者為輔助顧問啟發(fā)式中，其主要思想為：假如當(dāng)前變量是x，且算法用到的VOH（VOH1）建議去選擇另一個變量y，僅當(dāng)輔助VOH（VOH2）也選擇y時，接受這個建議，即當(dāng)scoreVOH2(y)>scoreVOH2(x)時，其中，scoreVOH2(x)和scoreVOH2(y)是VOH2[8]分配給變量x和y的值。受文獻[2]中實驗結(jié)果啟發(fā)，在Hsdiff(e)中，VOH采用dom/wdeg，e取值0.1；Hcadv(VOH2)中輔助啟發(fā)式為wdeg。2個啟發(fā)式可合取或析取應(yīng)用。

本文在文獻[2]基礎(chǔ)上進行實驗，選取不同的Benchmark測試問題類，以進一步驗證自適應(yīng)分支策略的優(yōu)勢。在實驗中將Hsdiff(0.1)和Hcadv(wdeg)簡記為H1和H2，它們的合取和析取記為H12∧和CPU運行時間實驗結(jié)果如表1所示。表中每個實例 CPU運行時間的最好情況都用黑體顯示。從表中可以看出，自適應(yīng)分支策略總是趨于選擇效果好的分支方式，有些情況甚至比兩者中的優(yōu)勝者更好。

4 AdaptBranchLVO算法

為進一步提高約束求解效率，本文在自適應(yīng)分支的基礎(chǔ)上加入look-ahead值啟發(fā)式。考慮到求解難解CSP時，多數(shù)時間花費在探查搜索空間不可能產(chǎn)生問題解的分支上。為減少回溯，應(yīng)首先嘗試那些更可能導(dǎo)致相容解的值。即使被選擇的值是某個解的一部分可能性的微小增大都能對找到解的時間開銷有著本質(zhì)上的影響。本文利用在自適應(yīng)約束傳播look-ahead階段中收集到的信息改進值排序啟發(fā)式。在自適應(yīng)分支框架上，加入文獻[5]中的LVO啟發(fā)式，它根據(jù)look-ahead得到的信息為當(dāng)前論域中的值劃分等級。當(dāng)前變量則用最高級別的值實例化。得到的算法是AdaptBranchLVO，其維持弧相容的框架描述如圖1所示。

由于需要區(qū)分完全的 2-way策略和受限的2-way策略，而這2種策略的區(qū)別僅在于下一個實例化的變量改變與否。所以用布爾變量Restricted_or_Not（第2行）作為是否需要判斷限定分支的標識變量，其值為真，表示下一次需要判斷是否限定分支，反之不需要。Free_variables（第4行）是未實例化的變量。Soulution_Stack（第 5行）為存儲解的動態(tài)堆棧。AdaptBranchLVO算法的 MAC過程為，只要還有未實例化的變量，就根據(jù) SELECT_VAR函數(shù)（下面詳述）選擇出一個變量（第7行），并按LVO為其選擇一個值（第9行）。自適應(yīng)分支的具體實現(xiàn)在SELECT_VAR函數(shù)中，總體上實現(xiàn)了自適應(yīng)分支和LVO結(jié)合的方式。

表1 自適應(yīng)分支策略與標準分支策略的比較（單位：ms）

圖1 MAC框架描述

SELECT_VAR函數(shù)在整個MAC的過程中尤為重要（如圖2所示）。在選擇變量的時候，主要考慮的是Restricted_or_Not的值。在其值為真的前提下，需要判定是否限定分支，判定的依據(jù)是H1和H22種自適應(yīng)分支啟發(fā)式的滿足情況，并根據(jù)判定結(jié)果選擇合適的變量作為下一個實例化對象。Switch的4個分支（第17）～25)行）對應(yīng)著4種啟發(fā)式運用的方式。如果使用 dom/wdeg啟發(fā)式篩選出變量恰為當(dāng)前變量cur_var，則不執(zhí)行啟發(fā)式H1、H2。

圖2 選擇變量過程

5 實驗結(jié)果

為驗證AdaptBranchLVO算法優(yōu)勢，本文利用標準測試庫Benchmark中的多類問題實例對算法進行測試。實驗是在AMD Athlon(tm) 64 X2雙核處理器3600的DELL計算機上完成的，主頻為1.90 GHz，內(nèi)存為1.00 GB，操作系統(tǒng)為Microsoft Windows XP Professional。測試環(huán)境為 Microsoft Visual Studio 2008。將AdaptBranchLVO和已有自適應(yīng)分支算法進行比較，考查 CPU運行時間、約束檢查次數(shù)和搜索樹生成節(jié)點數(shù)3項技術(shù)指標。CPU時間（單位：ms）記為cpu，約束檢查次數(shù)記為#ccks，搜索樹生成節(jié)點數(shù)記為#nodes。將AdaptBranchLVO算法應(yīng)用于搜索中，得到與原自適應(yīng)分支算法的實驗對比結(jié)果，如表2所示，最好的情況均用黑體標記。實驗結(jié)果表明：新提出算法在時間開銷、約束檢查次數(shù)及搜索樹生成節(jié)點數(shù)方面均明顯優(yōu)于已有自適應(yīng)分支算法。

為檢驗新提出算法的高效性及普適性，本文在可滿足問題（簡記為sat）和不可滿足問題（簡記為unsat）兩大類問題上進行實驗，共選取composed、bqwh、driver、frb、rlfap、geom、ehi、QCP 等 8 類問題，并從每個分類中選出5～10個實例進行測試，取時間測試結(jié)果的平均值作為此分類實例的實驗數(shù)據(jù)。

在sat類中，選出部分測試結(jié)果如表3所示。很清楚看出，加入 LVO的自適應(yīng)分支策略在平均時間上明顯優(yōu)于未加入的情況，尤其在 composed-25-10-20和geom兩類問題上，總體效率提高了2倍左右。有些更是提高了3倍左右，如frb30-15在H1上的改進。總之，AdaptBranchLVO綜合性能明顯優(yōu)于已有自適應(yīng)分支算法。

在unsat問題類上，本文給出composed-25-1-2、ehi-85、QCP-10和rlfapModScens 4類子問題的測試結(jié)果如表 4所示。可以看出，在不可滿足問題類上，加入LVO的自適應(yīng)分支求解效率整體上也優(yōu)于已有自適應(yīng)分支算法。需要指出的是，對于rlfapModScens問題實例，加入LVO策略的基于H2和H12?自適應(yīng)分支求解算法在平均性能上比已有自適應(yīng)分支約束算法差，考慮這和rlfapModScens問題實例的特殊結(jié)構(gòu)有關(guān)，未來工作將深入探討和問題結(jié)構(gòu)密切相關(guān)的自適應(yīng)約束求解算法。

表2 AdaptBranchLVO與已有自適應(yīng)分支算法對比結(jié)果

表3 sat類上平均求解時間對比（單位：ms）

表4 unsat類上平均求解時間對比（單位：ms）

6 結(jié)束語

不同分支策略在不同實例上有不同效率表現(xiàn)。自適應(yīng)分支策略以選擇最合適分支為最終目標，是自適應(yīng)約束求解方法的重要研究方向。分支策略性能對比實驗充分證明：引入自適應(yīng)分支可以有效提高約束求解效率。本文基于新近提出的自適應(yīng)分支約束求解框架，結(jié)合look-ahead值啟發(fā)式，提出一種新的約束求解算法AdaptBranchLVO。并針對標準測試庫Benchmark中的典型sat和unsat問題進行比較實驗。實驗結(jié)果表明，加入look-ahead值啟發(fā)式的自適應(yīng)分支約束求解方法能更有效地提高約束求解的效率。未來工作考慮將學(xué)習(xí)型值啟發(fā)式嵌入到自適應(yīng)分支框架中，以進一步提高約束求解效率。

[1] BALAFOUTIS T, PAPARRIZOU A, STERGIOU K.Experimental evaluation of branching schemes for the CSP[A].CoRR[C].2010.

[2] BALAFOUTIS T, STERGIOU S.Adaptive branching for constraint satisfaction problems[A].Proceedings of ECAI[C].Lisbon, Portugal,2010.855-860.

[3] HARALICK R M, ELLIOTT G L.Increasing tree search efficiency for constraint satisfaction problems[J].Artificial Intelligence, 1980,14(3)： 263-313.

[4] BOUSSEMART F, HEREMY F, LECOUTRE C,et al.Boosting systematic search by weighting constraints[A].Proceedings of ECAI[C].Valencia, Spain, 2004.482-486.

[5] DANIEL FROST, RINA DECHTER.look-ahead value ordering for constraint satisfaction problems[A].Proceedings of IJCAI [C].Montréal, Québec, Canada, 1995.572-578.

[6] LIKITVIVATANAVONG C, ZHANG Y L, BOWEN J,et al.Arc consistency during search[A].Proceedings of IJCAI[C].Hyderabad,India, 2007.137-142.

[7] STAMATATOS E, STERGIOU K.Learning how to propagate using random probing[A].Proceedings of CPAIOR[C].Pittsburgh, USA,2009.263-278.

[8] GRIMES D, WALLACE R J.Sampling strategies and variable selection in weighted degree heuristics[A].Proceedings of CP[C].Providence, USA, 2007.831-838.