互斥約束工作流可滿足性決策的匹配剪枝模式回溯法

翟治年 盧亞輝 萬 健,3 王中鵬 吳茗蔚

1.浙江科技學(xué)院信息與電子工程學(xué)院，杭州，310023 2.深圳大學(xué)計算機(jī)與軟件學(xué)院，深圳，518060 3.復(fù)雜系統(tǒng)建模與仿真教育部重點實驗室，杭州，310018

0 引言

云制造是一種面向服務(wù)的網(wǎng)絡(luò)化制造新模式,它將分布式制造資源通過云平臺集約化運營，使客戶可根據(jù)需求靈活租用資源，快速組織定制化的生產(chǎn)。在這種模式下，資源的多源性和虛擬性給客戶的業(yè)務(wù)過程帶來了更嚴(yán)重的安全隱患。

云制造業(yè)務(wù)依賴于平臺的服務(wù)注冊、匹配、組合、執(zhí)行等支撐功能[1]。通常，制造需求可分解為若干有序的步驟，形成一個工作流。對它進(jìn)行授權(quán)規(guī)劃，根據(jù)每個步驟的制造功能要求，在注冊服務(wù)中進(jìn)行搜索，為其匹配若干候選的服務(wù)資源。由于同一步驟的候選服務(wù)功能相同，因此須根據(jù)客戶的非功能需求進(jìn)行服務(wù)組合，即定義服務(wù)質(zhì)量優(yōu)化目標(biāo)和約束條件，求解相應(yīng)的資源分配問題，為每個步驟指定唯一的執(zhí)行服務(wù)。服務(wù)組合是滿足客戶需求的關(guān)鍵。不過，有關(guān)研究多強(qiáng)調(diào)一定業(yè)務(wù)指標(biāo)或系統(tǒng)特性的優(yōu)化，例如完工時間、資源利用率、可靠性等[2-4]，而忽略了業(yè)務(wù)的安全性要求。特別地，服務(wù)提供者在完成步驟時可獲取相關(guān)業(yè)務(wù)數(shù)據(jù)，有非法使用的可能。然而服務(wù)由大量第三方以虛擬資源形式提供，客戶很難對提供者進(jìn)行有效鑒別。為了降低有關(guān)安全隱患，客戶往往需要在特定步驟之間施加某種職責(zé)分離約束，例如禁止關(guān)鍵零件的加工步驟使用同一執(zhí)行服務(wù)，以免產(chǎn)品設(shè)計被組合破解。附加安全約束的業(yè)務(wù)過程不一定是可行的，這就產(chǎn)生了所謂工作流可滿足性決策(workflow satisfiability decision，*WS)問題。

*WS尋求同時滿足給定約束和授權(quán)規(guī)劃的任意一個資源分配，可驗證授權(quán)規(guī)劃的可行性，為業(yè)務(wù)的安全執(zhí)行提供必要的保證?；コ馐且环N應(yīng)用廣泛的二元職責(zé)分離約束，相應(yīng)的*WS問題記為*WS(≠)，有非常重要的意義。該問題是NP完全的[5]，對于該問題，確定性算法對中小規(guī)模實例有不錯的效果，并可以保證完備性(問題無解時能夠正確識別)，本文將進(jìn)一步研究其性能優(yōu)化問題，以推動相關(guān)求解技術(shù)的進(jìn)步。

*WS問題的資源分配解為每個步驟分配一個資源,也為每個資源指定一個步驟子集(可為空，但要求這些步驟子集恰為所有步驟的一個劃分)?；谇罢?，可以建立明確的解空間(以步驟為變量，資源為值的變量分解樹)，通過搜索特別是回溯法搜索求任意一個可行解?；诤笳撸诤芏嗉s束條件下，為任一資源合法指定任一步驟子集，可遞推轉(zhuǎn)化為剩余資源與剩余步驟之間的*WS問題，且不同的遞推路徑可能產(chǎn)生重復(fù)子問題，從而導(dǎo)致動態(tài)規(guī)劃的求解方法。這兩條求解路線上，各有一些新的進(jìn)展。在動態(tài)規(guī)劃路線上，CRAMPTON等[6]基于Bjorclund求賦權(quán)集最大權(quán)劃分的方法對一系列*WS問題給出了具有優(yōu)化指數(shù)時間復(fù)雜度的算法。對于*WS(≠)問題，其時間復(fù)雜度為O*(2|S|(|X|+|U|2))(S、U、X分別為步驟、資源和互斥約束的集合)，O*表示法用來度量算法的主要開銷，設(shè)c為正常數(shù)，p(n)是關(guān)于n的多項式，則O(cnp(n))可表示為O*(cn),是目前最優(yōu)的理論結(jié)果。但該方法的空間復(fù)雜度為指數(shù)級，且實際空間占用極大，嚴(yán)重限制了求解規(guī)模和性能表現(xiàn)。COHEN等[7]通過識別互斥等一大類約束的資源獨立性特征，建立了資源分配的模式編碼技術(shù)，以此壓縮動態(tài)規(guī)劃緩存，得到了一種時間復(fù)雜度為O*(3|S|wlgw)的算法，其中w是資源的分散度。2016年，他們將該方法推廣到了資源獨立性計數(shù)約束下的*WS[8]問題。在解空間搜索路線上，KARAPETYAN等[9]利用模式編碼技術(shù)來壓縮解空間，提出了資源獨立約束*WS問題的模式回溯算法，其時間復(fù)雜度為O*(B|S|)，其中B|S|為第|S|個貝爾數(shù)，具有目前最好的實際性能。CRAMPTON等[10]將模式回溯法推廣到類別獨立約束中，給出了層次組織約束*WS問題的求解算法。除文獻(xiàn)[6]以外，上述研究均與模式編碼技術(shù)有關(guān)。

事實上，WS問題是約束可滿足問題(constraint satisfaction problem,CSP)的特殊情形，而模式編碼是一種CSP值對稱打破技術(shù)。模式回溯法不僅有前述的良好性能表現(xiàn)，而且推動了這一CSP問題技術(shù)領(lǐng)域的進(jìn)步。HENTENRYCK等[11]、RONEY-DOUGAL等[12]和FLENER等[13]先后對具有全局和逐塊值對稱的CSP問題進(jìn)行了研究，建立了以群等價樹(group equivalence-tree，GE-Tree)為核心的打破對稱技術(shù)。然而，上述研究對變量值域附加了相應(yīng)的限制，以聯(lián)合約束和值域特征，得到問題層面的對稱性。早在2006年，COHEN等[14]已經(jīng)從問題和約束兩個層面來區(qū)分CSP的對稱性概念。2014年，他們又通過WS問題對后一種對稱性進(jìn)行研究[7]，定義了資源獨立性約束的概念，并為問題的解建立了模式編碼表示，證明任意解與其模式在此類約束的驗證上是等價的。這一工作實際上是從約束而非問題層面來定義所謂全局值對稱性，從而有可能在不限制變量值域的情況下利用這一性質(zhì)。特別地，它為約束(而非問題)的對稱解建立了一種簡明的抽象機(jī)制，使模式解空間的定義成為可能。2015年，KARAPETYAN等[9]基于模式編碼給出了模式解空間的構(gòu)造方法，建立了資源獨立性約束WS問題的模式回溯法。模式解空間可以利用問題約束的資源獨立性快速構(gòu)造，而對變量值域沒有限制。模式回溯法通過授權(quán)匹配來驗證模式解的真實性，連同COHEN等關(guān)于解和模式約束驗證等價的結(jié)論，共同解決了在模式解空間上搜索真實可行解的問題，建立了一種新型的CSP全局值對稱打破技術(shù)。2016年，CRAMPTON等[10]將資源獨立性約束推廣為類獨立性約束，給出了組織機(jī)構(gòu)約束*WS問題的求解方法，實際上是將模式回溯法推廣到了多層嵌套的逐塊值對稱約束的可滿足問題?？梢姡訵S問題為應(yīng)用背景的模式編碼的相關(guān)研究，為CSP值對稱打破技術(shù)做出了重要貢獻(xiàn)。模式回溯法集中體現(xiàn)了有關(guān)進(jìn)展，是一種很有潛力的新型算法。

本文將以*WS(≠)問題為切入點來建立一種優(yōu)化的模式回溯算法。

1 *WS(≠)問題與模式回溯法

以下S表示工作流步驟集，U表示可用資源集，T表示S的子集。

定義1資源分配函數(shù)π:T→U，為T中每個步驟指派唯一的執(zhí)行資源。當(dāng)T=S時，稱π為完全資源分配；當(dāng)T=?時，稱π為空資源分配。所有資源分配的集合記為Π。

定義2訪問控制策略是一個四元組〈S,U,A,C〉，其中：

(1)授權(quán)A={UA(s)|s∈S}，這里UA(s)是步驟s的授權(quán)列表，而u∈UA(s)是s的候選執(zhí)行資源。由此定義資源u的授權(quán)步驟集SA(u)={s∈S|u∈UA(s)}。對于一個資源分配π:T→U，若任取s∈T，均有π(s)∈UA(s)，則稱π滿足授權(quán)。

(2)C是約束的集合。每個約束c=〈T,Θ〉，其中T?S是受c約束的步驟集，而Θ?Π表示滿足該約束的所有資源分配：任取θ∈Θ，其定義域均包含T，且其為T中各步驟分配的資源滿足約束c的要求。若T={s,s′}，而Θ={θ|θ(s)≠θ(s′)}，則稱c為互斥約束。

若一個完全資源分配滿足C中所有約束和授權(quán)A，則稱其是該訪問控制策略的可行解。

定義3互斥約束工作流可滿足決策問題*WS(≠)定義為訪問控制策略〈S,U,A,X〉，目標(biāo)是求任意一個可行解。其中，X是互斥約束的集合。

定義4[7]約束c=〈T,Θ〉具有資源獨立性，是指任取θ∈Θ和置換φ:U→U，必有φ°θ∈Θ。實際上，{θ-1(u)∩T|u∈U}構(gòu)成了T的一個劃分，φ°θ屬于Θ或滿足c，這是因為其可以保持每個劃分塊中的步驟都分配同一資源，且不同劃分塊分配不同資源。這就是說，c只限制T中各步驟所分配資源的組合方式，而不限制每個步驟具體分配哪個資源。例如互斥約束c=〈{s,s′},Θ〉，Θ={θ|θ(s′)≠θ(s″)}，對于φ:U→U，必有φ°θ(s′)=φ(θ(s′))≠φ(θ(s″))=φ°θ(s″)，故也有φ°θ∈Θ，滿足資源獨立性要求，因為c只要求s和s′分配的資源不同，而不限制是怎樣兩個不同的資源。

定義5[7,9]資源分配π:T→U的模式p定義為二元組〈T,{x1,…,x|S|}〉，它為每個步驟si分配一個編碼xi，使得：

(1)

若p是π的模式，也稱π符合p。xi≡0的模式稱為空模式。模式的編碼序列x1,…,x|S|確定了一個S→{0,1,…,min(|S|,|U|)}函數(shù)，且在該序列的非0編碼中，較小編碼的首次出現(xiàn)先于較大編碼的首次出現(xiàn)。

直觀上，將π中使用的不同資源，從1開始重新編號，就可得到π的模式p。盡管π為各步驟所分配資源之間的關(guān)系，在p中變成了相應(yīng)編碼之間的關(guān)系，但其組合方式?jīng)]有任何改變。因此，一個很自然的結(jié)論是：π滿足一個資源獨立性約束，當(dāng)且僅當(dāng)p滿足這一約束。例如U={ui|1≤i≤7},S={si|1≤i≤6},T={s1，s3，s4，s6，s7},若π:T→U使得π(s1)=u3、π(s3)=u6、π(s4)=u1、π(s6)=u6、π(s7)=u3，則其模式p為〈T,{1，0，2，3，0，2，1}〉。π滿足s1和s3之間的互斥約束，當(dāng)且僅當(dāng)p滿足這一約束。事實上，對于任意的資源獨立性約束集C，在資源分配集Π上存在等價關(guān)系“≈”，使得任取π∈Π，[π]≈中所有資源分配有相同的模式，且π滿足C當(dāng)且僅當(dāng)π的模式滿足C[7]。

為求訪問控制策略的一個可行解，可在解空間樹上回溯搜索。每個資源分配都對應(yīng)一個樹節(jié)點，當(dāng)搜索到該節(jié)點時，須驗證其是否滿足約束。在資源獨立性約束下，對資源分配與模式的約束驗證相互等價，而模式數(shù)量小得多，因此有可能通過構(gòu)造某種模式解空間來加快搜索。文獻(xiàn)[9]的模式回溯算法隱式給出了模式解空間的結(jié)構(gòu)：它是一棵根樹；每個節(jié)點對應(yīng)一個(步驟，編碼)對；從根到葉的每條路徑都不重復(fù)地包含S中所有步驟；根節(jié)點的編碼為1；每組兄弟節(jié)點的編碼分別為1,2,…,mx+1，其中mx是父節(jié)點到根的路徑上的最大編碼。由于每個節(jié)點唯一對應(yīng)于從根到該節(jié)點的路徑，且在該路徑上，較小編碼的首次出現(xiàn)早于較大編碼的首次出現(xiàn)，故每個節(jié)點都表示一個可能的模式，不妨記為p。只要所用編碼數(shù)(顯然不超過|S|)不超過|U|，p必然構(gòu)成某組資源分配Πp的模式。通常的解空間中，每個節(jié)點代表的資源分配都必然符合授權(quán)，這是因為每個步驟的授權(quán)資源集是預(yù)先確定的，在形成解空間時即可滿足授權(quán)要求。然而，模式將抽象的編碼而非真實的資源賦給步驟，在形成模式解空間時無法兼顧授權(quán)要求。這就給上述回溯搜索帶來了新的問題。

如前所述，對模式p=〈T,{x1,…,x|S|}〉進(jìn)行約束驗證即可判斷任何π∈Πp是否滿足約束。我們將這種約束驗證記為C。但是，符合模式p的資源分配不一定滿足授權(quán)。為了判斷是否存在某個π0∈Πp滿足授權(quán)要求，模式回溯算法給出了驗證的方法：設(shè)p的非0編碼集為I，首先計算I與U之間的授權(quán)二分圖B(任取x∈I和u∈U，若{s∈T|p(s)=x}?SA(u)，則(x,u)是B中的邊)，然后在B上用匈牙利算法[15]求I的完全匹配，即一個單射函數(shù)m:I→U。若能求得m，則m°p∈Πp且滿足授權(quán)要求，否則，Πp中沒有滿足授權(quán)的資源分配。我們將這種驗證稱為(編碼集與資源集的)授權(quán)匹配驗證，記為M。模式回溯算法中還使用了M的一個必要性驗證：設(shè)表示模式p的節(jié)點對應(yīng)(步驟，編碼)對(s,x)，判斷是否存在u∈U，使得{s∈T|p(s)=x}?SA(u)，即x在按前述方式計算的授權(quán)二分圖中是否有鄰點。若無，則p不可能通過驗證M。我們將這一驗證稱為(單個)編碼的授權(quán)真實性驗證，記為A。

在回溯搜索中，如何處理剪枝能力與驗證代價的關(guān)系有重要意義[16]，模式回溯法也不例外。文獻(xiàn)[9]和文獻(xiàn)[10]均只在搜索到葉節(jié)點時執(zhí)行驗證M，而當(dāng)搜索非葉節(jié)點時，則以其必要性驗證A代替。也就是說，僅當(dāng)找到一個完整的模式解，需要計算真實可行解的時候，才去執(zhí)行一次耗時的匹配驗證。這樣做降低了單個搜索節(jié)點上的驗證代價，并可以保證一定的剪枝能力。而本文將利用實例難度的分布特點表明，這種處理方法在宏觀上并不是最優(yōu)的。

2 *WS(≠)的匹配剪枝模式回溯算法

由于互斥約束有資源獨立性，故*WS(≠)問題可用模式回溯法求解。本節(jié)首先給出一種改進(jìn)的模式回溯算法，其特點是在每個搜索節(jié)點處執(zhí)行匹配驗證M，以充分發(fā)揮其剪枝能力，故稱為匹配剪枝模式回溯(MPB)算法；然后，將對其性能與代價的關(guān)系進(jìn)行分析研究。算法描述如下。

算法1MPB (s，p，v) //Match-Pruning Pattern Backtracking

輸入：s表示待分配編碼的當(dāng)前步驟，p表示之前各步驟的編碼分配模式(未分配編碼的步驟，其p值為0)，v將p中的編碼映射為相應(yīng)的步驟集

輸出：S的資源分配可行解π， 或NULL(表示無解)

1.mx←{0,max(p(j)|1≤j

2.for (1≤x≤max(mx+1,|U|)) //嘗試已使用的所有編碼和下一個新編碼，但編碼數(shù)不能超過資源數(shù)

3.p(s)←x;

4.v′←v; //為下一級調(diào)用計算新的v

5.v′(x)←v′(x)∪{s};

6. if (存在{s′,s″}∈X使得p(s′)=p(s″)) continue; //驗證C失敗，跳過當(dāng)前編碼，嘗試下一個

7.i←s; //從當(dāng)前步驟開始，對已分配編碼的所有步驟循環(huán)

8. while (i≥1) //循環(huán)計算編碼-資源二分圖bp，bp(x)表示其授權(quán)步驟集可覆蓋v′(x)的所有資源

9. if (bp(p(i))≠?) continue; //bp(p(i))已計算，跳過當(dāng)前x

10. for (u∈U∧v′(p(i))?SA(u))bp(p(i))←bp(i)∪{u}; //SA(u)是資源u的授權(quán)步驟集

11. if (bp(p(i))=?) break; //編碼p(i)在二分圖中無鄰點，驗證A失敗

12.i←i-1;

13. end while

14. if (i=s) continue; //為步驟s分配編碼x導(dǎo)致驗證A失敗，跳過當(dāng)前編碼，嘗試下一個

15. 求二分圖bp的完全匹配m; //根據(jù)m可將編碼映射為匹配資源

16. if (m不存在) continue; //無匹配，驗證M失敗，跳過當(dāng)前編碼，嘗試下一個

17. if (s=|S|) returnm°p; //p通過3種驗證，且為完整模式解，其所匹配的真實解即為所求可行解

18.π′←MPB(s+1,p,v′); //p通過3種驗證，但不是完整模式，繼續(xù)深度優(yōu)先搜索

19. if (π′≠NULL) returnπ′;//遞歸調(diào)用得到了可行解，將其返回即可

20.end for

21.p(s)←0; //清除嘗試賦值的痕跡

22.return NULL;

令初始調(diào)用為MPB (1,p:S→{0},v:{1,…,|U|}→{?})，即可求解*WS(≠)問題〈S,U,A,X〉，其中p:S→{0}給每個步驟賦值為0，v:{1,…,|U|}→{?}給每個資源賦值為?。由于在最壞情況下，算法可能遍歷模式解空間，故其時間復(fù)雜度為O*(B|S|)。

相對于現(xiàn)有模式回溯法(記為PB)，MPB算法的主要改變是在非葉節(jié)點處增加了第15～16行的授權(quán)匹配驗證M，以及第7～14行的授權(quán)二分圖計算，均屬于驗證M的內(nèi)容。其中第7行從當(dāng)前步驟s開始循環(huán)，將首先計算當(dāng)前編碼x在二分圖中的鄰點，這正是驗證A的內(nèi)容。若該驗證不通過，第11行將跳出循環(huán)，不會執(zhí)行剩余的二分圖計算過程，緊跟著第14行會檢測到這一情況，也不會執(zhí)行求匹配的代碼。簡單來說，PB算法在每個搜索節(jié)點處進(jìn)行組合驗證V=C+A，而MPB算法在其后附加了驗證M。上述算法設(shè)計的變化并不大，但會帶來很有意義的性能提升。分析如下。

回溯法的性能由搜索節(jié)點數(shù)量和節(jié)點驗證代價共同決定。MPB算法在每個搜索節(jié)點處引入匹配驗證M，其目的是加強(qiáng)剪枝，盡量避免dead-end現(xiàn)象，即搜索到葉子或接近葉端的位置才發(fā)現(xiàn)當(dāng)前解不可行，從而減少搜索節(jié)點的數(shù)量，避免相應(yīng)的驗證代價。然而，引入M也會增加單個節(jié)點的驗證代價，這可以根據(jù)3種驗證的時間復(fù)雜度進(jìn)行比較。設(shè)每個節(jié)點n對應(yīng)步驟-編碼賦值(s,x)，驗證C只檢查步驟s所參與的互斥約束，至多|S|個，而每一約束只需常數(shù)時間，故時間復(fù)雜度為O(|S|)。驗證A判斷編碼x是否對應(yīng)某個授權(quán)資源u，而x至多賦給|S|個步驟，需要逐一檢查這些步驟和每個資源之間的授權(quán)關(guān)系。通過預(yù)先計算所有資源和步驟之間的授權(quán)關(guān)系矩陣，驗證A可在O(|U||S|)時間內(nèi)完成，因此，驗證V=C+A的時間復(fù)雜度為O(|U||S|)。相對而言，驗證M所需時間代價較大，完整計算授權(quán)二分圖相當(dāng)于執(zhí)行O(|S|)次驗證A，需要O(|U||S|2)時間，若與文獻(xiàn)[9-10]保持一致，采用匈牙利算法求匹配，則其時間復(fù)雜度也是O(|U||S|2)，故驗證V+M的總代價為O(|U||S|2)。于是，MPB算法在非葉節(jié)點處的驗證代價較PB算法高出一個O(|S|)因子?？傮w上，PB算法和MPB算法的執(zhí)行代價之比可表示為

(2)

其中,#SNodes(PB)和#SNodes(MPB)分別是PB算法和MPB算法所搜索驗證的節(jié)點總數(shù)，Cost(V)是PB算法在單個非葉節(jié)點上的驗證代價，Cost(V+M)是MPB算法每個節(jié)點上的驗證代價，#FLeaves(PB)表示PB算法因M驗證失敗而剪枝的葉節(jié)點數(shù)目，包含于#SNodes(PB)，但需要額外的Cost(M)代價。MPB算法相對于PB算法的改進(jìn)目標(biāo)是使式(2)的比值盡可能大。改進(jìn)前，對于#SNodes(PB)-#FLeaves(PB)中的節(jié)點，驗證代價為Cost(V)，而對于#FLeaves(PB)中的節(jié)點，驗證代價為Cost(V+M)。改進(jìn)后，對于#SNodes(MPB)中的節(jié)點，驗證代價均為Cost(V+M)。Cost(V+M)>Cost(V)會減小式(2)的R值，如前述，Cost(V+M)比Cost(V)高出一個線性因子，這是其縮減作用的上限，當(dāng)#FLeaves(PB)在#SNodes(PB)中所占比例較小時，會更接近這一上限。同時，V+M的剪枝能力強(qiáng)于V，原來的每次剪枝，改進(jìn)后將發(fā)生在同樣或更靠根的位置，必有#SNodes(MPB)≤#SNodes(PB)，這將會增大式(2)的R值，但其作用強(qiáng)度很難估計，也缺乏合理的假設(shè)。本文將根據(jù)問題實例的難度分化情況，給出進(jìn)一步的分析。

已有研究指出，回溯法求解CSP問題時存在相變因素，導(dǎo)致性能兩極分化[17-18]。對于現(xiàn)有模式回溯法PB，我們也觀察到了類似現(xiàn)象，即其在多數(shù)實例上表現(xiàn)良好，但時有性能惡化的情況出現(xiàn)。對于這兩種情況，給出如下的分析。

2.1 PB性能惡化

PB性能惡化時將會伴隨著比較嚴(yán)重的dead-end現(xiàn)象，即很多葉節(jié)點不能導(dǎo)致真實可行解而被剪枝，從而增大#FLeaves(PB)在#SNodes(PB)中的比例?；蛟诟话闱闆r下，該比例不一定很大，但必然有大量剪枝點出現(xiàn)在接近葉端的位置，此時，任何新的剪枝能力對避免性能惡化都是非常重要的。特別地，大量剪枝點出現(xiàn)在近葉的位置，從根到剪枝點的路徑很長，這就增加了新驗證M在中間節(jié)點處提前剪枝的可能。而對原來比較靠近根端的剪枝點，引入M后至少可在同樣位置完成剪枝?？傮w上，平均剪枝高度明顯降低的可能性會比較大。對于正則的模式回溯解空間樹(所有葉節(jié)點的高度相等)，根據(jù)貝爾數(shù)的增長規(guī)律，當(dāng)初始高度大于4時，樹高每降低1層，所包含節(jié)點的數(shù)目減少2/3以上，且初始高度越大，降低1層后節(jié)點的減少比例越大。因此，模式回溯的搜索節(jié)點數(shù)量隨剪枝高度降低，且至少按3k指數(shù)速度減少。如果M能額外提供一定剪枝能力，則可有效增大#SNodes(PB)/#SNodes(MPB)，且比較容易抵消Cost(V+M)/Cost(V)的線性因子縮減作用，使式(2)取很大的R值，從而改善模式回溯法在困難實例上的性能表現(xiàn)。

2.2 PB性能良好

PB性能良好時，若非問題實例的規(guī)模非常小，或者第一個真實模式解對應(yīng)的葉節(jié)點恰巧出現(xiàn)在深度優(yōu)先序列靠近開始的位置，則表明驗證V的剪枝能力已經(jīng)很強(qiáng)，剪枝高度已經(jīng)較低。相應(yīng)地，被剪枝的模式部分解所用編碼數(shù)量也不多，為其進(jìn)行完全匹配的難度較低，比較容易通過驗證M。此時，M額外引入的剪枝能力有限，但卻增加了搜索節(jié)點上的驗證代價，容易引起整體性能下降。在最不利的情況下，M相對于V并未增加任何剪枝能力，引入M前后搜索節(jié)點的數(shù)量完全相同。此時，搜索代價完全取決于單節(jié)點驗證開銷，如前所述，MPB算法較PB算法高出一個O(|S|)因子。當(dāng)PB性能良好時，由此導(dǎo)致的絕對性能差距也不大。而由于如下原因，兩者的相對和絕對性能差距還會進(jìn)一步減?。?/p>

(1)由于PB算法有效的剪枝能力，剪枝點的高度h往往會明顯小于|S|，而任意搜索節(jié)點n的高度h會更小。設(shè)n=(s,x)，即在該節(jié)點處編碼x被賦給步驟s，那么，驗證C只需檢查s與當(dāng)前已賦值步驟之間的約束，其數(shù)量為O(h)，驗證A可在O(|U|h)時間內(nèi)完成，而驗證M可在O(|U|h2)時間內(nèi)完成。MPB算法在非剪枝的搜索節(jié)點處需要進(jìn)行V+M驗證，但相對于PB算法的V=C+A驗證，其代價只高出一個O(h)而非O(|S|)因子，兩者的相對性能差距也會比之前的分析更小。

(2) 由于所有剪枝點構(gòu)成了搜索范圍的下邊緣，根據(jù)模式解空間隨樹高的擴(kuò)張速度可以判斷，PB算法的剪枝點在所有搜索節(jié)點中占據(jù)了可觀的比例。這些剪枝點都不能通過驗證V，本文MPB算法按照先V后M的順序進(jìn)行驗證，在這些節(jié)點處沒有額外代價。相對于之前較為粗略的分析，這一因素進(jìn)一步限制了兩種算法的絕對性能差距。

由上述分析可以預(yù)期：相對于PB算法，MPB算法在容易的*WS(≠)實例上不會有多大劣勢(至多高出一個O(h)因子，且兩者的絕對性能差距不大)，而在困難實例上會取得比較明顯的優(yōu)勢。

3 實驗研究

現(xiàn)有算法中，文獻(xiàn)[6]算法(記為Cr13)具有最低的時間復(fù)雜度，是一種基于容斥原理的動態(tài)規(guī)劃算法，而文獻(xiàn)[7]算法(記為Co14)代表了基于模式的動態(tài)規(guī)劃算法，文獻(xiàn)[9]算法(記為PB)具有最好的實測時間性能，代表了現(xiàn)有的模式回溯方法。本實驗將MPB算法與這3種算法，特別是PB算法，進(jìn)行性能對比，驗證模式回溯法和增強(qiáng)匹配策略的優(yōu)勢。MPB算法和PB算法均根據(jù)步驟參與的互斥約束數(shù)量對其進(jìn)行降序排列，并采用匈牙利算法計算匹配。

在二元隨機(jī)CSP問題的標(biāo)準(zhǔn)模型中，采用變量個數(shù)、值域大小、約束密度和約束緊度4個參數(shù)控制實例生成，其約束類型不確定，且每個變量都取整個值域。對于僅含互斥約束且變量值域存在差異的*WS(≠)問題，約束緊度(違反約束的元組數(shù)與該約束值域中所有可能的元組數(shù)的比值)取決于兩個約束變量的值域，不必單獨控制，且生成模型中需要增加反映變量值域差異的參數(shù)。因此，本文通過以下幾個參數(shù)控制實例生成：

步驟集規(guī)模|S|、資源比例μ=|U|/|S|(取資源集規(guī)模|U|=|S|μ)、約束密度ω=2|X|/[|S|(|S|-1)](以概率ω決定在每一對步驟之間是否生成約束)、每個步驟s的授權(quán)比例ks=UA(s)/|U|(從U中隨機(jī)取|U|ks個資源作為s的授權(quán)資源集UA(s))。

每個實例的參數(shù)取值規(guī)則如下：

(1)在[s,S](此處S和s只是大小兩個整數(shù)，不表示步驟集和步驟)范圍內(nèi)隨機(jī)生成|S|。步驟數(shù)反映了WS問題的基礎(chǔ)規(guī)模。通常，取S=100即可覆蓋大多數(shù)工作流的規(guī)模，且該范圍的變化已經(jīng)可以導(dǎo)致模式解空間的膨脹，為生成難實例提供了必要條件。

(2)在[u,U]范圍內(nèi)隨機(jī)生成資源比例分子μ，取[u,U]=[50,200]以反映資源供應(yīng)從相對短缺到比較充分之間的各種情況。

(3)在[w,W]范圍內(nèi)隨機(jī)生成約束密度分子ω，由于互斥約束用于表達(dá)安全攸關(guān)的業(yè)務(wù)規(guī)則，故其密度通常不會太高。在本文實驗中，將統(tǒng)一取[w,W]=[10,25]。

(4) 對于每個步驟s，在[k,K]范圍內(nèi)隨機(jī)生成ks。當(dāng)所有步驟的ks均為100%時，每個資源都可以執(zhí)行每個步驟，只要模式部分解所用編碼數(shù)不超過|U|，就一定對應(yīng)某個真實部分解。特別地，當(dāng)μ≥1時，任何模式部分解所用編碼數(shù)都不超過|U|，故其一定具有真實性，不需要進(jìn)行授權(quán)相關(guān)驗證。以上是一種簡化的理想情況。在實際應(yīng)用中，不同的步驟需要不同的業(yè)務(wù)技能，其授權(quán)資源集通常存在差別。對于同一個編碼賦給的若干步驟來說，其授權(quán)資源存在交集的可能性被降低了，這就為匹配驗證的剪枝作用提供了基礎(chǔ)。我們將根據(jù)隨后實驗的目的對[k,K]進(jìn)行設(shè)置。

3.1 4種*WS(≠)算法的性能對比實驗(實驗1)

按上述規(guī)則隨機(jī)生成500個實例，未確定參數(shù)的取值為[s,S]=[5,35],由于各對比算法的性能水平不盡相同，故首先取較小規(guī)模的工作流進(jìn)行實驗，對于表現(xiàn)突出的算法再擴(kuò)大規(guī)模進(jìn)行測試；隨機(jī)取[k,K]= [1,4]、 [10,35]、[40,65]、[70,95]或[5,100]，分別反映授權(quán)比例很低、較低、中等、偏高或大范圍波動的情況。

設(shè)置時間上限為6 min，在500個實例上執(zhí)行4種對比算法，結(jié)果如下。

兩個動態(tài)規(guī)劃算法中，Cr13和Co14分別解出了133和122個實例，最大求解規(guī)模分別是15和17個步驟，大體相當(dāng)。在解出實例上的平均執(zhí)行時間方面，Cr13為14.95 s，Co14為23.80 s，前者有一定的優(yōu)勢。在解出實例上的平均占用空間方面，Cr13為541 MB，Co14為14 MB。在失敗實例當(dāng)中，Cr13除22個超時外，其余均為內(nèi)存超限，而Co14均為超時失敗。這表明前者的空間占用處于劣勢。從理論最壞情況來說，Cr13和Co14的空間復(fù)雜度分別為O*(|U|2|S|)和O*(B|S|)，前者低于后者。但兩者的空間利用方式顯著不同，Cr13有保存權(quán)函數(shù)和計算快速zeta變換兩個環(huán)節(jié)，均需一次性分配O*(2|S|)空間，而Co14隨著自底向上動態(tài)規(guī)劃，逐漸緩存新出現(xiàn)的模式部分解，這就使其空間代價的增長實際上比Cr13慢得多。

兩個模式回溯算法中，PB解出了493個實例，而MPB解出了全部實例，略有優(yōu)勢。兩者可求解的最大規(guī)模均為35個步驟。在解出實例上的平均執(zhí)行時間上， PB為0.83 s，MPB為0.33 ms，有明顯優(yōu)勢。在解出實例上的平均占用空間上，PB和MPB均為13 MB。較之兩種動態(tài)規(guī)劃算法，PB和MPB在求解率、最大求解規(guī)模、平均時間和空間占用上都有極大優(yōu)勢，驗證了模式回溯算法的優(yōu)越性。為了解平均時間性能差異背后的具體分布，將PB和MPB在493個共同解出實例上的執(zhí)行時間逐對成點，得到圖1所示的散點圖。由圖1可知，PB對大部分實例的處理都在300 μs以內(nèi)，但其余實例的執(zhí)行時間發(fā)生了數(shù)倍到成百萬倍的跳躍，這就導(dǎo)致平均執(zhí)行時間大大增加。而MPB的執(zhí)行時間基本上在2 ms以內(nèi)，且以相當(dāng)連續(xù)的方式變化，因此平均時間也在同一量級。

圖1 實驗1中MPB與PB執(zhí)行時間的逐點對比Fig.1 Pointwise comparison between the running time of MPB and PB in experiment 1

逐點對比兩種算法。y=x斜線上方是PB較MPB優(yōu)勢的實例，其數(shù)量很多(404個)，但是縱橫坐標(biāo)之比(MPB/PB)不大，平均為1.96，縱橫坐標(biāo)之差(MPB-PB)的平均值僅為159.49 μs，說明PB的相對優(yōu)勢不大，而絕對優(yōu)勢非常小；斜線及其下方是MPB較PB有更大或同等優(yōu)勢的實例，其數(shù)量相當(dāng)少(89個)，但是橫縱坐標(biāo)之比(PB/MPB)很大，平均為28 585.89。這表明PB在大量實例上有較小的優(yōu)勢，而MPB在少數(shù)實例上取得了很大的優(yōu)勢。此外，還有7個實例PB的執(zhí)行時間超過360 s，而MPB處理它們僅需0.149～0.455 ms，平均為0.29 ms，甚至低于MPB在所有實例上的平均時間。綜合上述結(jié)果可知，在PB性能相對惡化的實例上，MPB均取得了顯著的優(yōu)化效果。而在那些PB表現(xiàn)良好的實例上，MPB同樣有不錯的表現(xiàn)，與PB的絕對和相對性能差距都不大，這與之前的分析結(jié)果一致。

以上對少量步驟的情形進(jìn)行實驗，表明MPB性能的提高主要發(fā)生在PB性能惡化的實例上。接下來，我們將通過更大范圍的實驗來確定此類實例的出現(xiàn)條件，進(jìn)一步驗證本文算法的優(yōu)勢，并通過剪枝能力相關(guān)指標(biāo)的測量，進(jìn)一步揭示其原因。如前所述，問題實例的約束密度處于較低的范圍內(nèi)，我們將通過改變授權(quán)比例來尋找現(xiàn)有模式回溯法的難解實例。

3.2 MPB與PB的進(jìn)一步對比實驗(實驗2)

將步驟數(shù)的范圍擴(kuò)大到[s,S]=[10,100]，在不同波動幅度(100/3，100/5)下，令(k+K)/2等距(17±1)變化，分別生成一組實例。其中第1組[k,K]=[1,33]、 [17,49]、[34,66]、[50,82]和[68,100]，第2組[k,K]=[8,27]、[24,43]、[41,60]、[57,76]和[75,94]。每個[k,K]為1個單元，按前述單實例規(guī)則生成50個實例，每組包含5單元共250個實例。在兩組實例上以6 min為限運行PB和MPB，統(tǒng)計結(jié)果見表1和表2。其中，avg(G)表示算法G在若干實例(通常是一單元中某一類別的實例)上的平均執(zhí)行時間，剪枝高度均值(G)表示算法G在若干實例上產(chǎn)生的所有剪枝點(到實例結(jié)束或超時為止)的平均高度(剪枝點到根的距離稱為其高度)，搜索節(jié)點數(shù)均值(G)表示算法G在若干實例上的搜索節(jié)點數(shù)(一個實例執(zhí)行結(jié)束或到其超時為止，執(zhí)行過搜索驗證的節(jié)點總數(shù))的平均值，Diff表示PB超時而MPB未超時的實例集。

表1 實驗2第1組實例結(jié)果統(tǒng)計

表2 實驗2第2組實例結(jié)果統(tǒng)計

(續(xù)表)

類別編號[k,K][8,27][24,43][41,60][57,76][75,94]MPB優(yōu)勢的共同解出實例8數(shù)量110319avg(PB)(μs)2603.58×1069.41×10610810avg(MPB) (μs)19714424210611avg(PB)/avg(MPB)1.3224 90038 9001.0212avg(PB)-avg(MPB) (μs)633.58×1069.41×106213剪枝高度均值(PB)19.6920.8735.0815.7714剪枝高度均值比(MPB)15.0112.3624.4215.7715搜索節(jié)點數(shù)均值(PB)1781.55×1062.96×1065416搜索節(jié)點數(shù)均值(MPB)915499.3354PB優(yōu)勢的共同解出實例17數(shù)量444648444918avg(MPB)(μs)1 384.86887.239651.396637.386430.26519avg(PB)(μs)361.477285.739238.333248.023197.18420avg(MPB)/avg(PB)3.833.112.732.572.1821avg(MPB)-avg(PB) (μs)1 175.77601.5413.063389.363233.08122剪枝高度均值(MPB)34.1434.0830.3332.9929.7123剪枝高度均值(PB)34.1434.0830.3332.9929.7124搜索節(jié)點數(shù)均值(MPB)318.75226.18164.5158.36146.0625搜索節(jié)點數(shù)均值(PB)318.75226.18164.5158.36146.06

由表1、表2的1～3行可以看出，PB出現(xiàn)了數(shù)量不等的超時實例，而MPB大部分沒有超時。在PB超時而自身未超時的實例上，MPB平均執(zhí)行時間均未超過2 ms，性能優(yōu)勢非常顯著。由4～7行可知，MPB通過額外的匹配驗證，將剪枝高度平均降低了27.95，這導(dǎo)致其搜索節(jié)點數(shù)大幅度減少，降低了5～6個數(shù)量級。MPB的搜索節(jié)點數(shù)平均僅有幾百個，遠(yuǎn)低于其剪枝高度(40左右)相應(yīng)的貝爾數(shù)部分和，這主要是因為采用了剪枝點高度均值這一指標(biāo)，而不是嚴(yán)格意義上的平均剪枝高度(對于每個實例，將其搜索節(jié)點數(shù)從根開始以寬度優(yōu)先方式排列在解空間樹中，計算下邊緣的高度)。在形態(tài)上，前者可能導(dǎo)致從根開始的一叢分散的枝條，其平均長度較大，但枝條上的節(jié)點相對較少，而后者得到從根開始排列緊密的三角形，其高度不大，但包含了大量節(jié)點。若固定搜索節(jié)點的數(shù)量，則前者以后者為下界。事實上，PB在這些實例上的剪枝高度均值都已接近解空間樹的高度，兩個指標(biāo)區(qū)別不大。若對MPB也采用后一指標(biāo)，則相對于PB的降低程度會更大。另外，PB在大量葉節(jié)點處發(fā)生匹配失敗，統(tǒng)計其MatchFailedLeafCount(V)達(dá)到SearchNodeCount(V)的同等或1/10量級，這種情況屬于典型的“dead-end”。兩種算法對比可知，僅僅采用V=C+A驗證，在此類實例上遠(yuǎn)不能實現(xiàn)有效剪枝，而增加M驗證可明顯增強(qiáng)模式回溯法的剪枝能力。就PB超時實例的分布而言，當(dāng)(k+K)/2從較小的值開始增加時，大體呈減少的趨勢，這是因為授權(quán)比例增加對模式解空間大小沒有影響，但卻可以導(dǎo)致真實模式解數(shù)量的增加，使得第一個解在搜索序列中的出現(xiàn)位置提前，從而更容易被搜索到。隨著授權(quán)比例的增加，MPB的超時實例數(shù)量變化不太明顯，但其僅有的2個超時實例也出現(xiàn)在授權(quán)比例最低的區(qū)間。從表1、表2的第3行來看，在授權(quán)比例較低的解出實例上，MPB消耗的時間也較多?？偟膩碚f，PB在較低的授權(quán)比例下更容易出現(xiàn)超時，而MPB可以有效改善這種情況，但其性能在較低的授權(quán)比例下也較差。

由表1、表2的8～12行可以看出，MPB優(yōu)勢的共同解出實例很少，平均每單元(50個實例)不到2個，但MPB的優(yōu)勢很大。除2個執(zhí)行時間極為接近的實例(此時算法優(yōu)勢有一定偶然性)外，至少將性能提高到26.5倍，最多達(dá)到45萬倍，絕對性能差距則在2.5 ms～700 s之間，優(yōu)化效果也比較明顯。從13～16行的回溯剪枝指標(biāo)來看，MPB將剪枝高度平均降低了5.97(除去執(zhí)行時間幾乎相等的情況)，相應(yīng)將搜索節(jié)點數(shù)降低了1～5個數(shù)量級。由此可見，剪枝高度平均值的較少降低，已經(jīng)可以引起搜索節(jié)點數(shù)的大幅度減少。在PB性能相對惡化的實例上，MPB已經(jīng)可以取得很大優(yōu)勢。

觀察表1、表2第17～25行的數(shù)據(jù)可知，PB優(yōu)勢的共同解出實例很多，平均每單元45個左右。有些意外的是，在絕大部分情況下，MPB和PB的剪枝高度和搜索節(jié)點數(shù)平均值都相同。這說明對較為容易的實例，PB所使用的V=C+A驗證與V+M驗證往往是等效的。對本文算法來說，相當(dāng)于最不利的情況普遍發(fā)生了。即便如此，PB的性能優(yōu)勢最多只達(dá)到步驟集規(guī)模(10～100，中位值55)的1/10，而非線性比例，且絕對性能優(yōu)勢均在1.2 ms以內(nèi)，均與我們之前的分析一致。

上述兩組實例的[k,K]波動幅度較大，導(dǎo)致其中位值起點較高。為了考查更小的授權(quán)比例，取小的波動幅度(5，3)，令(k+K)/2等距(20)變化，生成3、4兩組實例進(jìn)行擴(kuò)展測試。每組實例包含3個單元，其中第3組[k,K]=[1,5]、 [21,25]、[41,45]，第4組[k,K]=[2,4]、[22,24]、[42,44]，其他參數(shù)與之前的設(shè)置相同。在兩組實例上以6 min為限運行PB和MPB，統(tǒng)計結(jié)果見表3。

表3 實驗2第3、4組實例結(jié)果統(tǒng)計

由表3的1～3行可見，PB的超時實例數(shù)隨著(k+K)/2的減小而增多，MPB的超時實例數(shù)明顯小于PB，且在PB超時而MPB未超時的實例上，MPB的平均執(zhí)行時間不超過45.4 s。由4～8行可見，MPB占優(yōu)勢的共同解出實例仍然不多，且MPB取得的性能優(yōu)勢是相當(dāng)顯著的(忽略2個執(zhí)行時間幾乎相等的實例)，至少為81.5倍，最高可達(dá)10 800倍。由9～13行可見，PB占優(yōu)勢的共同解出實例很多，但PB的性能優(yōu)勢不超過MPB的9.67倍，而其絕對性能優(yōu)勢不超過5 ms，同樣是非常微弱的。上述結(jié)果的變化規(guī)律與前兩組實例基本一致。值得注意之處在于，對于[k,K]=[1,5]、[2,4]兩個單元，PB的超時實例數(shù)和MPB優(yōu)勢的共同解出實例出現(xiàn)了明顯提升，表明在低約束密度下足夠小的授權(quán)比例可以導(dǎo)致真實模式解的數(shù)量急劇減小，使PB難解實例的數(shù)量顯著增加。

4 結(jié)語

本文從互斥約束工作流可滿足決策問題(即*WS(≠)問題)出發(fā)，針對現(xiàn)有模式回溯算法的缺陷進(jìn)行改進(jìn)，通過擴(kuò)大授權(quán)匹配驗證的作用范圍來增強(qiáng)其剪枝能力，并對其驗證代價的負(fù)面影響進(jìn)行考查。分析和實驗表明，現(xiàn)有模式回溯法的實例性能存在比較明顯的兩極分化現(xiàn)象:在性能惡化實例上，匹配驗證可以顯著增強(qiáng)剪枝能力，極大提高搜索性能；而在性能良好的實例上，盡管驗證代價的負(fù)作用更為突出，但造成的絕對性能下降幾乎可以忽略。在工作流環(huán)境約束密度較低的前提下，實驗還表明：當(dāng)授權(quán)比例較低時，更容易發(fā)揮本文方法的優(yōu)勢。

下一步將對特定約束的*WS隨機(jī)實例生成模型和解的分布規(guī)律進(jìn)行研究，用以改進(jìn)其求解效率。