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

王瑞偉　李占山　李宏博

1(符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué))　長(zhǎng)春　130012)2(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　長(zhǎng)春　130012)3　　　(吉林大學(xué)軟件學(xué)院　長(zhǎng)春　130012)

?

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

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

1(符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué))長(zhǎng)春130012)2(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院長(zhǎng)春130012)3(吉林大學(xué)軟件學(xué)院長(zhǎng)春130012)

(120801104@qq.com)

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

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

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

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

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

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

1背景知識(shí)

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

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

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

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

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

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

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

算法1. 檢測(cè)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

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

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

2) 刪掉c中所有不相容的元組后將PWsup[c]清空，因?yàn)榇藭r(shí)c中元組在所有的相鄰約束上必然存在PW支持.

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

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

算法2. 更新ctr計(jì)數(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中行⑦，當(dāng)ctr[c′][c][k]>0時(shí)將c′加入傳播隊(duì)列Q中并將c加入PWsup[c′]中，而在原來(lái)的eSTR算法[17]中，當(dāng)ctr[c][c′][j]=0時(shí)就將c′加入Q，這使得算法進(jìn)行了許多沒(méi)有必要的約束傳播，算法2是本文優(yōu)化后的結(jié)果.

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

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

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

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

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

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

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

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

Fig. 2　A 2F-dual graph.圖 2　1個(gè)2F-dual圖示例

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

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

引理1. 對(duì)于任意2個(gè)相鄰約束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，因?yàn)棣?是τ1在c2上PW支持，所以我們可知τ2和τ1在交集變量上的取值是相等的，而又因?yàn)閂是c1和c2的交集變量，所以τ1和τ2在V上的值是相等的，故可知τ2是(V，a)在c2上的支持.

證畢.

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

證明.

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

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

證畢.

證畢.

證畢.

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

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

算法3用于求約束網(wǎng)絡(luò)的極小約束范圍S，其主要思想是直接默認(rèn)變量x保留在對(duì)應(yīng)2x-dual圖的各個(gè)連通分量中第1個(gè)被訪問(wèn)到的約束c的極小約束范圍S[c]中，然后通過(guò)算法4深度優(yōu)先搜索確保對(duì)應(yīng)2x-dual圖中和c在同一連通分支上的所有其他約束不在極小約束范圍S中保留變量x.算法時(shí)間復(fù)雜度為O(|X|U2)，U表示變量中最大的度(包含某個(gè)變量的約束數(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. 汽車配置問(wèn)題可以直觀的表示為由表約束組成的約束可滿足問(wèn)題，表1中給出了1個(gè)關(guān)于汽車的簡(jiǎn)單配置問(wèn)題，主要考慮環(huán)保對(duì)配置汽車的2個(gè)簡(jiǎn)單約束:約束1是對(duì)不同類型車和發(fā)動(dòng)機(jī)類型及其發(fā)動(dòng)機(jī)排放標(biāo)準(zhǔn)的限制;約束2是限制一些汽車必須裝OBD，約束表中列出所有允許的元組.

Table 1　A Instance of Car Configuration

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

應(yīng)用極小約束范圍后，在單個(gè)約束c上執(zhí)行1次eSTR的時(shí)間復(fù)雜度是O(sd+max(s,g)t)，好于初始約束范圍的時(shí)間復(fù)雜度O(rd+max(r,g)t)[17]，其中s=|S[c]|，r=|scp(c)|，g是指約束范圍交集中變量數(shù)大于1的相鄰約束數(shù)目，t是當(dāng)前表中元組數(shù)量.但是每次約束檢測(cè)刪去的元組會(huì)減少，同時(shí)最終維持PWC+GAC要?jiǎng)h去的元組是一致的，于是增加了約束的檢測(cè)次數(shù)，總的來(lái)說(shuō)應(yīng)用極小約束范圍可以降低每次約束檢測(cè)的時(shí)間，但會(huì)增加約束檢測(cè)的次數(shù)，約束檢測(cè)是指對(duì)約束執(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時(shí)，算法只檢測(cè)元組在極小約束范圍中變量值的有效性，同時(shí)由于在eSTR算法初始化時(shí)建立了ctr計(jì)數(shù)器，檢測(cè)PW支持時(shí)也不會(huì)訪問(wèn)具體元組中的變量值.于是我們可以通過(guò)將元組集中那些不會(huì)被訪問(wèn)到的列刪去來(lái)降低eSTR算法的空間消耗，若約束c擁有獨(dú)立的元組集，那么極小約束范圍S[c]能夠減少Ο((r-s)t)的空間消耗.

4實(shí)驗(yàn)結(jié)果

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

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

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

4.1隨機(jī)問(wèn)題測(cè)試

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

Fig. 4　Experimental results of random instances.圖4　隨機(jī)實(shí)驗(yàn)結(jié)果

4.2Benchmark測(cè)試

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

Table3ResultsofDeletingVariablesbyMinimalConstraintScopeS

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

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

Table 4　Mean Running Time of Different Problem

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

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

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

5總結(jié)

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

參考文獻(xiàn)

[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ìn)求解約束滿足問(wèn)題粗粒度弧相容算法[J]. 軟件學(xué)報(bào), 2012, 23(7): 1816-1823)

[10]LiZhanshan,ZhangQian,ZhangLiang.Constraintsolvingbasedonthenumberofinstantiation[J].JournalofComputerResearchandDevelopment, 2015, 52(5): 1091-1097 (inChinese)(李占山, 張乾, 張良. 基于實(shí)例化次數(shù)的約束求解方法研究[J]. 計(jì)算機(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]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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

中圖法分類號(hào)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).