王 濤, 王瑞芹, 李占山, 陳 超

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

約束滿(mǎn)足問(wèn)題(constraint satisfaction problem, CSP)[1]廣泛應(yīng)用于符號(hào)推理、 系統(tǒng)診斷、 配置和調(diào)度等問(wèn)題中. 尋找一個(gè)約束滿(mǎn)足問(wèn)題的解是NP難問(wèn)題[1], 目前已有很多優(yōu)秀的CSP求解算法, 其中嵌入約束傳播技術(shù)[2]的回溯算法[3]是一種應(yīng)用較廣泛的CSP求解算法. 為了處理CSP問(wèn)題的高復(fù)雜性, 已產(chǎn)生了許多CSP分解方法, 其中超樹(shù)分解是目前應(yīng)用較多的一種方法. 它把CSP的結(jié)構(gòu)表示成一個(gè)超圖. 超圖是一個(gè)圖的泛化, 每條邊都與一個(gè)變量集相關(guān)聯(lián). Gottlob等[4]提出了超圖的超樹(shù)寬度是對(duì)無(wú)環(huán)性的一個(gè)合適度量, 也是衡量對(duì)應(yīng)計(jì)算問(wèn)題是否為易處理問(wèn)題的重要指標(biāo). 超樹(shù)分解的寬度越小, 相應(yīng)問(wèn)題的處理效率越高. 決定一個(gè)超樹(shù)分解的寬度是否為k是NP難題.

文獻(xiàn)[4]指出, 對(duì)一個(gè)固定值k, 可在多項(xiàng)式時(shí)間內(nèi)決定是否存在一個(gè)分解寬度為k的超樹(shù)分解, 并提出了k-decomp算法[4]. 該算法可以構(gòu)造一個(gè)極小寬度不大于k(k-bounded) 的超樹(shù)分解(若這樣的分解存在). 另一種計(jì)算極小寬度不大于k的超樹(shù)分解方法是opt-k-decomp算法[5-9], 它是目前唯一能在多項(xiàng)式時(shí)間內(nèi)精確構(gòu)造k-bounded超樹(shù)分解的算法, 但它即使對(duì)于小的超樹(shù)也需要大量的存儲(chǔ)空間和時(shí)間. Gottlob等[10]提出了一種基于回溯的超樹(shù)分解算法det-k-decomp, 結(jié)合了精確算法和啟發(fā)式算法的優(yōu)點(diǎn), 搜索空間和產(chǎn)生超樹(shù)分解的寬度均由固定上限k限定, 即它可通過(guò)設(shè)置足夠小的k找到具有極小寬度的超樹(shù)分解. 該方法可以在產(chǎn)生的超樹(shù)寬度和計(jì)算時(shí)間之間進(jìn)行平衡. Subbarayan等[11]提出了基于回溯的超樹(shù)分解算法, 并把部件同構(gòu)的概念應(yīng)用于算法中, 以加速算法的執(zhí)行. 此外還提出了HyperSpread Decomposition和Connected HyperTree Decomposition算法, 并給出了實(shí)驗(yàn)結(jié)果, 證明了引入同構(gòu)概念后Connected HyperTree Decomposition算法的優(yōu)越性.

基于det-k-decomp算法思想, 本文把Sathiamoorthy的同構(gòu)概念引入到det-k-decomp算法中, 提出一種新的易處理的分解方法： 基于分割的超樹(shù)分解算法----sht-k-decomp.

1 定 義

一個(gè)約束滿(mǎn)足問(wèn)題(CSP)是一個(gè)三元組(X,D,C), 其中:X是一個(gè)有限變量集;D是一個(gè)有限值域集;C是一個(gè)有限約束集. 有限值域di∈D是變量xi∈X的取值集合, 每個(gè)約束ci∈C都對(duì)應(yīng)一個(gè)X的子集si及一個(gè)關(guān)系ri, 其中ri是變量集si上的關(guān)系, 它限制了si中變量的取值范圍. 若給si中所有變量一個(gè)賦值, 這些賦值的組合滿(mǎn)足關(guān)系ri, 則稱(chēng)約束ci是可滿(mǎn)足的. 一個(gè)CSP的解是對(duì)CSP中的所有變量賦值, 且這些賦值滿(mǎn)足CSP中的所有約束.

一個(gè)CSP(X,C,D)的超圖H是一個(gè)二元組(V,E), 其中:V是一個(gè)變量集, 對(duì)應(yīng)于CSP的變量集X;E為超邊的集合, 對(duì)E中的每個(gè)超邊ei, 對(duì)應(yīng)于CSP中的一個(gè)約束ci, 滿(mǎn)足ei=si. 此外, 令vars(K)=∪e(e∈k), 其中K是超邊集E的子集,K?E,

edges(L)={e|e∈E,e∩L≠?}, edgesvar(L)=vars(edges(L)),

其中L是變量集V的子集.

超圖H(V,E)的超樹(shù)是一個(gè)三元組(T,χ,λ), 其中T=(N,E)是一個(gè)樹(shù),N是T中節(jié)點(diǎn)的集合. 對(duì)超樹(shù)T中的節(jié)點(diǎn)n∈N,χ(n)對(duì)應(yīng)超圖H中變量集V的一個(gè)子集,λ(n)對(duì)應(yīng)超圖H中超邊集E的一個(gè)子集, 即

χ(n)?V,λ(n)?E.

T的子樹(shù)

用root(T)表示T的根節(jié)點(diǎn),T(n)表示T以n為根節(jié)點(diǎn)的子樹(shù).

一個(gè)超圖H(V,E)的超樹(shù)分解是一個(gè)超樹(shù)(T,χ,λ), 其中T=(N,E), 滿(mǎn)足如下條件[2]：

1) ?e∈E, ?n∈N滿(mǎn)足e?χ(n);

2) ?v∈V, 集合{n|n∈N,v∈χ(n)}可誘導(dǎo)出T的一個(gè)子樹(shù);

3) ?n∈N,χ(n)?∪λ(n);

4) ?n∈N, ∪λ(n)∩χ(T(n))?χ(n).

超樹(shù)分解(T,χ,λ)的寬度為|λ(n)|, 其中n∈N是樹(shù)T中包含超邊數(shù)目最多的節(jié)點(diǎn). 一個(gè)超圖的超樹(shù)寬度是該超圖所有超樹(shù)分解寬度的最小值, 記為htw(H). 若一個(gè)超圖H的超樹(shù)寬度htw(H)≤k, 則稱(chēng)超圖H是k-decomposable的. 圖1為一個(gè)超圖及其寬度為2的超樹(shù)分解.

對(duì)超圖H=(V,E), 若存在超邊e∈E, 滿(mǎn)足x,y∈(∪e)W, 集合V′?V是[W]-connected的, 且V′中任意兩個(gè)變量都關(guān)于W相鄰, 則稱(chēng)變量x,y∈V關(guān)于變量集W?V相鄰. 若一個(gè)[W]-component是一個(gè)極大的[W]-connected變量集V′?VW, 則稱(chēng)W為一個(gè)separator, 它對(duì)超圖的超樹(shù)分解十分重要. 本文用覆蓋相應(yīng)變量集的超邊集合表示separator和[separator]-component.

定義1[4]若對(duì)T中的每個(gè)節(jié)點(diǎn)r及r的每個(gè)子節(jié)點(diǎn)s都滿(mǎn)足以下條件, 則一個(gè)超圖的超樹(shù)分解(T,χ,λ)是規(guī)格化形式的:

1) 存在一個(gè)[χ(r)]-componentCr, 使得

χ(T(s))=Cr∪(χ(s)∩χ(r));

2)χ(s)∩Cr≠?, 其中Cr是滿(mǎn)足條件1)的[χ(r)]-component;

3) ∪λ(s)∩χ(r)?χ(s).

圖1 一個(gè)超圖及該超圖寬度為2的超樹(shù)分解示意圖Fig.1 Example of a hypergraph and its hypertree decompositon of width 2

定義2[10]令(T,χ,λ)為超圖的一個(gè)具有規(guī)格化形式的超樹(shù)分解, 且s為T(mén)中的一個(gè)節(jié)點(diǎn), 如果s滿(mǎn)足下列條件, 則稱(chēng)s是極小標(biāo)識(shí)的:

1) 若s=root(T), 則|λ(s)|=1;

2)s的父節(jié)點(diǎn)為r(存在相應(yīng)[χ(r)]-componentCr滿(mǎn)足

χ(T(s))=Cr∪(χ(s)∩λ(r)),

且滿(mǎn)足對(duì)任意e∈χ(s),

∪edges(Cr)∩∪λ(r)?∪(λ(r){e})或(λ(r){e})∩edges(Cr)=?.

定義3[10]若一個(gè)超圖的超樹(shù)分解是規(guī)格化形式的, 且它的每個(gè)節(jié)點(diǎn)都是極小標(biāo)識(shí)的, 則該超圖的超樹(shù)分解是強(qiáng)規(guī)格化形式的.

引理1[10]對(duì)超圖H的任一個(gè)寬度為k的超樹(shù)分解, 都存在一個(gè)相應(yīng)強(qiáng)規(guī)格化形式寬度為k的超樹(shù)分解.

2 Det-k-decomp算法

由det-k-decomp算法得到超圖H的超樹(shù)分解(若存在)是強(qiáng)規(guī)格化形式的.

算法1det-k-decomp(H).

FailSeps∶=?;

SuccSeps∶=?;

HTree∶=decompCov(edges(H),?);

if HTree≠NULL then

HTree∶=expand(HTree);

endif

return HTree.

算法2decompCov(Edges,Conn).

if |Edges|≤kthen

HTree∶=getHTNode(Edges,∪Edges,?);

return HTree;

endif

BoundEdges∶={e∈edges(H)|e∩Conn≠?}

for each CovSep∈cover(Conn,BoundEdges) do

HTree∶=decompAdd(Edges,Conn,CovSep)

if HTree≠NULL then

return HTree;

endif

endfor

return NULL.

算法3decompAdd(Edges,Conn,CovSep).

InCovSep∶=CovSep∩Edges

if InCovSep≠? ork-|CovSep|>0 then

if InCovSep=? then AddSize∶=1

else AddSize∶=0

endif;

for each AddSep?Edges s.t.|AddSep|=AddSize

do

Separator∶=CovSep∪AddSep;

Components∶=separate(Edges,Separator);

if ?Comp∈Components.〈Separator,Comp〉?FailSeps then

Subtrees∶=decompSub(Components,Separator);

if Subtrees≠? then

Chi∶=Conn∪∪(InCovSep∪AddSep);

HTree∶=getHTNode(Separator,Chi,SubTrees)；

return Htree;

endif

endif

endfor

endif

return NULL.

算法4decompSub(Components,Separator).

Subtrees∶=?

for each Comp∈Components do

ChildConn∶=∪Comp∩∪Separator

if 〈Separator,Comp〉∈SuccSeps then

HTree∶=getHTNode(Comp,ChildConn,?)

else

HTree∶=decompCov(Comp,ChildConn);

if HTree=NULL then

FailSeps∶=FailSeps∪ {〈Separator,Comp〉};

return ?;

else

SuccSeps∶=SuccSeps∪{〈Separator,Comp〉};

endif

endif

Subtrees∶=Subtrees∪{HTree};

endfor

return Subtrees.

圖2 Det-k-decomp各過(guò)程間的調(diào)用關(guān)系Fig.2 Procedure calls of det-k-decomp

算法1中, 集合FailSeps和SuccSeps中的元素是一個(gè)二元組〈Separator,Comp〉(這里稱(chēng)為待分解部件), 分別用于存放分解過(guò)程中分解失敗的待分解部件和分解成功的待分解部件. 這樣在分解過(guò)程中若已知當(dāng)前待分解部件可成功分解, 則把當(dāng)前待分解部件作為超樹(shù)的截止節(jié)點(diǎn)； 否則, 返回, 不繼續(xù)當(dāng)前分解. det-k-decomp是主過(guò)程, 調(diào)用decompCov,decompAdd和decompSub過(guò)程對(duì)超圖進(jìn)行分解, 并返回分解得到的超樹(shù)(若不存在, 返回空樹(shù)). 在算法1的最后, 對(duì)分解得到的超樹(shù)執(zhí)行expand函數(shù)擴(kuò)展分解過(guò)程中得到的截止節(jié)點(diǎn). 算法2～算法4是遞歸調(diào)用過(guò)程, 完成對(duì)超圖的分解. 各算法調(diào)用關(guān)系如圖2所示.

該算法中, 最重要的是separator的選擇. 對(duì)待分解超圖, 先選擇出作為分解基準(zhǔn)的separator, 再找出待分解超圖中所有的[separator]-component, 最后逐個(gè)迭代分解每個(gè)[separator]-component, 直到每個(gè)子超圖都分解為寬度不大于k的超樹(shù)為止.

每次選出的separator都應(yīng)滿(mǎn)足如下兩個(gè)基本條件:

1) ∪Edges∩∪OldSep?∪separator;

2) separator∩Edges≠?.

其中: Edges是待分解超圖(這里用超圖的超邊集合表示超圖); OldSep是上次選出的separator. 算法4先對(duì)Childconn=∪Edges∩∪OldSep進(jìn)行計(jì)算, 然后把Childconn作為參數(shù)傳遞給算法2. 算法2在超圖中尋找與Conn(即Childconn)有共同變量的所有超邊, 存放在集合BoundEdges中. 這樣BoundEdges集合中就存放了所有與∪separator有交集的超邊, 并且∪BoundEdges=∪separator. 因此, 可以考慮將超邊集合BoundEdges中的超邊作為separator, 以縮減separator的搜索空間. 首先, 從BoundEdges中選出一個(gè)最多有k個(gè)超邊的子集CovSep, 使得Conn?∪CovSep, 且CovSep?separator. 該選擇過(guò)程由Cover函數(shù)完成. Cover過(guò)程可返回所有的CovSep. 然后調(diào)用算法3, 在decompAdd過(guò)程中首先判斷CovSep是否與待分解超圖Edges有交集, 且是否|separator|≤k決定separator的最終取值, 得到的separator即滿(mǎn)足上述兩個(gè)基本條件.

選出滿(mǎn)足條件的separator后, 在算法3中調(diào)用separate函數(shù), 對(duì)待分解超圖Edges進(jìn)行分解, 并將分解得到的每個(gè)子超圖Comp, 即[separator]-component, 放入集合components中. 然后判斷components中是否存在已知不可分解的Comp, 若存在, 則重新選擇separator； 否則, 調(diào)用decompSub過(guò)程對(duì)components中的所有Comp進(jìn)行分解, 并調(diào)用getHTNode函數(shù)構(gòu)造當(dāng)前超樹(shù)節(jié)點(diǎn), 其中: Chi為此節(jié)點(diǎn)的χ標(biāo)識(shí); Separator為節(jié)點(diǎn)的λ標(biāo)識(shí); Subtrees為當(dāng)前節(jié)點(diǎn)的子樹(shù)集合.

算法4完成對(duì)當(dāng)前分解得到的各個(gè)子超圖的分解. 對(duì)每個(gè)子超圖, 先計(jì)算出其與當(dāng)前分解選出的separator的交集： Childconn作為分解該子超圖時(shí)選擇separator的依據(jù); 再判斷當(dāng)前子超圖是否已知可以成功分解, 若可以, 則把當(dāng)前部件作為截止節(jié)點(diǎn); 否則調(diào)用遞歸過(guò)程decompCov進(jìn)行分解; 根據(jù)分解結(jié)果把當(dāng)前部件存放到FailSeps或SuccSeps中; 最后返回分解得到的子樹(shù), decompSub過(guò)程結(jié)束.

在det-k-decomp算法中, Cover過(guò)程應(yīng)用了一種啟發(fā)式, 即首先按超邊中包含的Conn中變量的個(gè)數(shù)給BoundEdges中的每條超邊賦一個(gè)權(quán)值, 然后根據(jù)該權(quán)值, 從大到小進(jìn)行排序, 最后基于這個(gè)順序, 選擇出所有可覆蓋Conn的極小超邊集CovSep.

由算法2可見(jiàn), 在計(jì)算BoundEdges時(shí), 是從超圖的所有超邊中選取. 但在許多超圖例子中可以注意到： 對(duì)兩個(gè)[OldSep]-component Edges和Edges′, ∪Edges∩∪OldSep∩∪Edges′≠?, 這樣在對(duì)Edges進(jìn)行分解時(shí), 選取的separator可能會(huì)包含Edges′中的超邊. 在多數(shù)情況下, Edges′的超邊對(duì)Edges的分解沒(méi)有實(shí)際作用, 甚至有時(shí)Edges′中超邊的選取還會(huì)導(dǎo)致該次循環(huán)過(guò)程的失敗返回. 因此, 本文提出了分割的超樹(shù)分解----SHTD的概念.

3 分割的超樹(shù)分解

定義4一個(gè)超圖的分割的超樹(shù)分解SHTD=(T,χ,λ), 滿(mǎn)足如下條件：

1) 它是一個(gè)具有強(qiáng)規(guī)格化形式的超樹(shù)分解;

2) 若對(duì)T中的每個(gè)節(jié)點(diǎn)r和r的子節(jié)點(diǎn)集合S, 滿(mǎn)足?si,sj∈S, 有

λ(si)∩λ(sj)?∪λ(r).

條件2)表明在選取下一個(gè)separator時(shí), 只從OldSep和待分解的Edges中選取, 而不是從所有的超邊中選取.

對(duì)det-k-decomp算法進(jìn)行時(shí)間復(fù)雜度分析可知, 算法的時(shí)間主要是由decompCov算法的循環(huán)次數(shù)決定, 因此對(duì)BoundEdges集合的大小進(jìn)行限制, 可減少I(mǎi)nCover過(guò)程返回滿(mǎn)足條件的CovSep數(shù)目, 進(jìn)而減少CovSep的循環(huán)次數(shù), 降低時(shí)間復(fù)雜度. 令超圖H的分割的超樹(shù)寬度為shtw(H), 可知htw(H)≤shtw(H). 若shtw(H)≤k, 則稱(chēng)超圖H是s-k-decomposable的. 由于分割的超樹(shù)分解是超樹(shù)分解的一個(gè)子集, 因此分割的超樹(shù)分解也是可處理的.

文獻(xiàn)[8]中提出了同構(gòu)的概念, 在其回溯的超樹(shù)分解算法中, 待分解部分Comp是一個(gè)變量的集合, 而在det-k-decomp中則把該待分解部分Comp轉(zhuǎn)化為edges(Comp), 這兩種情況是等價(jià)的, 且

Comp=∪edges(Comp)∪OldSep.

若Comp=Comp′, 則稱(chēng)(OldSep,Comp)和(OldSep′,Comp′)是同構(gòu)的. 文獻(xiàn)[8]還證明了

Conn=∪edges(Comp)∩∪OldSep=∪edges(Comp)Comp

的選取與OldSep無(wú)關(guān). 因?yàn)锽oundEdges的取值是從所有超邊中選取, 所以separator的選取也只與Conn和Comp有關(guān), 與OldSep無(wú)關(guān). 因此, 同構(gòu)的兩個(gè)部件可分解性也是等價(jià)的. 引入同構(gòu)的概念, 可使遞歸運(yùn)算極大減少.

基于上述分析, 本文提出基于分割的超樹(shù)分解算法----sht-k-decomp算法. 該算法基于det-k-decomp算法思想, 并引入同構(gòu)的概念, 舍棄一些對(duì)分解失敗概率較大的子超圖分解, 使分解效率得到提高. 需注意的是sht-k-decomp算法得到的超樹(shù)分解并不一定是分割的超樹(shù)分解.

4 Sht-k-decomp算法

算法5Sht-k-decomp(edges(H)).

FailSeps∶=?;

SuccSeps∶=?;

HTree∶=SdecompCov(vars(edges(H)),?,?);

if HTree≠NULL then

HTree∶=expand(HTree);

endif

return HTree.

算法6SdecompCov(Comp,Conn,OldSep).

if |edges(Comp)|≤kthen

HTree∶=getHTNode(edges(Comp),∪edges(Comp),?);

return HTree;

endif

InBoundEdges∶={e∈edges(Comp)∪OldSep|e∩Conn≠?}

for each CovSep∈Cover(Conn,InBoundEdges) do

HTree∶=SdecompAdd(Comp,Conn,CovSep,OldSep)

if HTre≠NULL then

return HTree;

endif

endfor

return NULL.

算法7SdecompAdd(Comp,Conn,CovSep,OldSep).

InCovSep∶=CovSep∩edges(Comp)

if InCovSep≠? ork-|CovSep|>0 then

if InCovSep=? then AddSize∶=1

else AddSize∶=0

endif;

for each AddSep?edges(Comp) s.t.|AddSep|=AddSize do

Separator∶=CovSep∪AddSep;

Components∶=separate(Comp,Separator);

if ?SepComp∈Components.

〈Separator,SepComp〉?FailSeps then

Subtrees∶=SdecompSub(Components,Separator,OldSep);

if Subtrees≠? then

Chi∶=Conn∪∪(InCovSep∪AddSep);

HTree∶=getHTNode(Separator,Chi,Subtrees);

return Htree;

endif

endif

endfor

endif

return NULL.

算法8SdecompSub(Components,separator,OldSep).

Subtrees∶=?

for each Comp∈Components do

ChildConn∶=∪edges(Comp)∩∪separator

if Comp∈SuccSeps then

HTree∶=getHTNode(Comp,ChildConn,?)

else

HTree∶=SdecompCov(Comp,ChildConn,separator);

if HTree=NULL then

FailSeps∶=FailSeps∪{〈OldSep,Comp〉};

return ?;

else

SuccSeps∶=SuccSeps∪{Comp};

endif

endif

Subtrees∶=Subtrees∪{HTree};

endfor

return Subtrees.

本文算法基于det-k-decomp算法思想, 不同之處在于： 在sht-k-decomp算法中, 待分解部件是一個(gè)變量集合Comp, 而不是超邊集合； 對(duì)separator的選擇空間做了進(jìn)一步限制, 主要體現(xiàn)在對(duì)與變量集Conn有公共變量的超邊集(det-k-decomp算法中此集合為BoundEdges; sht-k-decomp算法中為InBoundEdges)的計(jì)算上. 此外, 在sht-k-decomp算法中本文引入了同構(gòu)概念. 但在sht-k-decomp算法中, InBoundEdges的取值是與OldSep有關(guān)的, 所以separator的選取也與OldSep相關(guān). 因此, 在sht-k-decomp算法中判斷是否已知不為k-decomposable時(shí), 就需要判斷〈OldSep,Comp〉是否屬于FailSeps, 而在判斷是否已知是k-decomposable時(shí), 可引入Sathiamoorthy的同構(gòu)概念, 即只需判斷〈comp〉是否與SuccSeps中的部件同構(gòu), 但這樣得到的超樹(shù)分解不一定是SHTD.

令由算法sht-k-decomp得到的超樹(shù)分解寬度為sdhtw(H), 則htw(H)≤sdhtw(H).

定理1Sht-k-decomp返回一個(gè)基于分割的超樹(shù)分解當(dāng)且僅當(dāng)sdhtw(H)≤k.

證明： sht-k-decomp是在det-k-decomp基礎(chǔ)上進(jìn)行改進(jìn)的. 與det-k-decomp算法相同, sht-k-decomp是一個(gè)迭代過(guò)程, 在每次迭代中, 它會(huì)循環(huán)所有可能的分解情況, 即循環(huán)滿(mǎn)足條件的separator并進(jìn)行分解, 直到成功返回一個(gè)分解寬度至多為k的分割超樹(shù)分解或在迭代循環(huán)完所有的separator后返回一顆空樹(shù). 因此, 若存在sdhtw(H)≤k的分割超樹(shù)分解, sht-k-decomp過(guò)程則一定能找到這樣的超樹(shù)分解, 并成功返回.

表1列出了分別使用det-k-decomp算法和sht-k-decomp算法對(duì)圖1中超圖進(jìn)行分解的對(duì)比結(jié)果.

表1 Det-k-decomp和sht-k-decomp分解過(guò)程對(duì)比

由表1可見(jiàn), 當(dāng)Conn={a,c,d}時(shí), det-k-decomp算法中計(jì)算得到的

BoundEdges={A,B,C,D,E,F},

其Cover函數(shù)可返回的CovSep順序?yàn)閧B,C},{A,B},{B,F},{C,E},{C,D},{A,E},{E,F}. 而對(duì)sht-k-decomp算法, 計(jì)算得到的InBoundEdges={B,E,A,F}, Cover函數(shù)可返回的CovSep順序?yàn)閧A,B},{B,F},{A,E},{E,F}. 對(duì)超圖的分解, sht-k-decomp中會(huì)避免det-k-decomp中因CovSep取{B,C}而導(dǎo)致分解失敗的情況. 這是較小的例子, 對(duì)較大的例子, 超邊越多, 這種情況出現(xiàn)的幾率就越大, 此時(shí)用sht-k-decomp會(huì)極大提高分解效率.

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

本文使用文獻(xiàn)[10]中的部分測(cè)試用例對(duì)det-k-decomp算法和sht-k-decomp算法進(jìn)行對(duì)比. 測(cè)試環(huán)境為硬件DELL Intel Core 2 Duo 2.93 GHz CPU/2.0 Gb RAM； 軟件Windows XP Professional SP2/Visual C++6.0. 每個(gè)用例測(cè)試10次, 取平均值作為最后結(jié)果.

在測(cè)試用例時(shí), 本文設(shè)置時(shí)間限制為3 600 s, 并令k為不大于從det-k-decomp算法中已得到的最小分解寬度的值. 實(shí)驗(yàn)結(jié)果列于表2和表3. 表2和表3為在時(shí)間限制范圍內(nèi)得到的測(cè)試結(jié)果, 其中|V|和|E|分別為待分解超圖包含的變量數(shù)和超邊數(shù). 對(duì)這兩個(gè)算法, 用兩組屬性進(jìn)行比較： 運(yùn)行時(shí)間和最小分解寬度, 并把分解寬度作為最重要的對(duì)比標(biāo)準(zhǔn). 在最小分解寬度相同的條件下, 運(yùn)行時(shí)間越少, 算法運(yùn)行效率越高.

表2 DaimlerChrysler和Grid2D標(biāo)準(zhǔn)庫(kù)測(cè)試用例

表3 ISCAS89標(biāo)準(zhǔn)庫(kù)測(cè)試用例

由表2和表3可見(jiàn), 對(duì)所有例子, sht-k-decomp算法得到的最小分解寬度與det-k-decomp算法的最小分解寬度相同, 且多數(shù)情況下sht-k-decomp算法的執(zhí)行效率高于det-k-comp算法.

綜上所述, 本文提出了一種新的超樹(shù)分解方法： 分割的超樹(shù)分解----SHTD, 并基于分割的超樹(shù)分解所具有的特征提出了一種新的超樹(shù)分解算法----基于分割的超樹(shù)分解算法sht-k-decomp. 分割的超樹(shù)分解是超樹(shù)分解的子集, 它較易處理且htw(H)≤shtw(H). 算法sht-k-decompc通過(guò)進(jìn)一步縮小separator的搜索空間和引入同構(gòu)概念對(duì)算法det-k-decomp進(jìn)行改進(jìn). 采用文獻(xiàn)[10]部分用例進(jìn)行測(cè)試, 結(jié)果表明在多數(shù)情況下, sht-k-decomp算法高于det-k-decomp算法的效率, 且對(duì)所有的例子它們的最優(yōu)分解寬度相同.

[1] Freuder E C, Mackworth A K. Constraint Satisfaction: An Emerging Paradigm [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 13-27.

[2] Bessière C. Constraint Propagation [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 29-84.

[3] Beek P, Van. Backtracking Search Algorithms [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 85-134.

[4] Gottlob G, Leone N, Scarcello F. Hypertree Decompositions and Tractable Queries [J]. Journal of Computer and System Sciences, 2002, 64(3): 579-627.

[5] Gottlob G, Leone N, Scarcello F. On Tractable Queries and Constraints [C]//Proceedings of the 10th International Conference on Database and Expert System Applications (DEXA). London: Springer-Verlag, 1999: 1-15.

[6] Leone N, Mazzitelli A, Scarcello F. Cost-Based Query Decompositions [C]//Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD). Portoferraio: [s.n.], 2002: 390-403.

[7] Scarcello F, Greco G, Leone N. Weighted Hypertree Decompositions and Optimal Query Plans [J]. Journal of Computer and System Sciences, 2007, 73(3): 475-506.

[8] Gottlob G, Leone N, Scarcello F. A Comparison of Structural CSP Decomposition Methods [J]. Artificial Intelligence, 2000, 124(2): 243-282.

[9] Harvey P, Ghose A K. Reducing Redundancy in the Hypertree Decomposition Scheme [C]//Proceedings of the 15th International Conference on Tools with Artificial Intelligence. LosAlamitos, CA: IEEE Computer Society, 2003: 474-481.

[10] Gottlob G, Samer M. A Backtracking-Based Algorithm for Hypertree Decomposition [J]. Journal of Experimental Algorimics (JEA), 2008, 13(1): Article No.1.

[11] Subbarayan S, Andersen H R. Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs [C]//Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India: [s.n.], 2007: 180-185.