翟治年 盧亞輝 萬(wàn) 健,3 王中鵬 吳茗蔚

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

0 引言

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

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

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

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

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

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

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

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

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

定義2訪問控制策略是一個(gè)四元組〈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)}。對(duì)于一個(gè)資源分配π:T→U，若任取s∈T，均有π(s)∈UA(s)，則稱π滿足授權(quán)。

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

3.p(s)←x;

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

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

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

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

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

9. if (bp(p(i))≠?) continue; //bp(p(i))已計(jì)算，跳過當(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)在二分圖中無(wú)鄰點(diǎn)，驗(yàn)證A失敗

12.i←i-1;

13. end while

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

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

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

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

18.π′←MPB(s+1,p,v′); //p通過3種驗(yàn)證，但不是完整模式，繼續(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}給每個(gè)步驟賦值為0，v:{1,…,|U|}→{?}給每個(gè)資源賦值為?。由于在最壞情況下，算法可能遍歷模式解空間，故其時(shí)間復(fù)雜度為O*(B|S|)。

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

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

(2)

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

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

2.1 PB性能惡化

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

2.2 PB性能良好

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

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

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

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

3 實(shí)驗(yàn)研究

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

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

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

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

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

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

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

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

3.1 4種*WS(≠)算法的性能對(duì)比實(shí)驗(yàn)(實(shí)驗(yàn)1)

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

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

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

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

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

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

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

3.2 MPB與PB的進(jìn)一步對(duì)比實(shí)驗(yàn)(實(shí)驗(yàn)2)

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

表1 實(shí)驗(yàn)2第1組實(shí)例結(jié)果統(tǒng)計(jì)

表2 實(shí)驗(yàn)2第2組實(shí)例結(jié)果統(tǒng)計(jì)

(續(xù)表)

類別編號(hào)[k,K][8,27][24,43][41,60][57,76][75,94]MPB優(yōu)勢(shì)的共同解出實(shí)例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é)點(diǎn)數(shù)均值(PB)1781.55×1062.96×1065416搜索節(jié)點(diǎn)數(shù)均值(MPB)915499.3354PB優(yōu)勢(shì)的共同解出實(shí)例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é)點(diǎn)數(shù)均值(MPB)318.75226.18164.5158.36146.0625搜索節(jié)點(diǎn)數(shù)均值(PB)318.75226.18164.5158.36146.06

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

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

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

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

表3 實(shí)驗(yàn)2第3、4組實(shí)例結(jié)果統(tǒng)計(jì)

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

4 結(jié)語(yǔ)

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

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