基于模式回溯的#WS(≠)快速定界算法

翟治年，盧亞輝，俞 堅(jiān),潘志剛，周武杰，3

1(浙江科技學(xué)院 信息與電子工程學(xué)院，杭州 310023)2(深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 518060)3(浙江大學(xué) 信息與電子工程學(xué)院，杭州 310027)

1 引 言

工作流可滿足性(Workflow Satisfiability,WS)關(guān)系到業(yè)務(wù)安全策略與執(zhí)行資源分配的協(xié)調(diào)與否，是安全規(guī)劃的一項(xiàng)關(guān)鍵驗(yàn)證[1,2]，并具有執(zhí)行場(chǎng)景發(fā)現(xiàn)問(wèn)題(Scenarios Finding Problem,SFP)[3]等重要的應(yīng)用變體.為定量考查WS實(shí)例的可滿足性，并擴(kuò)展可滿足判定的途徑，文獻(xiàn)[4,5]提出了相應(yīng)的計(jì)數(shù)問(wèn)題(Counting Workflow Satisfiability,#WS).它是#CSP(Counting Constraint Satisfaction Problem)[6,7]的特殊形式，具有特定于業(yè)務(wù)安全的約束配置、可能的流程相關(guān)性[2]，步驟數(shù)量受限[8]、約束稀疏[9]等特征.在應(yīng)用上，#WS與安全工作流的資源彈性[10,11](部分資源失效時(shí)的WS)問(wèn)題有密切關(guān)系，為其提供了參考指標(biāo)和驗(yàn)證手段[4,12].近年來(lái)，云制造[13]、眾包[14]等依賴于第3方資源的新型工作流環(huán)境得到了蓬勃發(fā)展.此類資源具有虛擬、分散、多變等特性，失效和違約風(fēng)險(xiǎn)較高[15]，使業(yè)務(wù)安全規(guī)劃的資源彈性要求變得日益突出，亟待加強(qiáng)#WS等相關(guān)問(wèn)題的研究.

在基本的互斥約束下，#WS已進(jìn)入#P完全問(wèn)題類[16]，較NP完全問(wèn)題更為困難[17].而其全局計(jì)數(shù)要求又很難適用局部和智能搜索方法.特別地，在第3方資源環(huán)境下，候選資源數(shù)量大大超過(guò)工作流步驟[10,18,19]，給#WS算法造成了新的性能壓力.

現(xiàn)有#WS研究集中在常見(jiàn)的互斥和綁定約束下.其核心問(wèn)題是僅含互斥約束的#WS(≠)(綁定約束可以多項(xiàng)式時(shí)間消去[5])，在求解性能上已取得了一定進(jìn)展.2015年，文獻(xiàn)[5]將#WS(≠)歸約為邏輯可滿足計(jì)數(shù)問(wèn)題(Counting SATisfi ability,#SAT)[20]，借助其高效求解器sharpSAT，取得了一定的實(shí)測(cè)時(shí)間性能.由于歸約所得邏輯變量規(guī)模巨大，整體時(shí)間復(fù)雜度高達(dá)O*(2|R||S|)，其中S和R分別為步驟集和資源集.且其所用組件緩存技術(shù)極耗內(nèi)存，空間復(fù)雜度也達(dá)到同一量級(jí)，綜合性能很受局限.2016年，文獻(xiàn)[4]利用基于賦權(quán)集容斥原理和快速zeta變換的集合劃分方法，建立了一種#WS(≠)的動(dòng)態(tài)規(guī)劃算法，具有O*(2|S||R|)時(shí)間復(fù)雜度，但其空間復(fù)雜度仍為指數(shù)級(jí)，實(shí)際占用增長(zhǎng)很快.2016年，文獻(xiàn)[9]通過(guò)樹(shù)分解技術(shù)來(lái)利用約束圖的結(jié)構(gòu)信息，應(yīng)用樹(shù)分解回溯計(jì)數(shù)的方法(Counting Backtracking Tree Decomposition,#BTD)求解#WS(≠)，并對(duì)約束驗(yàn)證范圍進(jìn)行了簡(jiǎn)化，較前述工作更好地控制了空間開(kāi)銷.而其時(shí)間復(fù)雜度為O*(|R|W+1)，其中W為約束圖樹(shù)分解寬度.在工作流應(yīng)用常見(jiàn)的低約束密度條件下，W的值通常受限，因而該算法有比較明顯的時(shí)間性能優(yōu)勢(shì).但其對(duì)大量資源帶來(lái)的性能壓力，缺乏有效的約簡(jiǎn)機(jī)制.

最近，在WS研究中提出了一種模式回溯法[21,18,22].在互斥等資源獨(dú)立性約束條件下，可以有效克服資源集規(guī)模造成的解空間膨脹問(wèn)題，并利用回溯法的優(yōu)化技術(shù)積累.本文將根據(jù)模式回溯法的的兩層求解機(jī)制，通過(guò)精確的模式可行解計(jì)數(shù)，結(jié)合模式資源指派圖的匹配數(shù)量定界，提出一種# WS(≠)定界算法.實(shí)驗(yàn)表明，該算法在高資源配比、低約束密度條件下，能夠快速計(jì)算#WS(≠)解的上、下界，且其上界比較接近于精確解.

2 預(yù)備知識(shí)

WS以一組工作流步驟S為變量集、每個(gè)s∈S有一個(gè)值域Rs?R，其中R是所有資源的集合.對(duì)步驟變量的取值，有一組約束C.WS(≠)是C中僅含互斥約束的WS.任何互斥約束c都作用于兩個(gè)變量，要求它們?nèi)≈挡煌?WS(≠)的目標(biāo)是求任意一個(gè)可行解，即從S到R的一個(gè)賦值映射，使其滿足所有約束和(各變量的)值域要求，或指出可行解不存在.而#WS(≠)的目標(biāo)是統(tǒng)計(jì)WS(≠)可行解的數(shù)量.通常有解空間搜索或動(dòng)態(tài)規(guī)劃兩種求解途徑.

任何部分賦值，即從T?S到R的映射，都有其劃分模式：當(dāng)且僅當(dāng)兩個(gè)變量賦值相同時(shí)，將其歸入同一個(gè)塊，相應(yīng)塊的集合形成賦值變量集T的一個(gè)劃分，稱為模式.每個(gè)模式都是一組部分賦值的抽象.由此可以得到問(wèn)題解空間的一個(gè)壓縮映像，即模式空間.它是一棵以模式為結(jié)點(diǎn)的根樹(shù)，描述了對(duì)空劃分逐個(gè)加入新變量，最終擴(kuò)展至完全模式的可能路徑.其葉結(jié)點(diǎn)對(duì)應(yīng)于所有完全模式.

部分賦值滿足互斥約束c(即其給c的兩個(gè)變量分配不同的值)，當(dāng)且僅當(dāng)其模式滿足c(即其將c的兩個(gè)變量分入不同的塊).若對(duì)模式空間進(jìn)行搜索，發(fā)現(xiàn)一個(gè)模式違反約束，即可排除以其為模式的所有部分賦值，非常高效.然而，問(wèn)題解空間是根據(jù)值域構(gòu)造的，搜索時(shí)只需要驗(yàn)證約束.而壓縮為模式空間后，相應(yīng)于模式結(jié)點(diǎn)的部分賦值不一定符合值域要求，從而需要驗(yàn)證.文獻(xiàn)[18]解決了模式真實(shí)性驗(yàn)證(根據(jù)一個(gè)模式判定相應(yīng)的部分賦值有無(wú)可能滿足值域要求)的問(wèn)題，使得可以對(duì)模式空間進(jìn)行回溯搜索，通過(guò)可行模式得到WS(≠)的可行解.驗(yàn)證模式真實(shí)性的主要思路是給定任意模式P，為每個(gè)塊b∈P計(jì)算恰當(dāng)?shù)馁Y源指派鄰域Nb?Rb=∩s∈bRs，這里Rb稱為塊b的值域.根據(jù)P中所有塊的鄰域，可得(資源)指派圖G(P).存在符合WS(≠)值域要求且以P為模式的部分賦值，當(dāng)且僅當(dāng)二分圖G(P)存在左(塊側(cè))到右(資源側(cè))完備匹配.按此匹配為完全可行模式各塊中的步驟分配資源，即得WS的一個(gè)可行解.特別地，文獻(xiàn)[18]利用子模式相對(duì)父模式只有一個(gè)差異塊的特點(diǎn)，實(shí)現(xiàn)了增量式的真實(shí)性判定.只須計(jì)算差異塊的鄰域，并計(jì)算從差異塊出發(fā)的增廣路，即可將父模式指派圖擴(kuò)展為子模式指派圖，并由前者的匹配修改得到后者的匹配.

3 #WS(≠)的模式回溯定界

現(xiàn)有模式回溯法僅適用于WS(≠).若需統(tǒng)計(jì)所有可行解的數(shù)量，不僅要相應(yīng)改變算法結(jié)構(gòu)，而且所得算法將面臨著更嚴(yán)重的性能壓力.模式空間不僅實(shí)現(xiàn)了整個(gè)問(wèn)題解空間的壓縮，而且將部分賦值歸類為一個(gè)個(gè)的模式.相對(duì)于平面化的搜索空間，這種層次性有利于從宏觀上確定可行解數(shù)量的界，在保證一定結(jié)果質(zhì)量的前提下降低計(jì)算負(fù)擔(dān).本文在文獻(xiàn)[18]剛剛提出的增量模式回溯法基礎(chǔ)上，為#WS(≠)建立了一種模式回溯定界算法(Bounding Algorithm Based on Pattern Backtracking).其問(wèn)題求解思路可概括為以下幾點(diǎn)：

1.對(duì)每個(gè)模式P，均使用完全指派圖(對(duì)塊b∈P，Nb=Rb)，以防統(tǒng)計(jì)時(shí)遺漏可行解.WS(≠)求任意一個(gè)可行解，在可行解存在性等價(jià)的前提下，可以使用更為精簡(jiǎn)的指派圖來(lái)提高效率.而#WS(≠)不能遺漏任何可行解，只能使用完全指派圖(每個(gè)塊的指派鄰域都等于該塊的值域).

2.每個(gè)(左到右完備)匹配都可將完全可行模式轉(zhuǎn)化為一個(gè)真實(shí)可行解，不同匹配的轉(zhuǎn)化結(jié)果不同.故找到完全可行模式后，對(duì)其資源指派圖中的匹配數(shù)量計(jì)算上、下界，即為此模式所含可行解數(shù)量的界.而在驗(yàn)證模式真實(shí)性時(shí)，只關(guān)心匹配的存在性，求一個(gè)匹配即可.

3.用回溯法遍歷模式空間，對(duì)每個(gè)完全可行模式，計(jì)算其所含可行解數(shù)量的界，并相加匯總.

4.適當(dāng)利用約束圖和指派圖的結(jié)構(gòu)信息.通過(guò)連通片分解，由前者/后者得到獨(dú)立的# WS(≠)/二分圖匹配計(jì)數(shù)子問(wèn)題，分別求解，并相乘匯總.

下面給出具體算法.先由上述思路第4點(diǎn)得主控函數(shù).

算法1.#MAIN//計(jì)數(shù)主控函數(shù)

輸入：S、R、 {Rs|s∈S}和C作為全局變量可用，其中C只含互斥約束.

輸出：WS(≠)可行解數(shù)量下界LB和上界UB.

1.LB←1;

2.UB←1;

3.分解S和C構(gòu)成的約束圖，得一連通片集Comps;

4.for(compi∈Comps){

5.Si←V(compi);//V(compi)是compi的頂點(diǎn)集

6.Ci←E(compi);//E(compi)是compi的邊集，每邊對(duì)應(yīng)一條互斥約束

7. 〈LBi,UBi〉←#IPB≠(?,?,?,Si,Ci);

8.LB←LB·LBi;

9.UB←UB·UBi;

10.}

11.return〈LB,UB〉;

其中調(diào)用了如下模式回溯計(jì)數(shù)算法.它體現(xiàn)了前述思路的第1、3兩點(diǎn).

算法2.#IPB≠(P,&G,M,Si,Ci) //遞歸過(guò)程

輸入：已滿足約束和值域要求的模式P；其完全指派圖G=G(P)，&表示傳址；M是G的左到右完備匹配，其大小為|P|；Si和Ci表示一個(gè)連通片內(nèi)的變量集和約束集.

輸出：在Si和Ci導(dǎo)出的WS子問(wèn)題中，其模式擴(kuò)展于P的可行解數(shù)量下界LBi和上界UBi.

1.LBi←0;

2.UBi←0;

3.if(|∪P|=|Si|){//子問(wèn)題的完全可行模式

4. 〈LBi,UBi〉←#MATCH(G);//P為滿足C的完全模式，對(duì)其指派圖中符合值域的匹配數(shù)進(jìn)行界定

5.}else{

6. 按一定排序規(guī)則選擇擴(kuò)展變量s;//參見(jiàn)文獻(xiàn)[18]

7. 計(jì)算用s擴(kuò)展P形成的滿足C的模式集X(P);

8. for(Pj∈X(P)){//有未搜索的子模式

9. 基于G計(jì)算Pj的完全指派圖Gj=G(Pj);//指派圖增量計(jì)算，參見(jiàn)文獻(xiàn)[18]

10. 基于M計(jì)算Gj的左到右最大匹配Mj;//匹配增量計(jì)算，參見(jiàn)文獻(xiàn)[18]

11. if(|Mj|=|Pj|){//Mj完備

12. 〈LBij,UBij〉←#IPB≠(Pj,Gj,Mj,Si,Ci)//遞歸調(diào)用;

13.LBi←LBi+LBij;

14.LBi←LBi+LBij;

15. }

16. 恢復(fù)G;//利用增量計(jì)算時(shí)備份的差異信息

17. }//for

18.}//if-else

19.return〈LBi,UBi〉;

相對(duì)于用模式回溯求解WS(而不是#WS)，需要注意第16行恢復(fù)指派圖是無(wú)條件的，并非模式驗(yàn)證失敗或發(fā)生回溯時(shí)才進(jìn)行.算法2可以對(duì)完全可行模式進(jìn)行精確計(jì)數(shù).但為了進(jìn)一步得到真實(shí)可行解的數(shù)量界，須調(diào)用如下的匹配計(jì)數(shù)定界算法(其中函數(shù)LV()和RV()分別取二分圖的左側(cè)和右側(cè)頂點(diǎn)集).它體現(xiàn)了前述思路的第2、4兩點(diǎn).

算法3.#MATCH(G)

輸入：從模式(劃分塊的集合)到資源集的二分圖G

輸出：其左到右完備匹配數(shù)量的下界lb和上界ub.

1.lb←1;

2.ub←1;

3.對(duì)二分圖G進(jìn)行分解，得到連通片集GComps;

4.for(gcompk∈GComps){

5. if(gcompk是完全二分圖) {

6.p←0;//p表示已考查的左側(cè)頂點(diǎn)數(shù)

7. for(b∈LV(gcompk)){//對(duì)每個(gè)左側(cè)頂b

8.lb←lb·(|RV(gcompk)|-p);

9.p←p+1;

10. }

11.ub←lb;//可精確計(jì)數(shù)，上下界重合

12. }else{//非完全

13.lb←1;

14.p←0;//p表示已考查的左側(cè)頂點(diǎn)數(shù)

15. for(b∈LV(gcompk)){//對(duì)每個(gè)左側(cè)頂b

16.ub←ub·min{|Rb|,|RV(gcompk)|-p};

17.p←p+1;

18. }

19. }//if-else

20.}

在算法3中，對(duì)二分圖進(jìn)行連通片分解后，逐連通片計(jì)算匹配數(shù)上、下界.若連通二分圖是完全的，不難精確計(jì)算其匹配數(shù)，由第6-第11行代碼完成.否則，由第13-第18行代碼進(jìn)行定界.因?yàn)榭尚心Ｊ降闹概蓤D必然存在匹配，第13行將下界取1.而上界由第15-第18行代碼計(jì)算，其基本思路是將每個(gè)左側(cè)頂點(diǎn)的值域大小相乘.但是左側(cè)頂可匹配的鄰域還會(huì)受到一定限制.設(shè)b是連通二分圖中第p+1個(gè)被檢查的左側(cè)頂點(diǎn).事實(shí)上之前每檢查一個(gè)左側(cè)頂，都是從其可匹配的鄰域中隱含地選擇一個(gè)右側(cè)頂，形成一條擬匹配邊，得到一個(gè)更小規(guī)模的匹配子問(wèn)題.刪除這一對(duì)頂點(diǎn)及其所有關(guān)聯(lián)邊，不影響子問(wèn)題的計(jì)數(shù).因此檢查到第p+1個(gè)左側(cè)頂時(shí)，在相應(yīng)的子問(wèn)題中，至多有RV(gcompk)-p個(gè)右側(cè)頂可匹配.應(yīng)取其與|Rb|的較小者作為b可匹配的鄰點(diǎn)數(shù)上界.

整體上，算法1和現(xiàn)有的模式回溯WS算法一樣，至多對(duì)O*(B|S|)(B|S|表示第|S|個(gè)貝爾數(shù))個(gè)模式結(jié)點(diǎn)進(jìn)行檢查，每個(gè)結(jié)點(diǎn)處的驗(yàn)證開(kāi)銷為多項(xiàng)式級(jí).算法1要對(duì)每個(gè)完全可行模式進(jìn)行匹配計(jì)數(shù)，但由算法3易知，此過(guò)程可在多項(xiàng)式時(shí)間完成.因此，算法的整體時(shí)間復(fù)雜度仍為O*(B|S|).算法1沒(méi)有特殊的空間需求，和模式回溯WS算法一樣，具有多項(xiàng)式級(jí)空間代價(jià).

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

現(xiàn)在對(duì)算法1進(jìn)行實(shí)驗(yàn)研究，并與文獻(xiàn)[5]的sharpSAT歸約(R2sharpSAT)，文獻(xiàn)[4]的#DP和文獻(xiàn)[9]的#BTD簡(jiǎn)化(#BTD-S)算法對(duì)比.測(cè)試環(huán)境為主頻3.6GHz/睿頻4.2GHz的Intel Core i3 CPU、8G RAM、CentOS 8系統(tǒng)、GNU C++編譯器(-O3優(yōu)化)、GMP6.2大整數(shù)庫(kù)，單個(gè)實(shí)例執(zhí)行時(shí)限為半小時(shí).

實(shí)驗(yàn)1.4種#WS(≠)算法的性能對(duì)比

本實(shí)驗(yàn)將4種算法在不同步驟數(shù)量和資源配比下進(jìn)行綜合性能比較.由于互斥約束通常作用于職責(zé)分離的關(guān)鍵步驟，故取較低的約束密度.測(cè)試實(shí)例生成規(guī)則是：在[10,20]之間隨機(jī)生成20個(gè)值，得到相應(yīng)大小的S；對(duì)每個(gè)S，隨機(jī)取25≤μ≤75，得到μ%|S|大小的R(μ%稱為資源配比)；再?gòu)拇矸稚?D)、低(L)、中(M)、高(D)的4個(gè)區(qū)間{[1,100],[1,33],[34,66],[67,100]}中隨機(jī)選擇授權(quán)比例區(qū)間AP，對(duì)每個(gè)s∈S，隨機(jī)選取α∈AP，再隨機(jī)取α%|R|個(gè)不同資源作為Rs；隨機(jī)取5≤ω≤15，以概率ω%(稱為約束密度)決定每對(duì)步驟之間是否存在互斥約束，得到C，并保持其它參數(shù)不變，重復(fù)生成5次C，相應(yīng)得到一組5個(gè)同參數(shù)實(shí)例，測(cè)試時(shí)對(duì)每組的解出實(shí)例取平均結(jié)果.4種算法測(cè)得的解出率(用SP表示)、執(zhí)行時(shí)間、峰值空間如表1所示.

首先將算法1與#BTD-S比較.可以看到隨著實(shí)例規(guī)模的變化，兩者的空間占用均保持較小的值，且彼此差距不大.因?yàn)?BTD-S具有全局動(dòng)態(tài)規(guī)劃與局部回溯相結(jié)合的算法結(jié)構(gòu)，所以帶有子問(wèn)題解的緩存，更耗空間一些.算法1在12/20組實(shí)例上，平均空間占用不大于對(duì)方，略有優(yōu)勢(shì).在各組實(shí)例上，算法1的解出率均不低于對(duì)方.這主要源于算法1的執(zhí)行時(shí)間優(yōu)勢(shì).算法1在與對(duì)方解出率相同的15/20組實(shí)例(不含第20組實(shí)例，兩者均解出2/5，但具體實(shí)例不全相同，也不含#BTD-S無(wú)數(shù)據(jù)的第19組實(shí)例)上，所需的執(zhí)行時(shí)間也較少，其性能是對(duì)方的1.18-368倍不等，平均為54.9倍.在剩余3組兩者均完全解出的實(shí)例上，#BTD-S的性能是算法1的10.6-18.2倍，平均14.7倍.整體上，算法1有很明顯的時(shí)間性能優(yōu)勢(shì).

表1 4種#WS(≠)算法的時(shí)間(s)和空間(MB)代價(jià)Table 1 Cost of time(s)and space(MB)for the 4 #WS(≠)algorithms

將算法1與#DP比較.由于多項(xiàng)式和指數(shù)空間復(fù)雜度的差異，算法1有明顯的空間性能優(yōu)勢(shì).由表1可以看到，#DP的空間占用始終高于算法1，且隨著|S|的增大，差距不斷擴(kuò)大，從1.07倍增長(zhǎng)到207倍，平均為22.1倍.#DP的時(shí)間復(fù)雜度低至2的指數(shù)級(jí)，較算法1更有優(yōu)勢(shì).測(cè)試表明，在8G內(nèi)存和半小時(shí)限制下，#DP解出了第17組的全部5個(gè)實(shí)例，而算法1有2個(gè)未解出.除此以外，算法1的解出率均不低于對(duì)方.在兩者均完全解出的17組實(shí)例上，算法1的時(shí)間性能均優(yōu)于對(duì)方，比率為1.53-464548倍不等，平均為62019倍.這主要是由于#DP通過(guò)系統(tǒng)、規(guī)整的計(jì)算來(lái)控制時(shí)間復(fù)雜度，且初始開(kāi)銷很高，對(duì)小規(guī)模的實(shí)例并無(wú)優(yōu)勢(shì).而對(duì)于稍大規(guī)模的實(shí)例，#DP會(huì)很快遭遇空間性能的瓶頸.因而其僅在|S|=18(第17組實(shí)例)這樣的過(guò)渡區(qū)域，表現(xiàn)出了一定的優(yōu)勢(shì).在時(shí)間特別是內(nèi)存資源受限條件下，算法1的整體優(yōu)勢(shì)更為明顯.

將算法1與R2sharpSAT比較.R2sharpSAT始終具有很高的空間占用，達(dá)到算法1的258-278倍，平均258倍.R2sharpSAT的空間代價(jià)主要由組件緩存導(dǎo)致，由于使用了緩存清理技術(shù)，并未隨問(wèn)題規(guī)模明顯增長(zhǎng).在解出率上，R2sharpSAT也在第17組實(shí)例上超過(guò)了算法1，多解出了1個(gè)實(shí)例.但其在第19和20組實(shí)例上解出率均為0.算法1在與對(duì)方解出率相同的17/20組實(shí)例上，有15組優(yōu)勢(shì)，時(shí)間性能達(dá)到對(duì)方的18.8-116157倍不等，平均8151倍，有2組劣勢(shì)，對(duì)方性能是算法1的6.10和44.1倍.算法1仍然有整體上的優(yōu)勢(shì).

總體上，算法1的綜合性能比較突出.其空間性能僅在個(gè)別實(shí)例上弱于#BTD-S，時(shí)間性能在多數(shù)實(shí)例上有明顯優(yōu)勢(shì)，但在極少數(shù)實(shí)例上弱于其它算法.這種優(yōu)勢(shì)首先來(lái)源于模式空間對(duì)原始解空間的壓縮，其搜索范圍只取決于步驟數(shù)量，是與資源數(shù)量無(wú)關(guān)的.同時(shí)，在低約束密度下，約束圖結(jié)構(gòu)較為松散，容易形成多個(gè)連通片，降低子問(wèn)題的步驟數(shù)量.進(jìn)而，在葉結(jié)點(diǎn)處計(jì)算匹配數(shù)時(shí)，沒(méi)有采用指數(shù)時(shí)間的動(dòng)態(tài)規(guī)劃精確計(jì)數(shù)，而是盡可能分解二分圖，然后通過(guò)快速方法定界，使前述兩點(diǎn)優(yōu)化的效果得以保持.相形之下，#BTD-S雖然也較好控制了內(nèi)存占用，但其側(cè)重于對(duì)約束圖的結(jié)構(gòu)進(jìn)行深入的分解，對(duì)于大量資源造成的解空間膨脹問(wèn)題，缺乏有效的解決機(jī)制.而其它兩種算法整體上較#BTD-S更弱，很大程度上是受空間性能制約.當(dāng)然，其它算法均給出精確的可行解數(shù)量，而算法1只能給出其上、下界.表1進(jìn)一步給出了算法1的界相對(duì)其它算法所得精確值的比率(組內(nèi)各比率求平均，第20組只計(jì)算了與#BTD-S共同解出的1個(gè)實(shí)例).可以看到，其上界質(zhì)量較好，為精確解的1.06-2.79倍，平均1.41倍.

實(shí)驗(yàn)2.算法1時(shí)間性能隨資源配比的變化

如前述，每組實(shí)例主要有|S|、資源配比和約束密度3個(gè)參數(shù).由實(shí)驗(yàn)1可以看到，算法1的解出率和時(shí)間性能隨著|S|的增大，大體上呈現(xiàn)下降的趨勢(shì).工作流應(yīng)用中，約束密度通常較低，變動(dòng)不大.而在當(dāng)前常見(jiàn)的第三方資源環(huán)境下，資源配比|R|/|S|向上波動(dòng)的空間很大.根據(jù)實(shí)驗(yàn)1的測(cè)試情況，我們選擇|S|=15，取ω=10，在20%、50%、80%三種授權(quán)比例下，讓資源配比從4到20，以步長(zhǎng)4變化，進(jìn)一步了解算法1解出率、執(zhí)行時(shí)間和所得界的變化.為消除約束分布偶然性影響，每組參數(shù)生成50個(gè)實(shí)例，結(jié)果如表2所示.

表2 算法1執(zhí)行時(shí)間(s)隨資源配比的變化Table 2 Variation of the run-time(s)of algorithm 1corresponding to the ratio of resource

首先，資源配比的增大，使得80%授權(quán)的第5組出現(xiàn)了2個(gè)未解出實(shí)例.進(jìn)一步觀察可知，隨著資源配比的增加，平均執(zhí)行時(shí)間大體呈增加趨勢(shì).對(duì)于偏離趨勢(shì)的20%授權(quán)第3組實(shí)例和50%授權(quán)第2組實(shí)例，相應(yīng)的最大執(zhí)行時(shí)間也偏高.異常與這些個(gè)別值拉高平均值有關(guān).另外，50%授權(quán)的第4組和第5組實(shí)例平均值接近，但第5組實(shí)例的最大值偏低，其平均值主要源于集體貢獻(xiàn).對(duì)原始數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，可知第5組較大的值更多，其中位數(shù)是第4組的6.2倍，且有37個(gè)值不小于第4組的中位數(shù).對(duì)于同樣的|S|，模式空間的大小是固定的.上述執(zhí)行時(shí)間隨資源配比增長(zhǎng)的趨勢(shì)，主要是因?yàn)樵谒阉鹘Y(jié)點(diǎn)處，為計(jì)算模式塊的值域，需要在更大的資源范圍中搜索.當(dāng)其它條件一定時(shí)，更多資源會(huì)導(dǎo)致更多滿足約束和值域要求的賦值，故表2中無(wú)論LB還是UB都呈現(xiàn)隨資源配比而增長(zhǎng)的趨勢(shì).

5 結(jié)論與下一步工作

本文針對(duì)互斥約束下的#WS問(wèn)題，建立了一種基于模式回溯的定界算法.它具有O*(B|S|)時(shí)間復(fù)雜度和多項(xiàng)式空間復(fù)雜度.在資源配比相當(dāng)高，而約束密度較低的隨機(jī)生成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，本文算法在時(shí)間性能上較現(xiàn)有三種精確計(jì)數(shù)算法有相當(dāng)明顯的統(tǒng)計(jì)優(yōu)勢(shì)，而空間占用也常常是最小的.同時(shí)，算法確定的上界與精確結(jié)果比較接近，為其提供了很好的快速估計(jì).下一步將繼續(xù)優(yōu)化本文算法的性能，提高其求解問(wèn)題的規(guī)模.