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

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

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

0 引言

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

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

*WS尋求同時滿足給定約束和授權規劃的任意一個資源分配，可驗證授權規劃的可行性，為業務的安全執行提供必要的保證。互斥是一種應用廣泛的二元職責分離約束，相應的*WS問題記為*WS(≠)，有非常重要的意義。該問題是NP完全的[5]，對于該問題，確定性算法對中小規模實例有不錯的效果，并可以保證完備性(問題無解時能夠正確識別)，本文將進一步研究其性能優化問題，以推動相關求解技術的進步。

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

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

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

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

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

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

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

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

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

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

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

定義4[7]約束c=〈T,Θ〉具有資源獨立性，是指任取θ∈Θ和置換φ:U→U，必有φ°θ∈Θ。實際上，{θ-1(u)∩T|u∈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|)}函數，且在該序列的非0編碼中，較小編碼的首次出現先于較大編碼的首次出現。

直觀上，將π中使用的不同資源，從1開始重新編號，就可得到π的模式p。盡管π為各步驟所分配資源之間的關系，在p中變成了相應編碼之間的關系，但其組合方式沒有任何改變。因此，一個很自然的結論是：π滿足一個資源獨立性約束，當且僅當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之間的互斥約束，當且僅當p滿足這一約束。事實上，對于任意的資源獨立性約束集C，在資源分配集Π上存在等價關系“≈”，使得任取π∈Π，[π]≈中所有資源分配有相同的模式，且π滿足C當且僅當π的模式滿足C[7]。

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

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

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

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

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

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

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

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

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

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

3.p(s)←x;

4.v′←v; //為下一級調用計算新的v

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

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

7.i←s; //從當前步驟開始，對已分配編碼的所有步驟循環

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

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

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

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

12.i←i-1;

13. end while

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

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

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

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

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

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

20.end for

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

22.return NULL;

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

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

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

(2)

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

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

2.1 PB性能惡化

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

2.2 PB性能良好

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

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

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

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

3 實驗研究

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

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

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

每個實例的參數取值規則如下：

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

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

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

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

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

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

設置時間上限為6 min，在500個實例上執行4種對比算法，結果如下。

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

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

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

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

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

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

將步驟數的范圍擴大到[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個單元，按前述單實例規則生成50個實例，每組包含5單元共250個實例。在兩組實例上以6 min為限運行PB和MPB，統計結果見表1和表2。其中，avg(G)表示算法G在若干實例(通常是一單元中某一類別的實例)上的平均執行時間，剪枝高度均值(G)表示算法G在若干實例上產生的所有剪枝點(到實例結束或超時為止)的平均高度(剪枝點到根的距離稱為其高度)，搜索節點數均值(G)表示算法G在若干實例上的搜索節點數(一個實例執行結束或到其超時為止，執行過搜索驗證的節點總數)的平均值，Diff表示PB超時而MPB未超時的實例集。

表1 實驗2第1組實例結果統計

表2 實驗2第2組實例結果統計

(續表)

類別編號[k,K][8,27][24,43][41,60][57,76][75,94]MPB優勢的共同解出實例8數量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搜索節點數均值(PB)1781.55×1062.96×1065416搜索節點數均值(MPB)915499.3354PB優勢的共同解出實例17數量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搜索節點數均值(MPB)318.75226.18164.5158.36146.0625搜索節點數均值(PB)318.75226.18164.5158.36146.06

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

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

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

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

表3 實驗2第3、4組實例結果統計

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

4 結語

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

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