一種基于時(shí)間戳的簡單表縮減算法?

楊明奇 , 李占山 , 張家晨

1(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長春 130012)

2(符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)),吉林 長春 130012)

約束傳播(或局部相容性)作為一種有限的推理方法[1],被廣泛應(yīng)用于求解約束滿足問題.目前比較成功的一種方法是將回溯搜索與約束傳播相結(jié)合,在預(yù)處理以及回溯搜索的每一階段刪除不滿足相容性的賦值來降低搜索空間.局部相容性根據(jù)用于推理的約束子網(wǎng)的規(guī)?？梢苑譃椴煌瑥?qiáng)度的相容性,通常,更強(qiáng)的相容性意味著更強(qiáng)的剪枝能力和更高的實(shí)現(xiàn)復(fù)雜度,而廣義弧相容(generalized arc consistency,簡稱GAC)是研究最多且應(yīng)用最廣泛的局部相容性方法.

近年來,在配置、數(shù)據(jù)庫、偏好建模等領(lǐng)域有著重要應(yīng)用的表約束求解方法受到了大量學(xué)者關(guān)注.表約束上的弧相容算法研究誕生了許多成功的技術(shù),其中,simple tubular reduction(STR)[2]是一種可以動(dòng)態(tài)維持元組集有效部分的算法.STR 使用一種簡單的數(shù)據(jù)結(jié)構(gòu)sparse set[3,4]表示元組的序號,具有增量維持元組集的有效部分以及單位時(shí)間的回溯代價(jià)的性質(zhì).STR2[5]對STR 提出兩點(diǎn)改進(jìn):(1)只對相鄰兩次調(diào)用中元組對應(yīng)變量論域發(fā)生改變的位置檢測有效性,實(shí)現(xiàn)了增量檢測元組有效性;(2)當(dāng)變量中所有值均找到支持時(shí),停止為該變量查找支持,避免了無用的支持查找.STR3[6]類似GAC4 是路徑最優(yōu)的,通過查詢dual table,找到并刪除無效值對應(yīng)的無效元組,再通過被刪除的無效元組為其他變量值更新支持.這避免了STR2 中可能存在的對約束表同一區(qū)域的重復(fù)查找,但dual table 中需要處理的元組數(shù)目是原始表中約束元數(shù)的倍數(shù),當(dāng)約束元數(shù)較高時(shí),同樣會存在較多重復(fù)的查找,路徑最優(yōu)方法對于能否提升維持GAC 的效率并不明確.例如,在多數(shù)實(shí)例上,STR2 的效率優(yōu)于STR3[7,8].AdaptiveSTR[9]給出了一種自適應(yīng)的表縮減方法,可以根據(jù)當(dāng)前約束表中有效部分的規(guī)模,自適應(yīng)地選擇代價(jià)較低的表縮減策略.文獻(xiàn)[10]改善了STR2 在有效元組集縮減較慢時(shí)的性能.

將元組集壓縮表示可以降低待處理的元組集的規(guī)模,也是一種有效的提高維持GAC 效率的方法,并受到了深入的研究.其中,MDD 算法[11]將每個(gè)約束的元組集建成一個(gè)多值決策圖,當(dāng)多值決策圖中同構(gòu)的子圖較多時(shí),壓縮率較高.在基于STR 的壓縮方法中,STR2-C 和STR3-C[12]將多個(gè)元組表示為一個(gè)c-tuples[13];ShortSTR[14]將多個(gè)元組表示為一個(gè)短元組;STR-slice[15]將多個(gè)元組表示為關(guān)聯(lián)模式的子表;STRbit[16]用和 Compact-Table[17]均采用比特位表示元組序號,一次比特操作可以同時(shí)處理多個(gè)元組.此類元組集壓縮方法維持GAC 的效率受限于壓縮率,當(dāng)壓縮率較高時(shí)加速顯著;當(dāng)壓縮率降低時(shí),加速效果減弱,部分方法會發(fā)生退化,例如,MDDc、STR2-C、STR3-C 在壓縮率較低的問題上效率低于STR2,STR3.

表約束上的高階相容性算法[18-21]也受到廣泛研究,目前應(yīng)用較為成功的高階相容性有pairwise consistency(PWC)[22]以及弱化版PWC,從降低維護(hù)代價(jià)的角度出發(fā),最新的維持高階相容性算法,例如FE[8]、FDE[23],均采用對約束問題重構(gòu)的策略,并證明了采用特定的重構(gòu)方法,在重構(gòu)后的問題上維持GAC 等價(jià)于對原問題維持PWC 或更高階段相容性.值得注意的是,這些方法均通過實(shí)驗(yàn)證實(shí),使用STR2 對重構(gòu)后的問題維持GAC 的效率高于MDDc,STR3 在重構(gòu)問題上維持GAC 的效率.

本文提出的STR2*是一種非基于表壓縮的STR 算法,具有直接處理原始表、實(shí)現(xiàn)簡單等特點(diǎn).STR2*采用了一種全新的動(dòng)態(tài)維持元組集有效部分的方法,包含效率更高的檢測元組有效性以及為變量值更新支持的方法.實(shí)驗(yàn)結(jié)果表明,STR2*擁有比STR2 和STR3 更高的維持GAC 的效率,在元組集數(shù)目極小時(shí),STR2*趨近于STR2;在元組集數(shù)目增多時(shí),STR2*相對于STR2 和STR3 提升顯著.對于元組集規(guī)模縮減較快的問題,STR2*優(yōu)于現(xiàn)有的基于表壓縮的算法.

1 背景知識

一個(gè)約束滿足問題P=(X,C),其中,X是變量集合{x1,...,xn},C是約束集合{c1,...,ce}.dom(x)是x∈X的當(dāng)前有效論域.我們使用(x,a)表示x的一個(gè)值a(在不引起混淆的情況下,也可直接表示為a),如果a∈dom(x),我們稱a是有效的;否則,a是無效的.每個(gè)c∈C包括兩個(gè)部分:scp(c)是X中有序的變量子集,表示c的約束范圍,c的元數(shù)是|scp(c)|;rel(c)是與scp(c)對應(yīng)的元組的集合.給定scp(c)={x1,...,xn},rel(c)?表示scp(c)包含的變量中所有可滿足的值的組合的集合.我們規(guī)定,所有元組集都是有序的.給定一個(gè)有序變量集合S?scp(c)和一個(gè)元組t∈rel(c),t關(guān)于S的投影t[S]表示t中與S中變量對應(yīng)的部分.t是(x,a)在c中支持ifft[x]=a.t關(guān)于x是有效的 ifft[x]∈dom[x];t是有效的 iff 對于任意x∈scp(c),t關(guān)于x是有效的;c關(guān)于x∈scp(c)是有效的 iff 對于任意t∈c,t關(guān)于x是有效的;c是有效的 iff 對于任意x∈scp(c),c關(guān)于x是有效的.顯然,c是有效的 iffc中所有元組都是有效的.

定義1(廣義弧相容generalized arc consistency(GAC)).對于一個(gè)約束滿足問題P,(x,a)關(guān)于c是GAC 的iffc中存在一個(gè)(x,a)的有效支持;x關(guān)于c是GAC 的iff 對于任意a∈dom(x),(x,a)關(guān)于c是GAC 的;c是GAC 的iff 對于任意x∈scp(c),x關(guān)于c是GAC 的;P是GAC 的iff 對于任意c∈C,c是GAC 的.

P的一個(gè)解是一個(gè)約束范圍為X的有效元組,使得所有約束都被滿足,P是可滿足的iff 存在至少一個(gè)解.確定一個(gè)約束滿足問題是否是可滿足的是NP-hard.顯然,當(dāng)一個(gè)值(x,a)不是GAC 時(shí),該值不會出現(xiàn)在任何解中,維持GAC 就是通過在回溯搜索的每一個(gè)階段刪除所有不滿足GAC 的值,產(chǎn)生對搜索樹剪枝的效果.

2 STR2*

STR2*基于回溯搜索中動(dòng)態(tài)維持元組集的有效部分的思想,即在搜索的每一階段變量論域發(fā)生刪減時(shí),刪除所有與被刪除的值關(guān)聯(lián)的無效元組;同時(shí),在回溯時(shí)恢復(fù)因回溯而重新變?yōu)橛行У脑M.STR2*采用如下數(shù)據(jù)結(jié)構(gòu).

?table(c)是存儲了正表約束c中所有元組的數(shù)組,每個(gè)元組按在table(c)數(shù)組中的位置唯一標(biāo)識,table(c).length表示約束c中元組的總個(gè)數(shù).

?position(c)是存儲了約束c中每個(gè)元組在table(c)中的位置的數(shù)組,c中第i個(gè)元組為table(c)[position(c)[i]].在任意時(shí)刻,position(c)中的值是{0,1,2,...,table(c).length-1}的排列.

?currentLimit(c)是一個(gè)記錄position(c)中最后一個(gè)有效元組位置的整數(shù),-1≤currentLimit(c)≤position(c).length-1,當(dāng)currentLimit(c)=-1 時(shí),c中當(dāng)前有效元組數(shù)目為0.

?levelLimit(c)記錄回溯搜索中每一次賦值前position(c)中最后一個(gè)有效元素的位置,用于對currentLimit(c)的備份和恢復(fù).

table(c)是一個(gè)僅用于查詢的表,在STR2*中,一個(gè)約束c中第n個(gè)元組對應(yīng)變量x位置的取值為a=table(c,x)[t].由于c中元組的個(gè)數(shù)遠(yuǎn)大于約束的元數(shù),采用這種表示方法的table(c)可以最大限度地利用連續(xù)的存儲空間,加速查詢速度.position(c)中包含了回溯搜索中c的當(dāng)前有效元組和無效元組兩個(gè)部分,其中,position(c)[0]到position(c)[currentLimit(c)]是有效部分,position(c)[currentLimit(c)+1]到position(c)[position(c).length-1]是無效部分.當(dāng)一個(gè)元組position(c)[i]因無效被刪除時(shí),我們只需將position(c)[i]與position(c)[currentLimit(c)]交換,然后將currentLimit(c)減1.而回溯時(shí)只需恢復(fù)currentLimit(c)的值,便實(shí)現(xiàn)了對已刪元組的恢復(fù).顯然,回溯發(fā)生后,元組在position(c)中的順序發(fā)生了改變,但這不影響算法的正確性.借助于上述數(shù)據(jù)結(jié)構(gòu),STR2*可以動(dòng)態(tài)地維持元組集的有效部分,并且只需要單位時(shí)間的恢復(fù)代價(jià).STR2*基本沿用了STR2 的數(shù)據(jù)結(jié)構(gòu),只是table(c)采用了一種與STR2 中table(c)[5]互補(bǔ)的表示方法.

STR2*包含兩個(gè)部分.第1 部分對應(yīng)于算法1 的第1 行～第11 行,算法檢測約束c中元組有效性并刪除無效元組.一個(gè)元組是無效的當(dāng)且僅當(dāng)存在至少一個(gè)(x,a)∈t是無效的.對于任一變量x∈scp(c),如果dom(x)在上次調(diào)用STR2*后沒有發(fā)生改變,則c中所有元組關(guān)于x仍然是有效的,無需再次檢測.因此,我們僅對c中元組在變量論域發(fā)生改變的位置上檢測有效性.我們通過變量的時(shí)間戳和其所在約束的時(shí)間戳大小關(guān)系,識別變量論域在上一次調(diào)用STR2*后是否發(fā)生改變,每一個(gè)約束c和每一個(gè)變量x在回溯搜索中被賦予一個(gè)全局唯一的時(shí)間戳.time是一個(gè)全局計(jì)數(shù)器,用于標(biāo)識不同事件發(fā)生的先后次序和更新變量和約束的時(shí)間戳,變量x論域發(fā)生改變時(shí),stamp[x]被更新為當(dāng)前的time;在約束c上STR2*時(shí),stamp[c]被更新為當(dāng)前的time.當(dāng)stamp[x]

圖1 是STR2*在檢測階段動(dòng)態(tài)維持當(dāng)前有效表的一個(gè)例子,scp(c)={x,y,z}.

?圖1(a)是約束c的table(c),假設(shè)初始階段約束c的狀態(tài)為currentLimit(c)=10,約束c中滿足stamp[x]>stamp[c]的變量集合為{x,y,z},dom(x)={a,b},dom(y)=,dom(z)={a,c}.

?圖1(b)是檢測c關(guān)于x的有效性,即檢測position(c)[0]到position(c)[10]中,元組關(guān)于x的有效性.8-th～10-th 元組被刪除,currentLimit(c)=7.

?圖1(c)是檢測c關(guān)于y的有效性,即檢測position(c)[0]到position(c)[7]中,元組關(guān)于y的有效性.2-th～4-th、7-th 元組被刪除,currentLimit(c)=3.

?圖1(d)是檢測c關(guān)于z的有效性,即檢測position(c)[0]到position(c)[3]中元組關(guān)于z的有效性.5-th、0-th元組被刪除,currentLimit(c)=3.

最終,c的當(dāng)前有效元組為6-th、1-th 元組.

Fig.1 Demonstration of executing STR2* on the constraint c圖1 STR2*在表約束c 上的執(zhí)行演示

STR2*的第2 部分對應(yīng)于算法1 的第12 行～第26 行,算法分別為未賦值變量更新支持,并刪除沒有支持的變量值.外層是對變量的迭代,內(nèi)層循環(huán)是對當(dāng)前有效元組的迭代.當(dāng)size=|dom(x)|時(shí),dom(x)中所有值均找到支持,算法跳出當(dāng)前迭代,對應(yīng)于算法1 的第21 行、第22 行.所有論域發(fā)生刪減的變量被更新時(shí)間戳,并放入集合Xevt.c中所有變量均被處理后,更新c的時(shí)間戳.

算法1.STR2*(c:constraint):set of variables.

算法2.setStamp(m:index of variable or constraint).

2.1 復(fù)雜度分析

性質(zhì)1.對于包含n個(gè)元組的r元約束c,STR2*的時(shí)間復(fù)雜度為O(r+(Sval+Ssup)×n),其中,Sval表示c中滿足stamp[x]>stamp[c]的個(gè)數(shù),Ssup表示c中未賦值變量的個(gè)數(shù).

證明:算法1 的第2 行和第12 行的時(shí)間復(fù)雜度為O(r),檢測元組集關(guān)于一個(gè)變量有效性的復(fù)雜度為O(n),因此,第1 部分的時(shí)間復(fù)雜度為O(r+Sval×n).在剩余的有效元組集上,為一個(gè)變量查找支持的復(fù)雜度為O(n),因此,第2 部分的時(shí)間復(fù)雜度為O(r+Ssup×n).STR2*的總時(shí)間復(fù)雜度為O(r+(Sval+Ssup)×n).□

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

我們在非二元正表約束上測試STR2*與現(xiàn)有STR 算法的性能.測試所用實(shí)例均來自CSP 求解大賽,可在http://www.cril.univ-artois.fr/～lecoutre/#下載.我們測試了正表實(shí)例,并將部分包含負(fù)表的實(shí)例轉(zhuǎn)換成正表測試.程序采用java 編寫,運(yùn)行環(huán)境為Intel i5@3.2Ghz 處理器、4GB 內(nèi)存、windows10 64 位操作系統(tǒng).回溯搜索采用dom/ddeg的變量啟發(fā)式、字典序的值啟發(fā)式和domv的revise啟發(fā)式[24].每個(gè)實(shí)例的求解時(shí)間上限為600s,T/O表示求解時(shí)間超過600s,所有算法均在找到第1 組解或判定無解后結(jié)束.

表1 分別給出了STR2*、STR2 和STR3 在多組實(shí)例集上的平均運(yùn)行結(jié)果.#表示每組實(shí)例集測試的實(shí)例的個(gè)數(shù);STR2*、STR2 和STR3 分別表示3 種算法的平均運(yùn)行時(shí)間,單位是s;avgTuple是回溯搜索中表約束的平均大小;avgP是avgTuple與初始表約束大小的比值;avgSval是回溯搜索中Sval的平均大小.在圖2 的散點(diǎn)圖中,每個(gè)點(diǎn)表示一個(gè)實(shí)例.

Table 1 Mean results of different algorithms表1 不同算法的平均結(jié)果

Fig.2 Comparisons of STR2 and STR2*,STR3 and STR2* in duration for finding a solution圖2 STR2 和STR2*、STR3 和STR2*的求解時(shí)長的對比

?STR2* VS STR2

STR2*采用全新的動(dòng)態(tài)維持元組集有效部分的方法維持GAC 的效率顯著高于STR2.當(dāng)avgTuple>>avgSval時(shí),STR2*相對于STR2 擁有4 倍以上的效率提升.對于一些表約束規(guī)模極小的實(shí)例,avgTuple近似等于avgSval,STR2 和STR2*維持元組集有效部分的代價(jià)都很低,兩種算法的效率近似.表1 和圖2 中左圖可以看出,STR2*整體優(yōu)于STR2,在大多數(shù)實(shí)例上有2 倍～4 倍的效率提升.

?STR2* VS STR3

在一些表約束規(guī)模極小的問題上,STR2*得益于運(yùn)用的數(shù)據(jù)結(jié)構(gòu)簡單維護(hù)代價(jià)較低,求解效率高于STR3.在多數(shù)實(shí)例上,隨著搜索的向下進(jìn)行,元組集規(guī)?？s減較快,avgP<30%,STR2*優(yōu)于STR3;在少數(shù)元組集縮減較慢的實(shí)例上,avgP>30%,并且表約束規(guī)模足夠大時(shí),STR3 優(yōu)于STR2*.從表1 和圖2 中右圖可以看出,在絕大多數(shù)實(shí)例上,STR2*優(yōu)于STR3;在部分實(shí)例上,STR2*的效率是STR3 的20 倍以上.

我們同樣將STR2*與基于表壓縮的STR 算法進(jìn)行了對比,基于表壓縮的STR 采用分目前公認(rèn)性能最優(yōu)的STRbit.表2 中,STR2*和STRbit分別表示3 種算法的平均運(yùn)行時(shí)間,單位是s.圖3 是STR2*和STRbit 效率對比的散點(diǎn)圖,每個(gè)點(diǎn)代表一個(gè)問題實(shí)例.

Table 2 Mean results of STR2* and STRbit表2 STR2*和STRbit 的平均結(jié)果

Fig.3 Comparisons of STRbit and STR2* in duration for finding a solution圖3 STRbit 和STR2*的求解時(shí)長的對比

?STR2* VS STRbit

在一些拓?fù)浣Y(jié)構(gòu)復(fù)雜且表約束規(guī)模較小的實(shí)例上,例如aim、varDimacs 和dubois,兩種算法維持元組集有效部分的代價(jià)都比較低,STR2*得益于運(yùn)用的數(shù)據(jù)結(jié)構(gòu)簡單維護(hù)代價(jià)較低,求解效率稍優(yōu)于STRbit.在一些元組集規(guī)?？s減較快的實(shí)例上,例如rand-15-23、rand-8-20 和bddsmall,STR2*優(yōu)于STRbit,擁有超過2 倍的效率提升.表2 可以看出,STR2*在所有16 類問題的9 類中優(yōu)于STRbit.由于不同類問題的實(shí)例集中的實(shí)例個(gè)數(shù)差別較大,例如STRbit 效率更高的rand-3、rand-5 和crossword 這3 類問題的實(shí)例總個(gè)數(shù)占到所有測試實(shí)例的60%,在圖3 的散點(diǎn)圖中,才會有STRbit 在多數(shù)實(shí)例上效率優(yōu)于STR2*的效果.

4 總結(jié)

我們提出了一種表約束上維持GAC 的算法STR2*,采用了一種新的動(dòng)態(tài)維持元組集有效部分的方法.實(shí)驗(yàn)結(jié)果證實(shí),STR2*維持GAC 的效率均高于STR2 和STR3,并且在元組集縮減較快的問題以及元組集規(guī)模較小的問題上優(yōu)于最新的采用表壓縮的STRbit.今后,我們希望將這種新的動(dòng)態(tài)維持元組集有效部分的方法運(yùn)用到其他基于STR 的算法中.