董愛(ài)迪 李占山 于海鴻

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

在約束編程中,由于表約束算法可以對(duì)任何種類的約束編碼,并且表達(dá)方式簡(jiǎn)潔,所以近些年來(lái)基于表約束過(guò)濾算法被廣泛研究和使用,其中STR2[1]和STR3[2]算法是當(dāng)前主流的表縮減算法.關(guān)于表約束的研究,國(guó)內(nèi)學(xué)者關(guān)注于約束可滿足問(wèn)題中二元問(wèn)題,其中文獻(xiàn)[3]的算法將約束求解與優(yōu)化技術(shù)相結(jié)合,提高約束求解效率;李占山等人[4]提出新啟發(fā)式用于回溯搜索過(guò)程.同時(shí)為了在表約束上維持高階相容性,王瑞偉等人[5]提出一種對(duì)eSTR算法的優(yōu)化算法.而由于表約束將關(guān)系用表的方式顯示出來(lái),內(nèi)存空間的需求可能會(huì)由于參數(shù)的增加而出現(xiàn)指數(shù)型爆炸,所以為了優(yōu)化表縮減算法性能,降低約束表的空間消耗并提高廣義弧相容(generalised arc consistent, GAC)算法的運(yùn)行速度,許多用于約束表壓縮的算法相繼被提出.例如用MDD圖來(lái)表示約束關(guān)系的MDD4R[6]算法,當(dāng)子圖十分復(fù)雜且壓縮率很高時(shí),在其上維持GAC效果十分顯著.同時(shí)運(yùn)用c-tuple在笛卡兒積壓縮表上維持GAC的STR2-C算法及STR3-C[7]算法,同樣在壓縮率較大的benchmark實(shí)例上,能取得顯著的效果提升.而STR-slice[8]算法則是在分割表上維持GAC的算法,這些改進(jìn)算法都是用一種更加緊湊的方式來(lái)表示約束表,從而提高過(guò)濾性能.

在眾多成功的表壓縮方法中,我們發(fā)現(xiàn):約束表中完全長(zhǎng)度集合大小嚴(yán)重大于短支持集合,因此運(yùn)用短支持方法,利用元組的特性,將原有約束表壓縮成短表[9],減少約束元組個(gè)數(shù),更加節(jié)省空間,同時(shí)可以比原始STR算法傳播更多的約束,甚至由于內(nèi)存問(wèn)題,原始STR算法都不能將這些約束放入內(nèi)存中.但是當(dāng)壓縮率比較小時(shí)(即原約束表中元組很少能被壓縮成短約束元組),應(yīng)用短支持方法的ShortSTR2與STR2算法相比運(yùn)行速度并沒(méi)有顯著提升.而位操作[10]允許在位向量上并行操作來(lái)提高算法運(yùn)行速度,因此文中提出一種新的表壓縮算法STRO(simple tabular reduction optimizaton),結(jié)合短支持方法和位操作,保留了短支持方法中可以傳播更多結(jié)點(diǎn)的優(yōu)點(diǎn),輔以位操作并行的優(yōu)勢(shì),與主流算法STR2,ShortSTR2相比,約束表空間壓縮程度更好,且運(yùn)行速度有顯著提高;與目前維持GAC效果較好的STRbit算法相比,表壓縮率更大,可明顯降低空間消耗.

1 背景知識(shí)

定義1. 約束網(wǎng)絡(luò)(constraint network, CN)[11].約束網(wǎng)絡(luò)CN由一個(gè)包含n個(gè)變量的集合和一個(gè)包含e個(gè)約束的集合構(gòu)成.每個(gè)變量x都有一個(gè)相關(guān)的論域dom(x),其中包含了一個(gè)變量x的有限賦值集合.每個(gè)約束c都有一個(gè)集合scp(c)和一個(gè)集合rel(c),其中scp(c)是X的子集,集合內(nèi)元素是約束c涉及的變量.r表示約束c的元數(shù),在正表約束中,rel(c)是滿足約束c的元組的集合.若a∈dom(x)則(x,a)是有效的；若a?dom(x)則(x,a)是無(wú)效的.一個(gè)元組τ是(x,a)的支持當(dāng)且僅當(dāng) (x,a)∈τ.τ是有效的當(dāng)且僅當(dāng)?x∈scp(c),都有(x,τ(x))是有效的.

定義2. 短支持(short support)[9].短支持S是一個(gè)文字的集合S=(y→2,z→1),其中x∈scp(c),且文字x→v是關(guān)于Ds有效的,x在S中僅僅出現(xiàn)一次,并且S的每一個(gè)超集都包含一個(gè)有效的文字,關(guān)于scp(c)中每個(gè)變量來(lái)說(shuō)都是一個(gè)完全長(zhǎng)度支持.

在本文中,我們用完全長(zhǎng)度元組來(lái)表示短支持,*表示一個(gè)不被短支持包含的變量.假設(shè)有一個(gè)約束c涉及3個(gè)變量x,y,z,短支持S=(y→2,z→1),S用完全長(zhǎng)度表示為{*,2,1}.壓縮算法Greedy-Compress是由Jefferson等人[9]于2013年提出,描述如何將大小為r的完全長(zhǎng)度元組,逐步迭代壓縮直到不能壓縮為止.算法用UsedTuples存儲(chǔ)可以被壓縮的元組,并用CompTuples存儲(chǔ)壓縮后的元組,最終將所有可能大小的元組收集起來(lái),完成短支持壓縮.

定義3. 廣義弧相容GAC[12].一個(gè)約束c是弧相容的,當(dāng)且僅當(dāng)對(duì)每一個(gè)x∈scp(c)，每個(gè)值a∈dom(x)在c中至少存在一個(gè)支持.

定義4. 位操作(bit-wise operation)[10].位操作將約束表中元組集構(gòu)造成位表,用數(shù)組來(lái)表示約束和域,用數(shù)組bit_dom[x]表示變量的域,將變量X域中的每一個(gè)值對(duì)號(hào)入座,但是存放的不是變量值而是0或1.0表示與這個(gè)位置對(duì)應(yīng)的值不在變量X的值域中,反之則為1.同時(shí)用位向量support來(lái)表示約束表中的支持,如果元組τ對(duì)值對(duì)(x,a)關(guān)于約束C是有支持的,那么位向量在位置i的值為1,否則為0.

例1. 一個(gè)簡(jiǎn)單原始約束表如表1所示,其中dom(x)={a,b,c},dom(y)={a,b,c},dom(x)={a,b,c}.每個(gè)變量值對(duì)應(yīng)的位向量support值如表2所示.

Table 1 Constraint Table 表1 約束表

Table 2 Value of Bit Support 表2 位支持的對(duì)應(yīng)值

2 STRO算法的思想

STRO算法是結(jié)合短支持和位操作得到的簡(jiǎn)表壓縮優(yōu)化方法,其中位操作受到STRbit算法的啟發(fā),沿用了STR的算法框架.主要思想是先將約束表壓縮為短表,再將其轉(zhuǎn)化為位表,并在位表上維持GAC.整個(gè)算法可以分為3個(gè)部分:1)將原約束表壓縮成短表;2)在搜索過(guò)程中動(dòng)態(tài)刪除無(wú)效的元組;3)為每個(gè)變量值對(duì)在當(dāng)前有效的約束表中尋找支持.

為了實(shí)現(xiàn)STRO算法,需用到5種數(shù)據(jù)結(jié)構(gòu).

1)support(C,X,a).表示值對(duì)(x,a)關(guān)于約束c的位支持.

2)support*(C,X,a).表示值對(duì)(x,a)關(guān)于約束c的位短支持.

3)LAST(C,X,a).記錄的是最后一個(gè)有效位支持的位置,初始化為support.size-1.

4)DEL(C,X).集合中存放所有從值域中刪除但還未更新位表的變量值.

5)VAL(C,X).表示的是元組的有效性,初始時(shí)每個(gè)位的值均為1.

對(duì)于表1的約束表,經(jīng)過(guò)STRO算法的第1步短表壓縮后將轉(zhuǎn)變?yōu)楸?,相應(yīng)的位短支持support*的計(jì)算可以看作2部分,首先計(jì)算出原有的位支持support,而當(dāng)任何一個(gè)變量x被壓縮后,該變量的值對(duì)(x,*)的位支持support等于包含*的元組位置的位值為0,其余為1.在表4中,對(duì)于壓縮后的(y,*)值對(duì)的位支持support=(011111),將相應(yīng)值對(duì)的位支持support和(y,*)值對(duì)的位支持support進(jìn)行按位與計(jì)算,從而得到位短支持support*.例如變量值(y,a)的support(y,a)=(110100),與support(y,*)=(011111)進(jìn)行按位與計(jì)算后,得到support*(y,a)=(010100).

Table 3 Constraint Table After Short Table Compression表3 短支持壓縮后的約束表

Table 4 Value of Bit Support* After Short Table Compression表4 短支持壓縮后的位短支持的對(duì)應(yīng)值

算法1. STRO算法.

Algorithm STRO()

①S←{x|(x→a)∈shorttable∧|dom(x)|>1}；

②deleteInvalidTuple();

③ returnsearchSupport();

FunctiondeleteInvalidTuple()

① FOR all variables∈Sdo

② FORa∈DEL(C,X) do

③ FORi≤LAST(C,X,a) do

④u=support*(C,X,a)[i].

mask&VAL(C,X);

⑤ IFu≠0

⑥ save(C,VAL(C,X),restoreV);

⑦VAL(C,X)=(u) &

VAL(C,X);

⑧ ENDIF

⑨ ENDFOR

⑩ ENDFOR

FunctionsearchSupport()

① FOR all variablex∈Sanda∈dom(x) do

②now=LAST(C,X,a);

③ IFsupport(C,X,a)[now].mask&VAL(C,X)=0

④now=now-1;

⑤ IFnow<0

⑥dom(x)←dom(x){a};

⑦ AddatoDEL(C,X);

⑧ IFdom(x)=?

⑨ return false;

⑩ ENDIF

Functionsave(key,newdata,store)

① IF(key,olddata)?top(store) for any

olddata

② Addnewdatatotop(store);

③ ENDIF

STRO算法是在回溯搜索過(guò)程中維持GAC的,所以需要在初始化時(shí)就使得約束表中的元組滿足GAC.在初始化階段,VAL(C,X)中每個(gè)位值都設(shè)置為1,LAST(C,X,a)等于最后一個(gè)位支持的位置,DEL(C,X)初始為空.

STRO算法首先經(jīng)過(guò)第1步短表壓縮后,開(kāi)始動(dòng)態(tài)刪除無(wú)效的元組(調(diào)用deleteInvalidTuple方法),遍歷DEL中所有的變量,將變量的所有支持刪除,并清空DEL(C,X)數(shù)據(jù)結(jié)構(gòu),同時(shí)記錄VAL(C,X)的值.在STRO算法中support和support*的值只在創(chuàng)建時(shí)計(jì)算,不會(huì)有更改,動(dòng)態(tài)變化的是VAL(C,X)的值,用于記錄當(dāng)前約束表中元組的有效性.由于在DEL(C,X)中存儲(chǔ)的是確定的已被刪除的值,所以在刪除無(wú)效元組階段驗(yàn)證短支持有效性時(shí),我們嚴(yán)格要求提τi[x]=a,即用support*輔助刪除無(wú)效元組.

在搜索支持階段(調(diào)用searchSupport方法),STRO將為約束范圍內(nèi)的每一個(gè)變量的每一個(gè)變量值進(jìn)行位支持的有效性檢查.若support(C,X,a)[now].mask&VAL(C,X)=0,則表明在位支持中沒(méi)有包含有效元祖.now是當(dāng)前操作的位支持,當(dāng)now<0表明變量值沒(méi)有有效的位支持,將該變量值刪除并加入到DEL數(shù)據(jù)結(jié)構(gòu)中.算法中函數(shù)save中保存的數(shù)據(jù)將用于算法回溯時(shí)恢復(fù)現(xiàn)場(chǎng)使用.其中restoreV中保存的是VAL(C,X)的值,restoreL中記錄的是LAST(C,X,a)數(shù)據(jù)結(jié)構(gòu)的值.STRO算法在搜索支持后,由于為當(dāng)前約束表中的每個(gè)變量值都維持了至少一個(gè)支持,所以約束是滿足GAC的.

Jefferson等人[9]已詳細(xì)分析了STR2與Short-STR2算法的復(fù)雜度:對(duì)于一個(gè)值域大小為d且有t個(gè)元祖的變量集合U,STR2算法的復(fù)雜度為O(|U|d+|Sval|+|U|t),ShortSTR2算法的復(fù)雜度為O(rd+|Sval|+|U|t).其中Sval是STR2及ShortSTR2算法中用于保存相對(duì)于前一次的調(diào)用，論域發(fā)生改變的未賦值的變量,r為ShortSTR2算法中變量在主循環(huán)的時(shí)間消耗.

定理1. 對(duì)于r元約束,d為變量的最大值域,sn為表中各個(gè)變量值的位短支持總數(shù),在一條長(zhǎng)度為m的搜索路徑上,STRO算法的最壞時(shí)間復(fù)雜度為O(sn+r2d2+m).

證明. STRO算法維持GAC雖然有3個(gè)階段的操作,但主要的時(shí)間消耗在刪除無(wú)效元組和尋找支持2個(gè)階段.其中在刪除無(wú)效元組時(shí),若DEL(C,X)≠?,則DEL(C,X)中變量的每個(gè)變量值都要被處理一次,所以最壞時(shí)間復(fù)雜度為O(sn).尋找支持階段,LAST(C,X,a)值不變時(shí),時(shí)間復(fù)雜度為O(r2d2);LAST(C,X,a)值改變時(shí),遍歷了所有的位支持,所以STRO算法總的最壞時(shí)間復(fù)雜度為O(sn+r2d2+m).

證畢.

3 實(shí)驗(yàn)結(jié)果與分析

為了展示新表壓縮算法STRO的優(yōu)化效果,本文實(shí)驗(yàn)對(duì)比了STRO,STR2,ShortSTR2,STRbit算法的性能.文中實(shí)驗(yàn)環(huán)境為Intel?CoreTMi7-3770 CPU@ 3.40 GHz,8.00 GB的RAM,Java語(yǔ)言,所有算法采用的變量啟發(fā)式為dom/ddeg,變量值啟發(fā)式為字典序[13],實(shí)驗(yàn)中的經(jīng)典測(cè)試用例來(lái)自XCSP2數(shù)據(jù)庫(kù)[14],其中MDD0.7和MDD0.9以及rand-5-2x實(shí)例來(lái)自STR2-C論文中提出的benchmark實(shí)例[15].

表5中的數(shù)據(jù)是3種算法對(duì)于每類benchmark實(shí)例進(jìn)行測(cè)試,各個(gè)算法消耗的平均時(shí)間、運(yùn)行時(shí)間單位為s,實(shí)例的最高運(yùn)行時(shí)間設(shè)置為600 s,大于600 s則為timeout.實(shí)驗(yàn)測(cè)試了19個(gè)系列,共861組實(shí)例,表5中黑體為該系列3個(gè)算法中最短平均時(shí)間.實(shí)驗(yàn)結(jié)果表明,在90%以上的benchmark實(shí)例上,STRO算法的時(shí)間都是最優(yōu)的.尤其在MDD0.9實(shí)例上,STRO算法的運(yùn)行速度為STR2算法的20倍左右,是ShortSTR2算法的3倍左右;在MDD0.7實(shí)例中,STRO算法的運(yùn)行速度也可達(dá)到STR2算法的10倍左右.這是由于在這2組實(shí)例上,STRO算法的壓縮率非常大,所以提升效果特別明顯.而由于rand-8,tsp和aim-50系列實(shí)例的約束表在回溯搜索中的平均大小特別小(<0.004),而STRO算法相較于STR2算法需要有壓縮表的過(guò)程,所以STR2算法消耗時(shí)間要比STRO算法更少一些.在jnh實(shí)例中,由于短支持位表較小,所以STRO算法與ShortSTR2算法的CPU時(shí)間接近.

Table 5 Running Time of STR2,ShortSTR2 and STRO表5 STR2,ShortSTR2,STRO運(yùn)行時(shí)間比較

Note: The minimum average time of each row is in bold.

圖1中的矩形代表的是用STR2及STRO算法分別測(cè)試benchmark實(shí)例中經(jīng)常出現(xiàn)的時(shí)間結(jié)點(diǎn)區(qū)間.在圖1中可以清楚看到STRO算法中絕大部分的時(shí)間是集中在10 s以下,STRO算法整體運(yùn)行時(shí)間大多都小于STR2算法.

Fig. 1 Comparison of running time between STR2 and STRO圖1 STR2 與STRO時(shí)間對(duì)比盒圖

在圖2中用散點(diǎn)圖的方式更加清晰地比較STRO與STR2,ShortSTR2算法的時(shí)間性能.圖2中每個(gè)點(diǎn)都代表一個(gè)具體的實(shí)例,圖2中斜線代表2個(gè)對(duì)比算法在測(cè)試實(shí)例上消耗時(shí)間相同.在圖2(a)和圖2(b)中大部分的點(diǎn)都集中在右下角,所以STRO算法相對(duì)于ShortSTR2和STR2算法,都耗時(shí)更少、性能更好.對(duì)比圖2(a)和圖2(b)發(fā)現(xiàn):圖2(b)中的結(jié)點(diǎn)更遠(yuǎn)離紅線,因此，STRO算法相對(duì)于STR2算法的速度提升效果比STRO算法相對(duì)于ShortSTR2算法要更為明顯.并且ShortSTR2算法和STR2算法運(yùn)行超時(shí)(>600 s)時(shí),STRO算法都能夠在600 s內(nèi)完成實(shí)例的測(cè)試.

Fig. 2 Running time of STRO, STR2 and ShortSTR2圖2 STRO與STR2及ShortSTR2時(shí)間性能對(duì)比

STRO和STRbit算法的性能對(duì)比結(jié)果展示在表6中,在表6中將壓縮率和每秒處理的結(jié)點(diǎn)數(shù)作為衡量算法性能的參數(shù).可以看到,STRO與STRbit算法相比,STRO算法整體的壓縮率都比STRbit算法壓縮率要大,尤其對(duì)于實(shí)例MDD0.7,STRO算法壓縮率是STRbit算法的4倍左右,每秒處理的結(jié)點(diǎn)數(shù)是2倍以上.對(duì)于MDD0.9實(shí)例,STRO算法壓縮率是STRbit算法的20倍以上,每秒處理的結(jié)點(diǎn)數(shù)也達(dá)到了10倍以上.在實(shí)驗(yàn)中,在少數(shù)實(shí)例上STRO算法速度提升效果并不大,這是由于STRO算法需要將原約束表轉(zhuǎn)化為短表,維持了額外的數(shù)據(jù)結(jié)構(gòu),有額外的時(shí)間開(kāi)銷,但總體來(lái)講在時(shí)間上可以替代STRbit算法.

Table 6 Performance Comparison Between STRbit and STRO表6 STRbit與STRO算法的性能對(duì)比

Note: The minimum average time of each row is in bold.

4 總 結(jié)

表縮減算法STR在表約束上求解效率非常高,對(duì)于STR算法的改進(jìn)算法,近些年來(lái)也相繼被提出.其中通過(guò)表壓縮的方式,將約束表的空間壓縮從而提高效率,是STR算法的一種優(yōu)化方式.而其中的ShortSTR2算法,在壓縮率較低的情況下對(duì)于STR2算法的優(yōu)化效果并不明顯.這是由于目前沒(méi)有直接的短表,需要短支持方法維護(hù)額外的數(shù)據(jù)結(jié)構(gòu),將原有的約束表轉(zhuǎn)化為短表,所以消耗了一部分時(shí)間.但是相比STR算法,ShortSTR2算法節(jié)約了空間,可以傳播更多的結(jié)點(diǎn).基于此本文將短支持方法輔以位操作,保留短支持方法的優(yōu)勢(shì),并結(jié)合位操作提出STRO算法.實(shí)驗(yàn)結(jié)果表明:除了在約束表規(guī)模特別小的情況下,效果與STR2算法及ShortSTR2算法差別不大,STRO算法在大多數(shù)情況下優(yōu)于STR2算法及ShortSTR2算法；與STRbit算法相比,在CPU處理時(shí)間上可以替代STRbit算法,但是表壓縮率更大,更加節(jié)省空間.