王瑞偉　李占山　李宏博

1(符號計算與知識工程教育部重點實驗室(吉林大學(xué))　長春　130012)2(吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院　長春　130012)3　　　(吉林大學(xué)軟件學(xué)院　長春　130012)

?

求解約束可滿足問題的eSTR算法優(yōu)化

王瑞偉1,3李占山1,2,3李宏博1,2

1(符號計算與知識工程教育部重點實驗室(吉林大學(xué))長春130012)2(吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院長春130012)3(吉林大學(xué)軟件學(xué)院長春130012)

(120801104@qq.com)

摘要表約束方法是1種外延式知識表示方法，每個約束通過元組集直接枚舉出其在1個變量集上允許或禁止的所有元組，直觀易于理解，在約束程序中得到了深入的研究，這是因為表約束出現(xiàn)在如設(shè)計、數(shù)據(jù)庫、配置以及偏好建模等許多現(xiàn)實世界的應(yīng)用中.但隨著約束的增多及其元組集增大，占有的空間與相容性檢測效率成了關(guān)鍵問題.eSTR是1個將STR擴展到高階相容的算法，通過深入分析eSTR算法后發(fā)現(xiàn)有2種優(yōu)化方式:PWsup數(shù)據(jù)結(jié)構(gòu)和極小約束范圍，同時證明了在極小約束范圍上，約束網(wǎng)絡(luò)仍然能夠維持PWC+GAC，其中極小約束范圍可以通過刪除約束元組集中相應(yīng)的列來降低eSTR2算法的空間消耗，而PWsup數(shù)據(jù)結(jié)構(gòu)能夠通過避免不必要的PW支持檢測來減少eSTR2的CPU運行時間，實驗結(jié)果表明：2種優(yōu)化方式和eSTR2相結(jié)合后能夠同時減少算法的空間消耗和CPU運行時間，在許多類實例上明顯優(yōu)于eSTR2和eSTR2w.

關(guān)鍵詞高階相容；極小約束范圍；約束網(wǎng)絡(luò)；PWsup數(shù)據(jù)結(jié)構(gòu)；PWC+GAC

作為人工智能一個主要研究分支的約束程序(constraint programming， CP) 興起于20世紀80年代末期，1996年美國計算機學(xué)會(Association for Computing Machinery, ACM) 在慶祝其成立50周年的大會上，將CP確立為21世紀計算機科學(xué)最有前途的戰(zhàn)略研究方向之一.正如其所預(yù)言的那樣，進入21世紀后，CP的理論研究與應(yīng)用出現(xiàn)了1個高潮：近年來召開的IJCAI,AAAI,ECAI等頂級國際會議都把相關(guān)問題研究作為會議的1個重要議題.最近幾年在設(shè)計、數(shù)據(jù)庫、配置和偏好建模等領(lǐng)域有著重要應(yīng)用的表約束求解方法受到了大量學(xué)者的關(guān)注.表約束方法是1種外延式知識表示方法，每個約束通過元組集直接枚舉出其在1個變量集上允許或禁止的所有元組，非常地直觀，但隨著約束的增多及其元組集增大占有的空間與相容性檢測效率成了關(guān)鍵問題.為此許多學(xué)者對此開展了大量研究工作.在表壓縮方面，如在表約束上維持GAC的高效算法有STR2[1],MDDC[2].其中2011年法國學(xué)者Lecoutre[1]提出的STR2是動態(tài)維持允許元組集算法STR的更精化版本，被認為是在多元正表約束上最有效的GAC(generalized arc-consistency)算法；2010年Cheng和Yap[2]提出的基于多元決策圖的MDDC方法是二元決策圖方法的1種推廣，適合于正表與負表約束二種知識表示的壓縮，尤其當元組集中各個元組之間具有許多交疊部分時MDDC要優(yōu)于STR2；2013年Xia和Yap[3]提出的STR2-C將STR2的思想與笛卡兒積壓縮表[4]相結(jié)合，在壓縮率較高的問題上STR2-C時間和空間效率都要優(yōu)于STR2；Jefferson和Nightingale[5]提出的SHORT-STR2利用元組集上的一些特性將一些元組轉(zhuǎn)化為短約束元組來減少元組集的行數(shù)(元組個數(shù))，從而提高STR2的算法時間和空間效率；國內(nèi)研究者李宏博等人[6]在2013年提出了STR-N，將STR算法擴展到負表約束.其他一些國內(nèi)學(xué)者主要研究的是約束滿足問題Benchmark模型生成或二元約束求解問題，如北京航空航天大學(xué)許可等人[7-8]提出了生成隨機約束可滿足問題benchmark實例的模型方法被廣泛應(yīng)用于benchmark實驗測試中；李宏博等人[9]研究了二元約束上的粗粒度弧相容算法的優(yōu)化問題，指出對于指向已賦值變量的弧存在無效的修正檢查并證明了這類修正檢查是冗余的，提出了1種方法來避免這類冗余的修正檢查方法；李占山等人[10]提出了用于回溯搜索的新啟發(fā)式；中國科學(xué)院軟件研究所張健等人[11-12]研究了約束滿足問題與組合優(yōu)化的關(guān)系問題和拉丁方問題，在文獻[11]中張健等人提出了將混合約束問題轉(zhuǎn)化為混合整數(shù)規(guī)劃問題的方法，用約束求解方法及混合整數(shù)規(guī)劃方法共同求解混合約束問題；在文獻[12]中張健等人描述了雙自成正交拉丁方的搜索方法，目前國內(nèi)研究表約束方法的人還較少.

另外1個受關(guān)注的表約束問題是維持高階相容性，高階相容性主要是通過求解特定的子問題來化簡整個問題的變量域或約束元組集，目前人們已經(jīng)提出了許多不同的高階相容性方法，如1989年Janssen等人[13]提出的PWC(pair-wise consistency)構(gòu)建的子問題是約束元組集中元組能否擴展到所有相鄰約束，同時還給出1種刪多余邊的方式來減少相鄰約束數(shù)量即化簡所構(gòu)建的子問題；maxRPWC是Bessiere等人[14]在2008年提出的高階域過濾相容性，主要是確保變量值在包含該變量的約束元組集中存在1個能擴展到所有相鄰約束的GAC支持，在稀疏問題或較大定義域問題上maxRPWC優(yōu)于GAC；Paparrizou等人[15]在2012年給出在表約束上維持maxRPWC的高效算法同時提出了maxRPWC+，maxRPWC+忽略掉那些因為元組失去PW(pair-wise)支持帶來的約束傳播，在他們所測的大多數(shù)問題上maxRPWC+要優(yōu)于maxRPWC；2010年Karakashian等人[16]提出維持R(*m)C的高效算法，R(*m)C將約束元組集中不能同時擴展到其他任意m-1個約束上的元組刪掉，在困難問題上R(*m)C優(yōu)于GAC；eSTR是2013年Lecoutre等人[17]提出的在表約束上維持PWC+GAC的高效算法，PWC所構(gòu)造的子問題是元組能否擴展到所有相鄰約束上，eSTR利用計數(shù)器來實時記錄元組在各個相鄰約束上的支持個數(shù)，從而能夠在常量時間內(nèi)判斷是否存在PW支持，它大幅度降低了搜索子問題解帶來的時間消耗，在許多類問題上能夠比maxRPWC+和STR2算法更有效率.但在高階相容性算法中很難像STR2-C和SHORT-STR2一樣通過壓縮元組集的行數(shù)(元組數(shù))來降低算法的時間和空間消耗，因為目前大多數(shù)高階相容性構(gòu)造的子問題會考慮到單個元組的特性，將多個元組壓成1行后，在求解子問題時還得分開考慮，很難一起處理多個元組，為此本文提出1種壓縮元組集列數(shù)的方式來降低eSTR算法的時間和空間消耗，另外在eSTR算法檢測PW支持時，進行了許多冗余的檢測，相應(yīng)的本文給出1種忽略冗余檢測的優(yōu)化方式來提高eSTR算法的時間效率.本文闡述的主要工作有2點：

1) 在檢測約束中元組是否在相鄰約束上有PW支持時，并不檢測所有的相鄰約束而只檢測可能使當前約束中元組失去PW支持的相鄰約束，本文采用PWsup數(shù)據(jù)結(jié)構(gòu)來記錄需要檢測的相鄰約束，減少約束檢查次數(shù)提高eSTR算法的時間效率.

2) 在維持PWC后，一些約束的約束范圍中存在多余變量，本文刪掉約束范圍中的多余變量得到極小約束范圍來降低eSTR算法的時間消耗，同時在刪完多余變量及初始化ctr計數(shù)器后可以直接刪掉對應(yīng)元組集中的列來降低eSTR算法的空間消耗.

1背景知識

約束可滿足問題定義為1個三元組(X，D，C)，其中X={x1,x2,…,xn}是1個由n個變量組成的集合，D={D(x1),D(x2),…,D(xn)}是有限域的集合，每個變量對應(yīng)1個域;C={c1,c2,…,ce}是e個約束組成的集合，其中每個約束都和變量子集scp(c)相對應(yīng)，稱scp(c)為約束范圍，同時每個表約束還有1個相對應(yīng)的元組集rel(c).

人們經(jīng)常使用的局部相容性是廣義弧相容(GAC)，1個變量值(x,a)是GAC的,當且僅當?c∈C且x∈scp(c),?τ∈rel(c),使得τ(x)=a且τ是有效的，則稱τ是a在c上的支持.1個變量x是GAC，當且僅當?a∈D(x),(x,a)是GAC的，1個約束可滿足問題是GAC的，當且僅當?x∈X是GAC的.

GAC是域相容，它通過刪除不相容的變量值來維持相容性，而關(guān)系相容是通過刪除不相容的元組來達到相容，PWC是關(guān)系相容，它確定了元組需要滿足的性質(zhì).1個元組(c,τ)是PWC的，當且僅當τ在所有和c相鄰的約束上有PW支持.1個約束c是PWC的，當且僅當?τ∈rel(c)是PWC的，1個約束可滿足問題是PWC的，當且僅當?c∈C是PWC的.元組τ在相鄰約束上存在PW支持是指在相鄰約束上存在和τ相交部分相等的元組.本文只考慮約束范圍交集中變量數(shù)大于1的相鄰約束，因為約束網(wǎng)絡(luò)維持GAC后在交集變量數(shù)為1的相鄰約束上一定有PW支持.

eSTR算法中最主要的數(shù)據(jù)結(jié)構(gòu)是ctr[c][c′][k]計數(shù)器，其用于記錄約束c的元組集在c和c′的約束范圍交集中變量上投影得到的集合中第k個元素在約束c當前元組集上的支持個數(shù)，若ctr[c][c′][k]=0則說明投影得到的集合中第k個元素在約束c的當前元組集中不存在支持,這說明在約束c′中存在ctr[c′][c][ctrlink[c][c′][k]]個元組在約束c上失去PW支持[17].

2PWsup數(shù)據(jù)結(jié)構(gòu)

STR2能夠有效地減少元組中變量值的有效性檢測，因為它只檢測可能變?yōu)闊o效的變量值，相應(yīng)地檢測元組的PW支持也可以只檢測那些可能會失去PW支持的相鄰約束.為此，我們引入1個新的數(shù)據(jù)結(jié)構(gòu)PWsup，PWsup[c]用于記錄約束c中元組在哪些相鄰約束上可能會失去PW支持.

算法1只檢測約束c中元組在PWsup[c]中約束上是否存在PW支持，若是在PWsup[c]中的約束上都存在PW支持那么就認為該元組是PWC相容的，因為PWsup[c]中包含了所有c在其上可能失去PW支持的相鄰約束，只要元組τ在PWsup[c]中的約束上存在PW支持，那么τ在c的所有相鄰約束上都存在PW支持.應(yīng)用PWsup[c]數(shù)據(jù)結(jié)構(gòu)最重要的1點是保證PWsup[c]包含所有可能使c在其上失去PW支持的相鄰的約束.

算法1. 檢測PW支持.

isPWconsistent(c,index):Boolean

① begin

② for eachc′∈PWsup[c] do

③j←ctrIndexes[c][c′][index];

④k←ctrlink[c][c′][j];

⑤ ifk=NULL ORctr[c′][c][k]=0 then

⑥ return FALSE;

⑦ end if

⑧ end for

⑨ return TRUE;

⑩ end

本文通過4種方式來維持PWsup[c]數(shù)據(jù)結(jié)構(gòu)：

1) 初始化時PWsup[c]={所有和c相鄰且變量交集大于1的約束}.

2) 刪掉c中所有不相容的元組后將PWsup[c]清空，因為此時c中元組在所有的相鄰約束上必然存在PW支持.

3) 當發(fā)生回溯而恢復(fù)現(xiàn)場時，清空PWsup[c]，因為在進入下1層之前，整個約束網(wǎng)絡(luò)要先維持GAC+PWC，也就是說回復(fù)現(xiàn)場后c中元組在所有相鄰的約束上都存在PW支持，所以清空PWsup[c].

4) 在算法2中更新ctr計數(shù)器時，通過ctr計數(shù)器的值判斷是否會引起相鄰約束中元組在c上失去PW支持，若是相鄰約束c′有元組在c上失去了PW支持，那么相應(yīng)地將c加入PWsup[c′]中，這樣我們就能保證PWsup[c′]包含所有可能使c′在其上失去PW支持且和c′相鄰的約束，具體見算法2.

算法2. 更新ctr計數(shù)器.

updateCtr(c,index)

① begin

② for eachc′≠cand |scp(c′)∩scp(c)|>1 do

③j←ctrIndexes[c][c′][index];

④ctr[c][c′][j]←ctr[c][c′][j]-1;

⑤ ifctr[c][c′][j]=0 then

⑥k←ctrlink[c][c′][j];

⑦ ifk≠NULL ORctr[c′][c][k]>0 then

⑧ addc′ toQ;

⑨PWsup[c′]←PWsup[c′]∪c;

⑩ end if

在算法2中行⑦，當ctr[c′][c][k]>0時將c′加入傳播隊列Q中并將c加入PWsup[c′]中，而在原來的eSTR算法[17]中，當ctr[c][c′][j]=0時就將c′加入Q，這使得算法進行了許多沒有必要的約束傳播，算法2是本文優(yōu)化后的結(jié)果.

維持PWsup[c]數(shù)據(jù)結(jié)構(gòu)后，約束c只需進行O(pt)次PW支持檢測就能夠維持PWC，其中p是PWsup[c]中包含的相鄰約束個數(shù)，回溯算法進入下1層之前約束網(wǎng)絡(luò)總是先維持PWC+GAC，這時PWsup[c]為空，也就是說不用檢測PW支持，若沒有PWsup數(shù)據(jù)結(jié)構(gòu)，我們就得進行O(gt)次PW支持檢測，其中g(shù)是指和c相鄰的約束范圍交集中變量個數(shù)大于1的約束數(shù)量，t是指約束表中的元組數(shù)量.另外維護數(shù)據(jù)結(jié)構(gòu)PWsup的時間消耗是O(gt+p)，O(p)是每次清空數(shù)據(jù)結(jié)構(gòu)的時間消耗，O(gt)是算法2中行⑨所帶來的消耗，幸運的是我們只有滿足條件ctr[c][c′][j]=0和ctr[c′][c][k]>0后才會進行更新而且每次更新的時間消耗都很少，所以通常維持數(shù)據(jù)結(jié)構(gòu)的時間很少，此外PWsup數(shù)據(jù)結(jié)構(gòu)消耗的空間復(fù)雜度是O(e2).

3極小約束范圍及其應(yīng)用示例

dual圖是1個以約束為結(jié)點并在任意2個約束范圍交集不為空的的結(jié)點之間添加邊后得到的圖，dual圖中的2個結(jié)點間的1條邊是多余邊，當且僅當存在1條替代路徑連接這2個結(jié)點且路徑中每個結(jié)點的約束范圍都包含這2個結(jié)點的約束范圍交集中所有變量，刪去多余邊后約束網(wǎng)絡(luò)依然能夠維持PWC[13].本文提出和多余邊相類似的多余變量，將約束范圍中的多余變量刪掉以后，約束網(wǎng)絡(luò)依然能夠維持PWC+GAC.

定義1. 約束網(wǎng)絡(luò)N所對應(yīng)的 2-dual圖是指將N對應(yīng)的dual圖中變量數(shù)小于2的邊去掉得到的圖.

圖1(a)給出了1個約束網(wǎng)絡(luò)，同時圖1(b)是其對應(yīng)的2-dual圖，我們可以發(fā)現(xiàn)其實2-dual圖其實就是以約束為結(jié)點集，在任意2個約束范圍交集中變量數(shù)大于1的約束之間存在1條邊的圖.

Fig. 1　A constraint network and 2-dual graph.圖 1　1個約束網(wǎng)絡(luò)和2-dual圖示例

定義2. 約束網(wǎng)絡(luò)N中任意變量V所對應(yīng)的2V-dual圖是指將N對應(yīng)的2-dual圖中所有不包含變量V的結(jié)點和邊刪掉得到的圖.

圖2中給出了圖1中約束網(wǎng)絡(luò)中變量F對應(yīng)的2F-dual圖，是通過刪掉圖1中所有不包含F(xiàn)的結(jié)點和邊后得到的圖.下面引入1種能夠確保約束網(wǎng)絡(luò)維持PWC+GAC的極小約束范圍S，它是通過將原始約束范圍中一些變量刪掉后得到新的約束范圍.

Fig. 2　A 2F-dual graph.圖 2　1個2F-dual圖示例

定義3. 若新的約束范圍S使得在約束網(wǎng)絡(luò)中的任意變量V所對應(yīng)2V-dual圖的每個連通分量中存在且只存在唯一的約束c使得V∈S[c]，則稱S是約束網(wǎng)絡(luò)的極小約束范圍.

圖1中約束網(wǎng)絡(luò)所對應(yīng)的1個極小約束范圍S：S[c1]={A,B,C,D},S[c2]={F},S[c3]={E},S[c4]={B,F},S[c5]={}.

引理1. 對于任意2個相鄰約束c1和c2，已知c1中元組在c2上都存在PW支持，?V∈scp(c1)∩scp(c2)，若V在c1上是GAC的，那么V在c2上也是GAC的.

證明. 不妨設(shè)(V，a)在c1上的支持為τ1，τ1,在c2上的PW支持為τ2，因為τ2是τ1在c2上PW支持，所以我們可知τ2和τ1在交集變量上的取值是相等的，而又因為V是c1和c2的交集變量，所以τ1和τ2在V上的值是相等的，故可知τ2是(V，a)在c2上的支持.

證畢.

定理1. 約束網(wǎng)絡(luò)在對應(yīng)的2-dual圖上維持PWC后，約束網(wǎng)絡(luò)是GAC的，當且僅當所有約束c的極小約束范圍S[c]中的所有變量在c上維持GAC.

證明.

1) 必要性.因為S[c]?scp(c)，所以當在scp(c)中的變量都在c上維持GAC后，相應(yīng)地在S[c]中的變量也都在c上維持GAC.

2) 充分性.若所有約束c的極小約束范圍S[c]中的所有變量在c上維持GAC而約束網(wǎng)絡(luò)不是GAC，則存在(V，a)在約束c上沒有支持且變量V不屬于S[c]，這時根據(jù)定義3可知，存在1個和c在同一連通分量中的約束c1，使得S[c1]包含V，假設(shè)c1,c2,…,c是從c1到c的路徑，若V在c1上是GAC的，則(V,a)在c1上存在支持τ1.根據(jù)引理1可知，(V,a)在c2中必定存在1個支持τ2，以此類推(V,a)在c上也有支持，于是產(chǎn)生矛盾.

證畢.

證畢.

證畢.

Fig. 3A constraint network and a new constraint scope.
圖31個約束網(wǎng)絡(luò)和新約束范圍

定理1確保約束網(wǎng)絡(luò)在極小約束范圍上維持PWC+GAC等價于初始約束范圍，而定理2和定理3說明極小約束范圍就是最小約束范圍.

算法3用于求約束網(wǎng)絡(luò)的極小約束范圍S，其主要思想是直接默認變量x保留在對應(yīng)2x-dual圖的各個連通分量中第1個被訪問到的約束c的極小約束范圍S[c]中，然后通過算法4深度優(yōu)先搜索確保對應(yīng)2x-dual圖中和c在同一連通分支上的所有其他約束不在極小約束范圍S中保留變量x.算法時間復(fù)雜度為O(|X|U2)，U表示變量中最大的度(包含某個變量的約束數(shù)量)

算法3. 求約束網(wǎng)絡(luò)N的極小約束范圍S.

getS(N)

① begin

② for eachc∈Cdo

③S[c]←?;

④Mark[c]←-1;

⑤M←?x∈X;

⑥ end for

⑦ for eachx∈Mdo

⑧ for eachc∈Candx∈scp(c) do

⑨ ifMark[c]≠xthen

⑩Mark[c]←x;

算法4. 遍歷和約束c同一連通分支的約束.

searchCoCo(Mark,c,x)

① begin

②stack←{c};

③ whilestack≠? do

④cnow←pop(stack);

⑤ for eachc∈Candx∈scp(c′) do

⑥ if|scp(c′)∩scp(cnow)|>1 then

⑦ ifMark[c′]≠xthen

⑧stack←stack∪c′;

⑨Mark[c′]←x;

⑩ end if

例1. 汽車配置問題可以直觀的表示為由表約束組成的約束可滿足問題，表1中給出了1個關(guān)于汽車的簡單配置問題，主要考慮環(huán)保對配置汽車的2個簡單約束:約束1是對不同類型車和發(fā)動機類型及其發(fā)動機排放標準的限制;約束2是限制一些汽車必須裝OBD，約束表中列出所有允許的元組.

Table 1　A Instance of Car Configuration

通過算法3可以得到例1中約束網(wǎng)絡(luò)對應(yīng)的1個極小約束范圍是：S[Constraint 1]={Engine Emission Standard，Engine Type，Vehicle Type}，S[Constraint 2]={Installing OBD}.相應(yīng)在eSTR算法構(gòu)建了ctr計數(shù)器以后，便可以刪去不在極小約束范圍中的列，表2給出了根據(jù)極小約束范圍刪去表1中汽車配置例子的列后得到的結(jié)果.

應(yīng)用極小約束范圍后，在單個約束c上執(zhí)行1次eSTR的時間復(fù)雜度是O(sd+max(s,g)t)，好于初始約束范圍的時間復(fù)雜度O(rd+max(r,g)t)[17]，其中s=|S[c]|，r=|scp(c)|，g是指約束范圍交集中變量數(shù)大于1的相鄰約束數(shù)目，t是當前表中元組數(shù)量.但是每次約束檢測刪去的元組會減少，同時最終維持PWC+GAC要刪去的元組是一致的，于是增加了約束的檢測次數(shù)，總的來說應(yīng)用極小約束范圍可以降低每次約束檢測的時間，但會增加約束檢測的次數(shù)，約束檢測是指對約束執(zhí)行1次eSTR算法.

Table 2　The Result of Deleting Redundant Columns

①http:www.cril.univ-artois.fr～lecoutresoftware.html

②http:www.cril.univ-artois.fr～lecoutrebenchmarks.html

約束網(wǎng)絡(luò)在極小約束范圍上維持GAC時，算法只檢測元組在極小約束范圍中變量值的有效性，同時由于在eSTR算法初始化時建立了ctr計數(shù)器，檢測PW支持時也不會訪問具體元組中的變量值.于是我們可以通過將元組集中那些不會被訪問到的列刪去來降低eSTR算法的空間消耗，若約束c擁有獨立的元組集，那么極小約束范圍S[c]能夠減少Ο((r-s)t)的空間消耗.

4實驗結(jié)果

我們分別在隨機問題和benchmark問題上測試優(yōu)化算法并將其和eSTR2，eSTR2w進行比較，下面采用P和T來分別表示2種不同的優(yōu)化方式，P表示PWsup數(shù)據(jù)結(jié)構(gòu)，T表示極小約束范圍，另外在實現(xiàn)eSTR算法時，本文是先刪去2-dual圖中的多余邊[13]后才建立的ctr計數(shù)器，在本文所測的所有實例上刪多余邊后eSTR算法基本都比沒刪多余邊要快許多，所以本文的eSTR算法都先刪去多余邊.在回溯中采用靜態(tài)變量啟發(fā)式dominitdeg和字母順序的值啟發(fā)式，dominit是變量初始域的大小.大部分實驗是在環(huán)境1中進行，但是由于Renault和aim問題中存在許多非常簡單的實例，在環(huán)境1中的運行時間小于1ms，所以我們在環(huán)境2中測試這2類問題.

實驗環(huán)境1. 4.0GB內(nèi)存、3.40GHz主頻、i7處理器、Windows7操作系統(tǒng)和Java語言.

實驗環(huán)境2. 2.0GB內(nèi)存、2.27GHz主頻、i3處理器、Windows7操作系統(tǒng)和Java語言.

4.1隨機問題測試

我們選擇隨機約束可滿足問題模型ModelRB[8]對算法進行測試，具體實例是通過使用RBGenerator2.0①來產(chǎn)生的，ModelRB問題由5個參數(shù)控制，r,n,d,e,p中的r是指約束的元數(shù)，n是指變量個數(shù)，d是變量值域的大小，e是約束的個數(shù)，p是約束的緊度(tightness).我們選取r=13,n=60,d=2,e=20的問題進行測試，每個緊度測20個實例.圖4展現(xiàn)p在0.8～0.95的實驗結(jié)果，緊度間隔是0.01，我們只給出0.8～0.95的實驗結(jié)果是因為在0.8～0.95之外緊度上13,60,2,20,p問題非常容易.eSTR2+P在13,60,2,20,p問題上的CPU運行時間平均比eSTR2快23%，eSTR2+P+T平均比eSTR2+P快10%、比eSTR2快31%，這說明PWsup數(shù)據(jù)結(jié)構(gòu)和極小約束范圍在這類問題上能夠提高eSTR2算法的時間效率.刪掉dual圖中的多余邊后，eSTR2比eSTR2w具有更好的時間效率，所以相應(yīng)的eSTR2+P+T平均要比eSTR2w快37%.另外從圖4我們可以知道2種優(yōu)化方式在13,60,2,20,p問題不同緊度上能夠穩(wěn)定地減少eSTR2算法的CPU運行時間.

Fig. 4　Experimental results of random instances.圖4　隨機實驗結(jié)果

4.2Benchmark測試

本文所測的大部分實例是從Lecoutre的主頁②上下載的，另外還有3類實例是使用RBGenerator2.0①來產(chǎn)生的，它們分別是rand-12，rand-5，rand-10問題.

Table3ResultsofDeletingVariablesbyMinimalConstraintScopeS

表3　極小約束范圍S刪變量結(jié)果

表4給出了每個算法在不同問題上的平均CPU運行時間，加粗表示是最好的時間，#Instance表示某類問題包含的實例個數(shù)，除了dubois問題外，eSTR2+P+T的CPU平均運行時間一般都比eSTR2要快，其中eSTR2+P+T在mdd-25-7問題上比eSTR2快41%，在rand-8問題上、比eSTR2快37%.刪除了dual圖中的多余邊之后，eSTR2在許多類實例上要比eSTR2w更具有優(yōu)勢；相應(yīng)地除了MDD-23-15和rand-3問題外,eSTR2+P+T算法的CPU平均運行時間要比eSTR2w快；在MDD-25-7問題上；eSTR2+P+T比eSTR2w快2倍；在rand-8問題上，eSTR2+P+T比eSTR2w快43%.表5列出不同實例的CPU運行時間和擴展結(jié)點數(shù)，每類問題選2個不同難易程度的實例，比如renault-mod-0實例只擴展了111個結(jié)點，而renault-mod-30實例擴展了1 449 414個結(jié)點.

Table 4　Mean Running Time of Different Problem

aim問題的元組集很小，只包含了6個或7個元組，這導(dǎo)致了PWsup數(shù)據(jù)結(jié)構(gòu)的優(yōu)化效果不好，因為在元組集很小的時候，算法維持數(shù)據(jù)結(jié)構(gòu)的額外時間開銷所占比例較多;另外aim是三元問題，在低元問題上極小約束范圍在每次約束檢測所減少的時間比較少，因為STR2本身就能夠避免一些變量的有效性檢測，而且在低元問題上單個約束的極小約束范圍能刪去的變量個數(shù)較少，所以在低元問題上極小約束范圍的時間優(yōu)化效果不理想.dubois問題只有2對約束的約束范圍交集中變量個數(shù)大于1同時只刪去了3%的約束變量，所以PWsup數(shù)據(jù)結(jié)構(gòu)和極小約束范圍的時間優(yōu)化效果都不理想.

MDD-23-15問題上PWsup數(shù)據(jù)結(jié)構(gòu)的優(yōu)化效果不好是因為算法在該問題上維持PWC時只進行1次約束檢測就刪空了變量域，顯然在這種實例上eSTR2w是最優(yōu)的.rand-3是1個三元問題，低元問題上極小約束范圍減少的約束檢測時間較少，無法抵消在三元隨機問題上約束檢測次數(shù)增多帶來的時間消耗，所以在這類問題上極小約束范圍降低了算法的時間效率.在renault-mod問題上，PWsup數(shù)據(jù)結(jié)構(gòu)的時間優(yōu)化效果不好是因為刪去dual圖中的多余邊后只剩下少量的邊(約束范圍交集中變量個數(shù)大于1的約束對)，而在邊較少時PWsup的效果并不理想.

Table 5　The Number of Extending Nodes and Running Time for Some Instances

5總結(jié)

本文提出了PWsup數(shù)據(jù)結(jié)構(gòu)和極小約束范圍2種方式來對eSTR算法進行優(yōu)化，PWsup數(shù)據(jù)結(jié)構(gòu)在擁有較大元組集且約束范圍交集中變量個數(shù)大于1的約束對較多的問題上具有非常明顯的時間優(yōu)化效果，而極小約束范圍在能刪去許多變量且約束擁有獨立元組集的問題上，可以減少大量的空間消耗，例如rand-12問題，極小約束范圍能夠刪去元組集中96%的列.將PWsup數(shù)據(jù)結(jié)構(gòu)和極小約束范圍相結(jié)合后便能夠在許多類問題上減少eSTR2算法的空間消耗并提高時間效率，尤其是在高元問題上，例如在MDD-25-7問題上eSTR2+P+T平均能夠減少eSTR2算法41%的CPU運行時間，同時刪去了元組集中94%的列.

參考文獻

[1]LecoutreC.STR2:Optimizedsimpletabularreductionfortableconstraints[J].Constraints, 2011, 16(4): 341-371

[2]ChengKCK,YapRHC.AnMDD-basedgeneralizedarcconsistencyalgorithmforpositiveandnegativetableconstraintsandsomeglobalconstraints[J].Constraints, 2010, 15(2): 265-304

[3]XiaWei,YapRHC.OptimizingSTRalgorithmswithtuplecompression[C]ProcofPrinciplesandPracticeofConstraintProgramming.Berlin:Springer, 2013: 724-732

[4]KatsirelosG,WalshT.Acompressionalgorithmforlargearityextensionalconstraints[C]ProcofPrinciplesandPracticeofConstraintProgramming.Berlin:Springer, 2007: 379-393

[5]JeffersonC,NightingaleP.Extendingsimpletabularreductionwithshortsupports[C]ProcoftheIntJointConfonArtificialIntelligence.MenloPark,CA:AAAI, 2013: 573-579

[6]LiHongbo,LiangYunchun,GuoJinsong,etal.Makingsimpletabularreductionworksonnegativetableconstraints[C]Procofthe27thAAAIConfonArtificialIntelligence.MenloPark,CA:AAAI, 2013: 1629-1630

[7]XuKe,LiWei.Exactphasetransitionsinrandomconstraintsatisfactionproblems[J].JournalofArtificialIntelligenceResearch, 2000, 12(1): 93-103

[8]XuKe,BoussemartF,HemeryF,etal.Randomconstraintsatisfaction:Easygenerationofhard(satisfiable)instances[J].ArtificialIntelligence, 2007, 171(8): 514-534

[9]LiHongbo,LiZhanshan,WangTao.Improvingcoarse-grainedarcconsistencyalgorithmsinsolvingconstraintsatisfactionproblems[J].JournalofSoftware, 2012, 23(7): 1816-1823 (inChinese)(李宏博, 李占山, 王濤. 改進求解約束滿足問題粗粒度弧相容算法[J]. 軟件學(xué)報, 2012, 23(7): 1816-1823)

[10]LiZhanshan,ZhangQian,ZhangLiang.Constraintsolvingbasedonthenumberofinstantiation[J].JournalofComputerResearchandDevelopment, 2015, 52(5): 1091-1097 (inChinese)(李占山, 張乾, 張良. 基于實例化次數(shù)的約束求解方法研究[J]. 計算機研究與發(fā)展, 2015, 52(5): 1091-1097)

[11]JiXiaohui,HuangZhuo,ZhangJian.Ontheintegrationofconstraintprogrammingandoptimization[J].ChineseJournalofComputers, 2005, 28(11): 1790-1797 (inChinese)(季曉慧, 黃拙, 張健. 約束求解與優(yōu)化技術(shù)的結(jié)合[J]. 計算機學(xué)報, 2005, 28(11): 1790-1797)

[12]LuRunming,LiuSheng,ZhangJian.Searchingfordoublyself-orthogonallatinsquares[C]ProcofPrinciplesandPracticeofConstraintProgramming.Berlin:Springer, 2011: 538-545

[13]JanssenP,JégouP,NouguierB,etal.Afilteringprocessforgeneralconstraint-satisfactionproblems:Achievingpairwise-consistencyusinganassociatedbinaryrepresentation[C]ProcofIEEEIntWorkshoponArchitectures,LanguagesandAlgorithmsinToolsforArtificialIntelligence.Piscataway,NJ:IEEE, 1989: 420-427

[14]BessiereC,StergiouK,WalshT.Domainfilteringconsistenciesfornon-binaryconstraints[J].ArtificialIntelligence, 2008, 172(6): 800-822

[15]PaparrizouA,StergiouK.Anefficienthigher-orderconsistencyalgorithmfortableconstraints[C]Procofthe26thAAAIConfonArtificialIntelligence.MenloPark,CA:AAAI, 2012: 535-541

[16]KarakashianS,WoodwardRJ,ReesonC,etal.Afirstpracticalalgorithmforhighlevelsofrelationalconsistency[C]Procofthe24thAAAIConfonArtificialIntelligence.MenloPark,CA:AAAI, 2010: 101-107

[17]LecoutreC,PaparrizouA,StergiouK.ExtendingSTRtoahigher-orderconsistency[C]Procofthe27thAAAIConfonArtificialIntelligence.MenloPark,CA:AAAI, 2013: 576-582

WangRuiwei.bornin1990.Master.Hismainresearchinterestsincludeconstraintprogramming.

LiZhanshan.bornin1966.PhDandProfessor.MemberofChinaComputerFederation.Hismainresearchinterestsincludemodel-baseddiagnosis,machinelearningandconstraintprogramming.

LiHongbo.bornin1985.PhD.Hismainresearchinterestsincludeconstraintprogramming.

收稿日期：2015-04-08；修回日期：2015-08-11

基金項目：國家自然科學(xué)基金項目(61170314,61272208)；吉林省自然科學(xué)基金項目(20140101200JC)

通信作者：李占山(zslizsli@163.com)

中圖法分類號TP18

Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems

Wang Ruiwei1,3, Li Zhanshan1,2,3, and Li Hongbo1,2

1(KeyLaboratoryofSymbolicComputationandKnowledgeEngineering(JilinUniversity),MinistryofEducation,Changchun130012)2(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012)3(CollegeofSoftware,JilinUniversity,Changchun130012)

AbstractTable constraints, i.e., constraints given in extension by listing all allowed (or forbidden) tuples, are very straight forward and easy to understand, which are intensively studied in constraint programming (CP). Because such constraints are presented in many real world applications from areas such as design, databases, configuration and preferences modeling. However, With the growth of number of constraints and number of tuples, the space cost for table constraints and time cost of consistency checking have become key topics. eSTR is an algorithm which extends simple tabular reduction (STR) to higher-order consistency. After in-depth analysis of eSTR algorithm, this paper proposes two kinds of optimized methods for eSTR: PWsup data structure and minimal constraint scope, and then we prove that the constraint network enforce Pair-Wise Consistency and Generalized Arc-Consistency (PWC+GAC) with minimal constraint scope is equivalent to original constraint scope. At the same time, minimal constraint scope can reduce further space cost of eSTR2 algorithm by deleting columns of the tables in constraints, and PWsupdata structure can reduce the CPU running time by avoiding some unnecessary checking of Pair-Wise-support (PW-support), since tuples in table of the constraint may not lose any PW-supports on the tables of other neighbour constraints. The experimental results show that combining our methods with eSTR2 algorithm can obviously outperform eSTR2 and eSTR2w on many instances of different problems, since it reduces the space cost and CPU running time of eSTR algorithm.

Key wordshigher-order consistency; minimal constraint scope; constraint network; PWsupdata structure; PWC+GAC

This work was supported by the National Natural Science Foundation of China (61170314,61272208) and the Natural Science Foundation of Jilin Province of China (20140101200JC).