李 曉,司懷偉,郭宗沂,李東雨,譚國(guó)真

(大連理工大學(xué) 電子信息與電氣工程學(xué)部,遼寧 大連 116024)

0 概述

約束網(wǎng)絡(luò)滿(mǎn)足弧相容(Arc Consistency,AC)要求,對(duì)于任意變量,變量論域中的任何取值可以在任意包含該變量的約束中找到支持。在回溯搜索中維持弧相容是求解約束滿(mǎn)足問(wèn)題常用的對(duì)搜索減枝的技術(shù)[1]。研究人員提出用于實(shí)現(xiàn)弧相容的算法,其中,AC3粗粒度弧相容算法及其擴(kuò)展算法維持了一個(gè)需要修訂的元素列表,在初始階段將約束網(wǎng)絡(luò)中的所有變量(或約束,取決于采用的傳播策略)加入到列表中,然后迭代取出對(duì)列表中的元素執(zhí)行修訂,將修訂過(guò)程中引入的需要修訂的元素重新加入到列表中,當(dāng)列表為空時(shí),當(dāng)前滿(mǎn)足連通性的約束網(wǎng)絡(luò)實(shí)現(xiàn)弧相容[2]。AC3粗粒度弧相容算法使用輕量數(shù)據(jù)結(jié)構(gòu)并且易于實(shí)現(xiàn),因此被廣泛用于回溯搜索解決方案[3]。

在維持相容性的過(guò)程中,可以將修訂應(yīng)用于變量、弧或約束,依此可以分為基于變量的傳播策略、基于變量間約束關(guān)系的傳播策略和基于混合變量關(guān)系(弧)的傳播策略,不同傳播策略維持的待修訂的元素列表分別有不同的實(shí)現(xiàn)[4]?；谧兞康膫鞑ゲ呗跃S持一個(gè)待修訂變量的集合,集合中每個(gè)變量所在的約束關(guān)系均是相容性被打破的約束,算法按照一定的順序從集合中取出變量并維持其所在約束的相容性,同時(shí)將維持當(dāng)前約束相容性而修改論域的變量放入集合,直到集合為空。當(dāng)前網(wǎng)絡(luò)實(shí)現(xiàn)相容性或證明當(dāng)前網(wǎng)絡(luò)不滿(mǎn)足相容性,通常以任一變量論域刪除來(lái)識(shí)別當(dāng)前網(wǎng)絡(luò)不滿(mǎn)足相容性,即該網(wǎng)絡(luò)無(wú)解。使用一個(gè)集合維持當(dāng)前待維持相容性的變量,不必在每次維持相容性時(shí)完整地掃描整個(gè)網(wǎng)絡(luò),因而是一個(gè)增量維持相容性的過(guò)程,基于約束的傳播策略和基于弧的傳播策略均是采用這種增量維持相容性的過(guò)程,因而也維持一個(gè)待更新的元素的集合,只是基于約束的傳播策略維持的是約束,基于弧的傳播策略維持的是弧,3種傳播策略分別實(shí)現(xiàn)了不同的識(shí)別并避免冗余傳播的優(yōu)化手段,具體請(qǐng)見(jiàn)文獻(xiàn)[3]。實(shí)驗(yàn)結(jié)果驗(yàn)證,基于變量傳播策略的算法實(shí)現(xiàn)通常有較為優(yōu)秀的性能表現(xiàn)[3,5]。本文提出的雙向傳播策略在維持相容性時(shí)同樣維持的是待修訂的變量的集合,但將當(dāng)前變量所在約束上的相容性維持分成2個(gè)獨(dú)立的階段,這種分階段維持相容性可以有效避免一些冗余傳播,綜合求解性能優(yōu)于現(xiàn)有的基于變量的傳播策略。

列表中元素的處理順序?qū)π抻喌男示哂酗@著影響[5],因此對(duì)其有效排序并進(jìn)行修訂是使用時(shí)序計(jì)數(shù)的主要目的。修訂效率上產(chǎn)生的影響將由核心運(yùn)算單元得到的計(jì)算時(shí)間反映出來(lái)。研究者已經(jīng)提出了多種修訂排序啟發(fā)式方法,首先利用約束網(wǎng)絡(luò)的信息,例如變量域范圍區(qū)間、約束階數(shù)和允許的值組合對(duì)列表中的元素進(jìn)行排序,dom/ddeg啟發(fā)式是一種動(dòng)態(tài)的啟發(fā)式排序算法,按照當(dāng)前變量域大小對(duì)變量進(jìn)行排序,對(duì)提高算法效率有重要作用[6]。dom/ddeg與AC3粗粒度弧相容系列算法的基于變量間關(guān)系或基于混合變量關(guān)系的傳播方案同時(shí)應(yīng)用是目前先進(jìn)的傳播策略,主要用于解決弧相容算法的加速問(wèn)題[7]。在文獻(xiàn)[7]中,基于變量的方案與dom/ddeg修訂排序啟發(fā)式集成,可以顯著減少約束檢查的數(shù)量。在文獻(xiàn)[8]中,有關(guān)約束權(quán)重的信息用于對(duì)列表中的元素進(jìn)行排序,不僅減少了約束檢查和表約束[9]的數(shù)量,還可以減少已探索搜索樹(shù)的大小壓縮解空間[10]。

文獻(xiàn)[11]結(jié)合路徑一致性給出一種解空間壓縮方式,這種解空間壓縮方式缺點(diǎn)在于得到加權(quán)有向圖的過(guò)程屬于一種緊湊表示過(guò)程,當(dāng)縮小權(quán)值范圍時(shí)導(dǎo)致部分可行解丟失,沒(méi)有維持滿(mǎn)足性條件。目前關(guān)注較多的約束滿(mǎn)足性問(wèn)題的求解技術(shù)包括簡(jiǎn)單表縮減STR、MDDC技術(shù),是約束關(guān)系壓縮表示技術(shù)[12]。基于約束關(guān)系的表約束過(guò)濾算法的傳播隊(duì)列包含必須重新修訂的約束信息[13]。文獻(xiàn)[14]建立了一種基于關(guān)系的軟約束模型,使用搜索方法探索解空間,適合處理少量變量的情況。文獻(xiàn)[15]使用搜索技術(shù)提出了并行的維持局部一致性的方法,但是由于時(shí)間代價(jià)大,尚未被廣泛應(yīng)用在求解中。文獻(xiàn)[16]提出按位運(yùn)算的表壓縮過(guò)濾算法有效壓縮處理元組,這種基于表約束的邊界處理方法使壓縮過(guò)程明顯加速。

本文基于增量的更新子網(wǎng)的方式,提出一種新的基于時(shí)序計(jì)數(shù)的傳播方案,將accumulateRevision和pushRevison作為雙向修訂的主要過(guò)程,并通過(guò)文獻(xiàn)[1]測(cè)試集進(jìn)行實(shí)驗(yàn)。

1 研究背景

一個(gè)約束網(wǎng)絡(luò)是一個(gè)元組(X,C),其中,X={x1,x2,…,xn}是一個(gè)n個(gè)變量的集合,C={c1,c2,…,cm}是m個(gè)約束的集合。每個(gè)變量xi有一個(gè)域值dom(xi),代表變量xi可行的取值集合。每個(gè)約束ci有一個(gè)約束范圍scp(ci)和一個(gè)關(guān)系rel(ci),其中scp(ci)是X的子集,并且rel(ci)是scp(ci)中滿(mǎn)足ci的元組的集合。一個(gè)二元約束只涉及2個(gè)變量,將一個(gè)xi和xj之間的二元約束描述為cij。如果2個(gè)變量共享一個(gè)約束那么被稱(chēng)為鄰居。一個(gè)弧是一個(gè)對(duì)(cij,xi),其中xi∈scp(ci)。當(dāng)關(guān)注二元約束時(shí),任何弧(cij,xi)可以表示為滿(mǎn)足xi,xj∈scp(cij)的變量對(duì)(xi,xj)。

弧(xi,xj)是AC或xi關(guān)于cij滿(mǎn)足AC的當(dāng)且僅當(dāng)對(duì)每一個(gè)a∈dom(xi),存在一個(gè)值b∈dom(xj),使得(a,b)滿(mǎn)足cij。在這種情況下,稱(chēng)b在cij上支持a。一個(gè)弧(xi,xj)的修訂或者說(shuō)與xi有關(guān)的cij需修訂保證dom(xi)所有值都支持dom(xj)。一個(gè)約束網(wǎng)絡(luò)是弧相容當(dāng)且僅當(dāng)變量沒(méi)有空域并且所有的弧都滿(mǎn)足弧相容?；∠嗳菟惴◤膁om(xi)刪除所有與不支持xi的約束。

約束滿(mǎn)足問(wèn)題(CSP)的實(shí)例由約束網(wǎng)絡(luò)定義。一個(gè)約束滿(mǎn)足問(wèn)題是可滿(mǎn)足的當(dāng)且僅當(dāng)存在至少一組解,否則該約束滿(mǎn)足問(wèn)題無(wú)解。解決CSP問(wèn)題的實(shí)例涉及找到一個(gè)(或多個(gè))解決方案或確定其不可滿(mǎn)足性。解決方案為所有變量賦值,以使所有約束都是滿(mǎn)足的。

1.1 基于約束關(guān)系的傳播策略

基于約束關(guān)系的傳播策略存儲(chǔ)以變量之間的關(guān)系為主,主要包括存儲(chǔ)弧和非單純變量,修訂時(shí)占用的存儲(chǔ)空間比基于變量的存儲(chǔ)空間大。基于純變量之間關(guān)系cij的傳播策略以變量之間的弧為傳播存儲(chǔ)單元,在FIFO結(jié)構(gòu)中,每個(gè)關(guān)系也即弧單元(xi,xj)存儲(chǔ)到列表中,依次彈出隊(duì)列進(jìn)入修改區(qū),如果弧單元(xi,xj)已被修改,即修訂標(biāo)記Reivise中DELETE元素的布爾屬性反轉(zhuǎn)為T(mén)rue,那么將新的弧單元(xk,xi)作為新的修訂內(nèi)容,即做再次修訂。在初次正向修訂時(shí),對(duì)弧中所有關(guān)系考察變量賦值,遍歷所有變量取值某個(gè)變量xi,若不存在任意一個(gè)滿(mǎn)足弧的取值,那么將此變量從弧關(guān)系中刪除,發(fā)生一次修訂,記錄一次DELETE反轉(zhuǎn)。

1.2 基于混合變量關(guān)系的傳播策略

在基于混合變量關(guān)系的傳播策略中,存儲(chǔ)單元為變量之間的關(guān)系,即弧和涉及變量,簡(jiǎn)寫(xiě)為(cij,xj),可以使用累加計(jì)時(shí)器CTR(cij,xi)避免冗余修訂,本文引入輔助參數(shù)needsNotBeRevised支持混合變量關(guān)系(cij,xj)的篩選和修訂,若needsNotBeRevised為真,那么忽略此修訂,否則將revise(cij,xj)賦給nbRemoval,如果nbRemoval(cij,xj)>0,那么判斷xj的域空間是否清空,如果域空間為空,那么此變量不滿(mǎn)足弧相容,在涉及此變量的所有相關(guān)關(guān)系的約束處理上,即對(duì)滿(mǎn)足cjk|cjk≠cij∧xj∈vars(cjk)的變量xj,將其放入隊(duì)列結(jié)構(gòu)。CTR累加轉(zhuǎn)變?yōu)?ctr(cjk,xj) ←ctr(cjk,xj)+nbRemovals。這是基于混合變量的單一循環(huán)結(jié)構(gòu)。

1.3 基于變量的傳播策略

當(dāng)Q為空或變量域消失時(shí),AC算法終止。在3種傳播方案中,基于變量的方案優(yōu)于其他2種方案。在文獻(xiàn)[18]中,CTR是某個(gè)事件發(fā)生的時(shí)間計(jì)數(shù)器,隨時(shí)間跟蹤算法的進(jìn)度識(shí)別冗余修訂。本文在基于變量的傳播策略上運(yùn)用時(shí)序計(jì)數(shù)標(biāo)記,每個(gè)變量的時(shí)序計(jì)數(shù)CTR標(biāo)識(shí)一個(gè)全局唯一的計(jì)數(shù),表示該變量論域最新發(fā)生修改的事件,每個(gè)約束的時(shí)序計(jì)數(shù)表示該約束最新滿(mǎn)足弧相容的時(shí)間[17]。

為了簡(jiǎn)化描述,本文使用revise(xi,xj)表示在xi上與cij相關(guān)的修訂。當(dāng)在一個(gè)約束cij上建立弧相容時(shí),如果CTR[xi]>CTR[cij],那么revise(xi,xj)是必要的,否則,revise(xi,xj) 是冗余的。在現(xiàn)有的采用時(shí)序計(jì)數(shù)檢測(cè)冗余revision的傳播策略中,假設(shè)cij是待處理的約束,存在一種情況,xi是最新從Q中取出來(lái)的變量,并且存在CTR[xi]>CTR[cij],而xj先于xi被處理并且存在CTR[xj]

2 基于變量的雙向傳播策略

在基于二元約束首尾變量的傳播策略中,修訂列表存儲(chǔ)的是變量xi,xj,xk,…,在隊(duì)列queue或其他數(shù)據(jù)結(jié)構(gòu)中初始化列表存儲(chǔ)這些變量。依次從基本數(shù)據(jù)結(jié)構(gòu)中彈出每個(gè)變量,對(duì)每個(gè)涉及的變量xi及其約束滿(mǎn)足eachcij|xi∈vars(cij)進(jìn)行修訂。累加計(jì)數(shù)器CTR用于識(shí)別冗余,?cij∈C,?xi∈vars(cij),CTR置為1,依然引入輔助參數(shù)needsNotBeRevised,返回邏輯運(yùn)算單元(ctr(cij,xi)>0 and ?xj∈vars(cij) |xj≠xi∧ctr(cij,xj) > 0),支持混合變量關(guān)系(cij,xj)的篩選和修訂,如果needsNotBeRevised為真,那么忽略此修訂,否則將revise(cij,xj)賦給nbRemoval;如果nbRemoval(cij,xj)>0,那么判斷xj的域空間是否清空;如果域空間為空,那么此變量不滿(mǎn)足弧相容,在涉及此變量的所有相關(guān)關(guān)系的約束處理上,即對(duì)滿(mǎn)足cjk|cjk≠cij∧xj∈vars(cjk)的變量xj,將其放入隊(duì)列結(jié)構(gòu)。CTR累加至ctr(cjk,xj) ←ctr (cjk,xj)+nbRemovals,對(duì)所有滿(mǎn)足x∈vars(cij)的變量 ctr (cjk,xj)置0。當(dāng)從傳播集合Q中選取變量xi時(shí),現(xiàn)有的基于變量的方案依次處理與xi相關(guān)的約束,對(duì)每個(gè)約束的處理包括修改約束中涉及的弧。

2.1 雙向傳播策略算法

雙向傳播策略算法如算法1～算法6所示。

算法1AC3-dual算法

begin

1.Q←{xi| xi∈ X};

2.?cij∈C,CTRs[cij]← 0

3.?xi∈X,CTRs[xi]← 1

4.while Q ≠? do

5. pick and delete xifrom Q

6. If xi∈past(P) then

7. Continue;

8. accumulateRevision(xi)

9. pushRevision(xi)

10.Return true;

end

算法2accumulateRevision(xi)算法

begin

1.for each cij| xi∈ scp(cij) ∧ CTR[xj] > CTR[cij] do

2. if revise(xi,xj) then

3. if dom(xi) =? then

4. clear Q(xi);

5. return false;

6. CTR = CTR[xi];

7. setCTR(xi);

8. if CTR[cij] > CTR then

9. setCTR(cij);

end

算法3pushRevision(xi)算法

begin

1.for each cij | xi ∈ scp(cij) ∧ CTR[xi] >CTR[cij] ∧ xj∈ past(P) do

2. if revise(xj,xi) then

3. if dom(xi) =? then

4. clear Q(xi);

5. return false;

6. Q← Q ∪ {xj};

7. setCTR(xj);

8.setCTR(cij);

end

算法4revis e(xi,xj)算法

begin

1.for each a ∈ dom(xi) do

2. if seekSupport(xi,xj,a) = false then

3. remove a from dom(xi);

4. return true;

5.return false;

end

算法5setCTR(m)算法

begin

1.CTR = CTR + 1;

2.CTR[m] = CTR;

end

算法6clearQ(x)算法

begin

1.CTR[x] = 0;

2.while Q ≠ ? do

3. pick and delete xifrom Q;

4. CTR[xi] = 0;

end

算法1給出了一種基于二元約束首尾變量的雙向傳播方案——AC3-dual,AC3-dual將維持相容性的修訂操作分為2個(gè)獨(dú)立的階段。past(P)是約束網(wǎng)絡(luò)P中已實(shí)例化變量的集合,如果檢測(cè)到約束網(wǎng)絡(luò)P不是弧相容的,則返回false,否則返回true。

算法2對(duì)應(yīng)AC3-dual的第1階段。該階段變量xi迭代xi的所有鄰居約束尋找支持,當(dāng)a∈dom(xi)在任意一個(gè)約束中無(wú)法找到有效支持時(shí),從dom(xi)中刪除a。本文利用時(shí)序計(jì)數(shù)標(biāo)記變量與約束被修訂的先后順序,只有CTR[xj]>CTR[cij]的弧(xi,xj)被修訂。當(dāng)修訂是有效時(shí)(至少一個(gè)值從dom(xi)中刪除),并且dom(xi)為空,說(shuō)明在該次修訂中,dom(xi)中所有值均在至少一個(gè)約束中沒(méi)有有效支持,因此當(dāng)前網(wǎng)絡(luò)不滿(mǎn)足相容性,算法調(diào)用clearQ,清空傳播集合Q,并且返回false,表示當(dāng)前賦值序列產(chǎn)生的約束網(wǎng)絡(luò)無(wú)解,觸發(fā)上層搜索算法回溯,撤銷(xiāo)導(dǎo)致無(wú)解的賦值。當(dāng)修訂是有效的,并且dom(xi)沒(méi)有被刪空時(shí),CTR[xi]被更新,表示dom(xi)被更新是最新的操作。注意到如果在更新CTR[xi]之前,CTR[cij]>CTR[xi],說(shuō)明約束cij在xi修改了與cij有關(guān)的約束后已經(jīng)是弧相容。在這一步更新CTR[cij]從而使得CTR[cij]>CTR[xi],避免在與cij相關(guān)的xj的冗余修訂。

算法3對(duì)應(yīng)AC3-dual的第2階段。所有xi的鄰居節(jié)點(diǎn)滿(mǎn)足CTR[xi]>CTR[cij],并根據(jù)cij進(jìn)行修訂。由于xi在第1階段根據(jù)所有xi的約束進(jìn)行修訂,并且dom(xi)的規(guī)模在當(dāng)前傳播中不再修改,尋找一種在xi上的支持非常必要。執(zhí)行修訂后,如果dom(xj)為空,表示當(dāng)前網(wǎng)絡(luò)不滿(mǎn)足相容性,當(dāng)前賦值序列無(wú)解,算法調(diào)用clearQ(x)并返回false,否則,xj被添加到Q中并且設(shè)置CTR [xj]將dom(xj)的修改標(biāo)記為最新的操作。最終約束cij變?yōu)榛∠嗳?并且CTR[cij]被更新。

2.2 雙向傳播示例

在AC3-dual中,在修訂變量xi及其所有鄰居后,涉及xi的所有約束都是弧相容(AC)的,這是AC3-dual與現(xiàn)有的基于變量的方案之間的主要區(qū)別。為了更好地說(shuō)明,本文給出以下示例。

圖1是一個(gè)二元CSP的子網(wǎng)絡(luò)。假設(shè)所有包含x1的約束依c12,c13,…,c16進(jìn)行處理。x1被選出并且從Q中刪除,變量的時(shí)序計(jì)數(shù)和約束如下:CTR[x2] < CTR[c12],CTR[x3] < CTR[c13],CTR[x4] > CTR[c14],CTR[x5] < CTR[c15],CTR[x6] > CTR[c16]。

圖1 二元約束CSP的一個(gè)子網(wǎng)絡(luò)

在現(xiàn)存的基于變量的傳播策略中,如果在處理c14時(shí)dom(x1)減小,則違反了在c14之前處理的所有約束的一致性,并且需要對(duì)它們進(jìn)行進(jìn)一步的修改,因此x1再次被添加到Q中,這種情況會(huì)在處理c16時(shí)再次發(fā)生。最終,在修改x1及其所有鄰居之后,涉及x1的約束不保證弧相容且x1可能仍然在Q中。在約束網(wǎng)絡(luò)上應(yīng)用算法1時(shí),所有k= 2,3,…,6的弧(x1,xk)在第1階段中滿(mǎn)足弧相容,因此dom(xi)在當(dāng)前傳播中不再減小。然后所有k= 2,3,…,6的弧(xk,x1)在第2階段中滿(mǎn)足弧相容。因此,在修改x1及其所有鄰居之后,所有涉及x1的約束都將成為弧相容,而x1將不會(huì)再次添加到Q中。

當(dāng)檢測(cè)到約束網(wǎng)絡(luò)不滿(mǎn)足相容性時(shí)(算法2的第3行以及算法3的第3行),發(fā)生回溯。約束網(wǎng)絡(luò)需要恢復(fù)到先前的弧相容狀態(tài)。時(shí)序計(jì)數(shù)標(biāo)記針對(duì)變量或約束的操作在全局上的先后順序,這種數(shù)據(jù)結(jié)構(gòu)相對(duì)回溯搜索是穩(wěn)定的[18],即搜索算法發(fā)生回溯時(shí)并不需要將時(shí)序計(jì)數(shù)恢復(fù)為原來(lái)的狀態(tài),因此也不需要對(duì)搜索各階段的時(shí)序計(jì)數(shù)備份,但是為了避免冗余修訂,所有的時(shí)序計(jì)數(shù)CTR[xi]應(yīng)該設(shè)置為小于所有時(shí)序計(jì)數(shù)CTR[cij]的整數(shù)[9]。本文將搜索期間約束網(wǎng)絡(luò)的所有變量劃分為3個(gè)組。第1組包括Q中的變量;第2組僅包括最近從Q中挑選的一個(gè)變量;第3組包括所有其他變量。在理解了AC執(zhí)行的過(guò)程之后,如果至少存在約束cij使得CTR [xi]> CTR [cij],那么xi必須屬于第1組或第2組。因此,當(dāng)回溯發(fā)生時(shí),只需要處理屬于組1或組2的變量的時(shí)序計(jì)數(shù)來(lái)實(shí)現(xiàn)。特別地,相關(guān)變量的標(biāo)記CTR[xi]需要設(shè)置為小于所有標(biāo)記CTR[cij]的整數(shù)。這是通過(guò)算法3中的clearQ(x)的程序完成的,該操作可以直接將時(shí)序計(jì)數(shù)CTR[xi]設(shè)置為0。

2.3 時(shí)間復(fù)雜度

AC3-dual的時(shí)間復(fù)雜度主要取決于修訂啟發(fā)式的結(jié)構(gòu),對(duì)于二元約束的數(shù)據(jù)集存在的e個(gè)約束關(guān)系,假設(shè)每個(gè)約束的約束關(guān)系包含的2個(gè)變量的論域大小為m、n,則每個(gè)約束的修訂復(fù)雜度為O(mn),為了便于觀察數(shù)量級(jí),令m=n=k,則每個(gè)變量的修訂復(fù)雜度為O(k2),使用dom/ddeg動(dòng)態(tài)決策啟發(fā)式一定程度上會(huì)減小修訂操作的計(jì)算量,但最壞時(shí)間復(fù)雜度仍與queue相同,為O(ek3)。

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

本文實(shí)驗(yàn)是在3.20 GHz Intel 8thcore i5處理器上運(yùn)行,內(nèi)存為8 GB。圖2為使用基于約束關(guān)系、基于混合變量關(guān)系和基于變量的雙向傳播策略,這3種策略應(yīng)用queue在不同測(cè)試集的修訂次數(shù)的平均對(duì)比結(jié)果。圖3為3種傳播策略使用dom/ddeg在不同測(cè)試集的修訂次數(shù)。圖4給出3種傳播策略使用queue在不同測(cè)試集的修訂時(shí)間。圖5給出3種傳播策略使用dom/ddeg在不同測(cè)試集的修訂時(shí)間。本文測(cè)試了超過(guò)1 600個(gè)實(shí)例,并在有限的600 s時(shí)間內(nèi)區(qū)分是否超時(shí),有關(guān)測(cè)試實(shí)例的詳細(xì)信息可以在C.lecoutre的主頁(yè)上找到。

圖2 3種傳播策略使用queue在不同測(cè)試集上修訂次數(shù)的對(duì)比結(jié)果

圖3 3種傳播策略使用dom/ddeg在不同測(cè)試集上修訂次數(shù)的對(duì)比結(jié)果

圖4 3種傳播策略使用queue在不同測(cè)試集上修訂時(shí)間的對(duì)比結(jié)果

圖5 3種傳播策略使用dom/ddeg在不同測(cè)試集上修訂時(shí)間的對(duì)比結(jié)果

本節(jié)通過(guò)對(duì)比不同傳播方案的修訂時(shí)間和修訂次數(shù)研究了本文傳播策略。其中,AC3-dual表示本文提出的傳播方案,RB表示經(jīng)典的基于關(guān)系的方案,應(yīng)用ctr來(lái)識(shí)別冗余修訂,VB表示應(yīng)用時(shí)間戳[18]的基于變量的傳播方案?；厮菟阉鞑捎玫淖兞颗判騿l(fā)式是dom/ddeg[6],值排序是按照字典序的排序方式。

在2種revision啟發(fā)式中,即queue啟發(fā)式和dom/ddeg啟發(fā)式,AC3-dual采用的傳播策略在擴(kuò)展單個(gè)節(jié)點(diǎn)的平均revise次數(shù),即算法在求解時(shí)調(diào)用算法4的總次數(shù)除以總擴(kuò)展節(jié)點(diǎn)數(shù),總是小于VB和RB中的revise次數(shù),這說(shuō)明AC3-dual采用的傳播策略在保證相容性不變的同時(shí),的確降低了算法執(zhí)行revise的次數(shù),原因已經(jīng)在本文第3節(jié)做了分析。AC3-dual在實(shí)例集<40,8,753,0,1>上降低revise操作的效果比較明顯,這是因?yàn)樵?40,8,753,0,1>上表示的約束網(wǎng)絡(luò)含有大量的環(huán),導(dǎo)致VB和RB在執(zhí)行revise時(shí),會(huì)頻繁地由鄰居節(jié)點(diǎn)傳向自身,增加了在維持相容性時(shí)的revise操作,AC3-dual運(yùn)行在該類(lèi)存在大量環(huán)的網(wǎng)絡(luò)中時(shí),先執(zhí)行accumulateRevision,確保所有由鄰居節(jié)點(diǎn)改變帶來(lái)的對(duì)該節(jié)點(diǎn)的修訂都已經(jīng)完成,再執(zhí)行pushRevision,將對(duì)該節(jié)點(diǎn)的修訂引起的網(wǎng)絡(luò)的變化更新到所有鄰居節(jié)點(diǎn)上,在網(wǎng)絡(luò)上存在較多環(huán)時(shí),部分避免了對(duì)當(dāng)前節(jié)點(diǎn)的修訂操作會(huì)頻繁地通過(guò)鄰居傳回自身。

從圖4和圖5可以看出,無(wú)論在queue啟發(fā)式還是在dom/ddeg啟發(fā)式中,AC3-dual降低revise操作數(shù)量帶來(lái)了求解效率的提升,AC3-dual在上述問(wèn)題上的修訂時(shí)間均小于VB和RB,對(duì)于revise操作降低比較明顯的實(shí)例集,求解效率提升較為顯著,這說(shuō)明AC3-dual采用的傳播策略在降低revise操作的同時(shí),沒(méi)有帶來(lái)太多額外的計(jì)算代價(jià)。

4 結(jié)束語(yǔ)

本文提出一種新的基于時(shí)序計(jì)數(shù)的傳播方案。該方案保留了在建立弧相容時(shí)需要修改的變量列表,并與修訂列表的啟發(fā)式相結(jié)合,在域過(guò)濾過(guò)程中進(jìn)行雙向修訂,減少修訂次數(shù)和域過(guò)濾變量的數(shù)量。實(shí)驗(yàn)結(jié)果表明,加入啟發(fā)式的雙向修訂及應(yīng)用時(shí)序計(jì)數(shù)的排序方法,提高了該傳播方案在整體求解速度和占用修訂時(shí)間性能。雖然本文弧相容傳播策略在大量問(wèn)題實(shí)例中速度明顯提升,但主要是應(yīng)用在二元約束背景中,下一步將本文傳播策略應(yīng)用到多元約束滿(mǎn)足問(wèn)題,為基于問(wèn)題重構(gòu)的高階相容性[20]引入新的刪除冗余的方法,以降低維持弧相容的代價(jià)。