一種維持約束網絡相容性的雙向傳播策略

李 曉,司懷偉,郭宗沂,李東雨,譚國真

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

0 概述

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

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

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

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

本文基于增量的更新子網的方式,提出一種新的基于時序計數的傳播方案,將accumulateRevision和pushRevison作為雙向修訂的主要過程,并通過文獻[1]測試集進行實驗。

1 研究背景

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

弧(xi,xj)是AC或xi關于cij滿足AC的當且僅當對每一個a∈dom(xi),存在一個值b∈dom(xj),使得(a,b)滿足cij。在這種情況下,稱b在cij上支持a。一個弧(xi,xj)的修訂或者說與xi有關的cij需修訂保證dom(xi)所有值都支持dom(xj)。一個約束網絡是弧相容當且僅當變量沒有空域并且所有的弧都滿足弧相容?；∠嗳菟惴◤膁om(xi)刪除所有與不支持xi的約束。

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

1.1 基于約束關系的傳播策略

基于約束關系的傳播策略存儲以變量之間的關系為主,主要包括存儲弧和非單純變量,修訂時占用的存儲空間比基于變量的存儲空間大?；诩冏兞恐g關系cij的傳播策略以變量之間的弧為傳播存儲單元,在FIFO結構中,每個關系也即弧單元(xi,xj)存儲到列表中,依次彈出隊列進入修改區(qū),如果弧單元(xi,xj)已被修改,即修訂標記Reivise中DELETE元素的布爾屬性反轉為True,那么將新的弧單元(xk,xi)作為新的修訂內容,即做再次修訂。在初次正向修訂時,對弧中所有關系考察變量賦值,遍歷所有變量取值某個變量xi,若不存在任意一個滿足弧的取值,那么將此變量從弧關系中刪除,發(fā)生一次修訂,記錄一次DELETE反轉。

1.2 基于混合變量關系的傳播策略

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

1.3 基于變量的傳播策略

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

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

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

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

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個獨立的階段。past(P)是約束網絡P中已實例化變量的集合,如果檢測到約束網絡P不是弧相容的,則返回false,否則返回true。

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

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

2.2 雙向傳播示例

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

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

圖1 二元約束CSP的一個子網絡

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

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

2.3 時間復雜度

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

3 實驗與結果分析

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

圖2 3種傳播策略使用queue在不同測試集上修訂次數的對比結果

圖3 3種傳播策略使用dom/ddeg在不同測試集上修訂次數的對比結果

圖4 3種傳播策略使用queue在不同測試集上修訂時間的對比結果

圖5 3種傳播策略使用dom/ddeg在不同測試集上修訂時間的對比結果

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

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

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

4 結束語

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