工作流可滿足性的約簡增量模式回溯法

翟治年,劉關(guān)俊,盧亞輝,向 堅,吳茗蔚,豐明坤

(1.浙江科技學(xué)院 信息與電子工程學(xué)院,浙江 杭州 310023;2.同濟(jì)大學(xué) 計算機(jī)科學(xué)系,上海 201804;3.深圳大學(xué) 計算機(jī)與軟件學(xué)院,廣東 深圳 518060)

0 引言

工作流可滿足性(Workflow Satisfiability,WS)[1-2]是一種保守(conservative)約束可滿足問題(Constraint Satisfaction Problem,CSP)[3-4],其基本設(shè)置是求授權(quán)約束下任一可行資源分配(或確定其無解),稱為WS決策。在工作流執(zhí)行資源日益云/服務(wù)化趨勢下,資源配比(資源數(shù)n與任務(wù)數(shù)k之比)顯著增大,成為WS相對其他CSP的主要特征,并給WS求解技術(shù)帶來了獨特挑戰(zhàn),要求其實現(xiàn)固定參數(shù)k的多項式時間復(fù)雜度[1,5-7]。另一方面,WS決策側(cè)重于安全策略性質(zhì)的驗證,不足以指導(dǎo)最終的資源分配。在WS無解時,為消除沖突,使業(yè)務(wù)得以運(yùn)轉(zhuǎn),可以通過CSP值化[8-9]將部分約束柔性化,并最小化有關(guān)風(fēng)險(也有研究通過調(diào)整授權(quán)來消除沖突,并最小化有關(guān)代價[10])。而當(dāng)WS有解,特別是可行解很多時,更有必要從其他角度優(yōu)選,特別是根據(jù)某些柔性約束,選出違反風(fēng)險最小者。柔性約束導(dǎo)致的尋優(yōu)需求對WS求解技術(shù)提出了進(jìn)一步考驗,要求其在枚舉設(shè)置下,快速求解“欠約束”實例。上述兩個方面的需求共同引出了本文的研究主題,下面展開進(jìn)行分析。

首先,高資源配比將造成變量取值范圍的膨脹,放大潛在的值對稱因素。但保守CSP的打破值對稱求解受到變量值域不統(tǒng)一的嚴(yán)重限制,在群等價樹[11]、值可交換性[12]、逐片值可交換性[13]等相關(guān)研究中,均未得到很好解決,給人們造成了長期困擾。2014年,COHEN[14]面向常見的資源獨立CSP,提出了資源分配模式概念,為完全值對稱因素的分離打破準(zhǔn)備了重要工具[15],并由此提出一種模式動態(tài)規(guī)劃(Pattern Dynamic Programming,PDP)算法。PDP借助模式等價性來壓縮緩存,但模式數(shù)量仍為超指數(shù)級,將造成極大空間開銷,且該算法的設(shè)計需要反復(fù)搬移緩存內(nèi)容,進(jìn)一步制約了其時間性能。隨后,文獻(xiàn)[16]通過約束預(yù)處理、約束傳播、資源動態(tài)排序和消除無用值對PDP進(jìn)行了優(yōu)化,但不能從根本上克服前述缺陷。2015年,KARAPETYAN[17]建立了模式空間上的回溯搜索技術(shù),首次實現(xiàn)了多項式空間的WS固定參數(shù)求解。普通回溯的搜索樹已體現(xiàn)了變量值域(即各任務(wù)的授權(quán)資源集)因素,在節(jié)點處只須檢查或傳播約束[3]。而模式回溯要在搜索節(jié)點處計算指派(二分)圖及其(從左到右完備)匹配,以驗證授權(quán)。指派圖需要系統(tǒng)計算,每個塊鄰域耗費(fèi)O(kn)時間,成為模式回溯的性能瓶頸。2019年,KARAPETYAN[7]在匹配等價前提下,將全指派約簡為k指派,利用搜索上下文加速指派及匹配計算,得到增量模式回溯(Incremental Pattern Backtracking,IPB)法,其性能顯著超過了包括CP-SAT(近幾年Minizinc約束規(guī)劃挑戰(zhàn)賽的冠軍求解器)和文獻(xiàn)[16]PDP在內(nèi)的多種代表性方法[7],將模式技術(shù)研究推向了高峰[18-21]?，F(xiàn)有IPB可對資源分配或其模式進(jìn)行決策、枚舉或計數(shù)[22],但缺乏面向?qū)?yōu)場景的性能研究。另一方面,柔性約束違反風(fēng)險是可行解尋優(yōu)的重要標(biāo)準(zhǔn),其建?？蚣茉贑SP領(lǐng)域已有研究[8-9],但相關(guān)算法難以應(yīng)對WS的高資源配比壓力。2015年,CRAMPTON[23]建模了柔性資源獨立約束的違反程度,表明其僅由模式確定,由此提出了值工作流可滿足性(Valued WS,VWS)問題及其模式分支限界(Pattern Branch Bounding,PBB)算法。2017年,CRAMPTON[24]針對多個柔性目標(biāo)的度量值難以歸一化的情況,提出了雙目標(biāo)VWS及其PBB算法?，F(xiàn)有PBB均借鑒模式回溯法,以深度優(yōu)先的模式枚舉搜索為基礎(chǔ),但不支持剛性的約束和授權(quán)。

若剛性和柔性資源獨立約束并存,且授權(quán)為剛性,需要對可行資源分配進(jìn)行尋優(yōu),則IPB的模式枚舉能力提供了直接的解決方案:根據(jù)柔性約束可快速計算模式的風(fēng)險值[23],通過模式枚舉找出風(fēng)險最小可行模式,利用其搜索驗證時的指派圖匹配信息,轉(zhuǎn)化為可行解即可。因其在僅與k有關(guān)的模式空間上搜索,并在模式層面進(jìn)行解的優(yōu)選,故具有固定k的參數(shù)化性能。若進(jìn)一步引入目標(biāo)剪枝能力,還可望達(dá)到更好的性能。

然而,現(xiàn)有IPB研究主要關(guān)注WS決策設(shè)置,并用相變實例集進(jìn)行測試。相變是從“欠約束”到“過約束”的臨界狀態(tài),將導(dǎo)致可行解極少而難以搜到,或剛好無解而難以剪枝,為決策設(shè)置提供了測試壓力。但模式枚舉的情況非常不同。特別是“欠約束”(通過擴(kuò)大授權(quán)或降低約束而脫離相變點)的實例,可能有大量可行模式,均位于完全搜索樹葉端,將共同拉近剪枝搜索樹與完全樹的差距。由于可行模式大量分布于葉端,找到其中一個很快,但枚舉它們要遍歷整個剪枝樹,將非常緩慢。本文實驗表明:IPB對“欠約束”實例的模式枚舉性能很弱,且隨著“欠約束”程度增大快速下降。從應(yīng)用角度看,相變實例的出現(xiàn)條件過于苛刻,大多數(shù)WS有解實例都位于“欠約束”區(qū),而“欠約束”程度越高,可行解越多,對枚舉尋優(yōu)性能要求越高。而對無解WS,也須盡量將問題調(diào)整到“欠約束”狀態(tài),并進(jìn)行解的尋優(yōu)?？偟膩碚f,枚舉設(shè)置下“欠約束”實例的求解性能是業(yè)務(wù)運(yùn)轉(zhuǎn)和優(yōu)化的重要保障,而現(xiàn)有IPB對此存在明顯不足。

本文對基于IPB的模式枚舉框架進(jìn)行研究,并將問題設(shè)置簡化為模式枚舉計數(shù)(通過模式枚舉完成模式計數(shù))。主要貢獻(xiàn)在于:通過挖掘模式授權(quán)驗證中指派與匹配兩個環(huán)節(jié)的關(guān)系,提出了新的指派圖約簡理論與技術(shù);將其用于現(xiàn)有IPB的兩種實現(xiàn),均明顯提升了模式枚舉計數(shù)性能,特別是對高授權(quán)比例的“欠約束”情形,提升效果更為顯著;在相變實例集上,其模式枚舉計數(shù)性能也有所提高,故也有益于WS的決策/模式?jīng)Q策求解(至少無解情形下如此)。

1 引例

本章對文獻(xiàn)[1]給出的采購工作流進(jìn)行調(diào)整,以說明剛性和柔性資源獨立性約束并存時,對WS可行解的尋優(yōu)需求。該工作流包括創(chuàng)建訂購t1、同意訂購t2、收貨簽字t3、創(chuàng)建支付t4、收貨副簽t5、同意支付t6共6個任務(wù),其執(zhí)行關(guān)系為t1-t2-(t3-t5,t4)-t6,這里用—連接順序任務(wù),用()列出并行任務(wù)。該工作流有一定資源集,在它與任務(wù)集之間存在一定的剛性授權(quán)關(guān)系。在t1和t2、t3和t5、t4和t6三對任務(wù)之間,分別存在剛性互斥約束,以保證創(chuàng)建與同意或簽字與副簽職責(zé)的分離;在t1和t3之間存在柔性綁定約束,表示最好由訂購者收貨,當(dāng)資源分配模式P為t1和t3分配相同資源時,違反度為0,否則為1;而在t1和t4之間存在柔性互斥約束,表示盡量避免由訂購者創(chuàng)建支付,當(dāng)模式P為t1和t4分配不同資源時,違反度為0,否則為1。根據(jù)兩條柔性約束的重要程度,為相應(yīng)違反度賦予不同權(quán)重,可得到關(guān)于P的目標(biāo)函數(shù)。

上述剛性授權(quán)和剛性互斥約束共同確定了一個WS問題。但為了實現(xiàn)目標(biāo)函數(shù)的最小化,需要對該問題進(jìn)行模式枚舉求解。

2 預(yù)備知識

約束的資源獨立性,是指當(dāng)計劃π滿足約束x∈X時(約束及其滿足的定義與約束類型有關(guān)),任取U上的置換φ,計劃φ°π也滿足x。根據(jù)該性質(zhì),將可通過模式抽象,簡化計劃的約束滿足性驗證。例如某模式相應(yīng)的多個計劃是否違反互斥約束x=(s,t),由s和t在該模式中是否同塊即可判斷,無須對每個計劃分別驗證。稱模式P是合格的,當(dāng)且僅當(dāng)任何符合該模式的計劃合格;又稱模式P是授權(quán)的,當(dāng)且僅當(dāng)存在相應(yīng)的計劃授權(quán)。稱授權(quán)且合格的模式為有效模式,而有效的全模式為可行模式。WS決策/枚舉/計數(shù)設(shè)置分別求任一可行計劃(或確定其不存在)/所有可行計劃/可行計劃的數(shù)量。這些設(shè)置可有模式化版,即模式?jīng)Q策/模式枚舉/模式計數(shù)分別求任一可行模式/所有可行模式/所有可行模式的數(shù)量。引言所述的模式枚舉計數(shù)要求通過枚舉方式統(tǒng)計可行模式數(shù)量,本質(zhì)上是模式枚舉設(shè)置。

上述模式授權(quán)性,等價于模式的全指派圖存在左完備匹配。該圖定義為:

定義1給定模式Q,其全指派圖B=B(Q)是以Q為左側(cè)頂點集(每個左頂是Q作為劃分的一個塊),U為右側(cè)頂點集的二分圖,且塊b∈Q在B中的鄰域NB(b)=∩{U(t)|t∈b}。同時,將該鄰域稱為塊b的全(指派)鄰域。

該圖的左完備匹配可為Q中每個塊分配不同的資源,從而將模式轉(zhuǎn)化為一個相應(yīng)的計劃。只要模式是授權(quán)的,該計劃就是授權(quán)的。

利用模式之間的關(guān)系組織樹形模式空間,并進(jìn)行回溯搜索,可求解WS的各種問題設(shè)置及其模式化版本。模式回溯壓縮了搜索范圍,有助于化解高資源配比的性能壓力,而代價是在搜索結(jié)點處增加了模式授權(quán)驗證,包括計算模式指派圖,再求其左完備匹配兩個環(huán)節(jié)[17]。

文獻(xiàn)[7]進(jìn)一步建立了模式回溯的增量化框架:在每個節(jié)點處,相對于父節(jié)點只有一個新塊,即包含當(dāng)前任務(wù)的塊(可能是當(dāng)前任務(wù)單獨成塊,或?qū)⑵浼尤敫腹?jié)點的某塊而得),只須計算該塊的指派鄰域,即可將父節(jié)點指派圖更新為該節(jié)點的指派圖,稱為增量指派;而在父指派圖的匹配中,將當(dāng)前任務(wù)所加入塊原有的匹配邊(若當(dāng)前任務(wù)單獨成塊,則之前為空塊,無匹配邊)取消,然后以其為初始匹配,進(jìn)行一次匹配增廣,即得該節(jié)點指派圖的左完備匹配,稱為增量匹配。

對于全指派圖,計算新塊鄰域需要O(kn)的時間,特別是求一個鄰點也需要O(kn)的時間,在高資源配比(n/k)條件下,計算塊指派的全鄰域會嚴(yán)重拖慢搜索進(jìn)度。為降低增量指派的計算代價,文獻(xiàn)[7]建立了k指派圖的概念:

定義2設(shè)模式Q的全指派圖B=B(Q),稱其生成子圖K為Q的k指派圖,當(dāng)且僅當(dāng)任取b∈Q,若|NB(b)|

該圖在|NB(b)|≥k時對塊b的鄰域?qū)嵤┘s簡,降低指派計算目標(biāo)和負(fù)擔(dān),且不影響授權(quán)匹配:

定理1給定模式Q,設(shè)其指派圖B=B(Q),而其k指派圖K∈K(Q),則B存在左完備匹配當(dāng)且僅當(dāng)K存在左完備匹配。

約簡指派計算目標(biāo)之后,文獻(xiàn)[7]對計算出的塊鄰域進(jìn)行緩存,以減少重復(fù)計算,而在其提供的IPB實現(xiàn)中,還使用了位運(yùn)算來加速鄰點計算。文獻(xiàn)[21]為塊指派鄰點的計算引入了邊界收縮加速,以克服IPB從整個U中連續(xù)查找鄰點的缺陷。

文獻(xiàn)[7]的IPB針對WS決策設(shè)置描述,但很容易修改用于模式?jīng)Q策,而文獻(xiàn)[22]進(jìn)一步給出了基于IPB近似求解WS計數(shù)設(shè)置的方法,容易修改用于模式枚舉計數(shù)。因后者不統(tǒng)計可行模式相應(yīng)的計劃數(shù),不存在遺漏可行計劃的問題,故可采用k指派圖代替該文獻(xiàn)使用的全指派圖。須注意的是,該文獻(xiàn)對約束圖做了連通分解預(yù)處理,以控制問題規(guī)模,加快總體求解,但其不能簡單遷移到模式枚舉/計數(shù)。不妨設(shè)有兩個連通分支,分別取相應(yīng)分問題的一個可行計劃,組合即得總問題的一個可行計劃(由于無跨連通片的約束,故組合不會導(dǎo)致約束違反,而在兩個分計劃中,每個變量的取值必然滿足其值域要求)。反過來,將后者分解到兩個連通片上,即可還原之前的兩個分計劃。于是約束分解不影響計劃的枚舉/計數(shù)。然而,在模式枚舉/計數(shù)設(shè)置下,從兩個連通片各自取一個分可行模式,其組合出的總可行模式未必唯一確定。具體有哪些結(jié)果,還依賴于每個分模式包含哪些可行計劃。為了保證模式枚舉/計數(shù)的正確性,應(yīng)當(dāng)取消約束分解。

3 約簡增量模式回溯法

本文將定義一種結(jié)構(gòu)優(yōu)化的簡指派圖(定義3),進(jìn)一步削減指派計算目標(biāo),并證明該圖的左完備匹配存在性等價于全指派圖(定理2)以及k指派圖。簡指派圖的塊鄰域大小與指派圖整體結(jié)構(gòu)(體現(xiàn)在定義3中的|Q|和|∪Q|項)耦合,不利于增量計算(父子結(jié)點對簡指派鄰域的定義標(biāo)準(zhǔn)不同,影響子結(jié)點處的重用)。本文將通過證明有關(guān)的算法不變式(引理1和定理3),表明在IPB模式計數(shù)的搜索上下文中,可以增量方式計算簡指派圖。下面先給出有關(guān)概念:

定義3設(shè)模式Q的全指派圖B=B(Q),稱其生成子圖R為Q的簡指派圖,當(dāng)且僅當(dāng)任取b∈Q,若|NB(b)|<|Q|+k-|∪Q|,則NR(b)=NB(b),否則|Q|+k-|∪Q|≤|NR(b)|≤k。易知Q的簡指派圖不唯一,將它們的集合記為R(Q)。

簡指派圖可代替全/k指派圖,作為授權(quán)匹配的基礎(chǔ)。其依據(jù)在于:

定理2給定模式Q,設(shè)B=B(Q)為其全指派圖,R∈R(Q)為其簡指派圖,則B存在左完備匹配當(dāng)且僅當(dāng)R存在左完備匹配。

證明由于R是B的生成子圖,充分性顯然。下面只證必要性。

由二分圖匹配的Hall定理,要證R有左完備匹配,只須證任取Q′?Q,|∪{NR(d)|d∈Q′}|≥|Q′|。而任取Q′?Q,分兩種情況:

(1)存在b∈Q′,|NB(b)|≥|Q|+k-|∪Q|。由定義3知,|NR(b)|≥|Q|+k-|∪Q|,又恒有|∪Q|≤k,故有|∪{NR(d)|d∈Q′}|≥|NR(b)|≥|Q|≥|Q′|。

(2) 任取b∈Q′,均有|NB(b)|<|Q|+k-|∪Q|。由定義3可知任取b∈Q′,NR(b)=NB(b),而由B有左完備匹配可知|∪{NB(d)|d∈Q′}|≥|Q′|,從而也有|∪{NR(d)|d∈Q′}|≥|Q′|。

綜合上可知,R必存在左完備匹配。

證畢。

給定模式Q中的塊,求每個指派鄰點都要驗證若干候選資源,最壞情況下須遍歷整個U,且對每個候選,都要驗證其與塊中O(k)個任務(wù)的授權(quán),故鄰點指派過程具有O(kn)代價。全指派塊鄰域的規(guī)模達(dá)到O(n),計算代價很高。k指派和簡指派可分別對規(guī)模超過k和|Q|+k-|∪Q|的塊鄰域?qū)嵤┘s簡,而后者的約簡條件更低。又因為k≥|NR(b)|,所以其約簡結(jié)果也可能更小。

本文的改進(jìn)IPB將對搜索到的每個模式節(jié)點,以增量化方式計算唯一的簡指派圖,其核心思路是:對模式空間中的結(jié)點Q,設(shè)其唯一的新塊(包含當(dāng)前任務(wù)的塊)為bQ,而任取非新塊b,必然屬于Q的父結(jié)點模式P,此時有:

|Q|+k-|∪Q|≤|P|+k-|∪P|。

(1)

注意子模式比父模式多含1個新任務(wù),故總有|∪Q|=|∪P|+1,但|P|≤|Q|≤|P|+1,即子模式所含劃分塊數(shù)未必加1。于是任取塊b∈P∩Q,P簡指派圖對全指派鄰域NB(b)在較高起點進(jìn)行較小幅度的約簡,所得b鄰域一定滿足Q簡指派圖的要求。只要b鄰域在P處符合要求,到Q處可不加改動。從而在節(jié)點Q處,只須計算新塊bQ的簡指派鄰域(這表明簡指派圖可以增量方式計算)。特別地,若|NB(bQ)|≥|Q|+k-|∪Q|,根據(jù)定義3,計算|Q|+k-|∪Q|個鄰點即可作為NR(bQ),否則取NR(bQ)=NB(bQ)。下面分兩種情況,對簡指派與k指派圖的約簡能力進(jìn)行比較:

(1)|NB(bQ)|<|Q|+k-|∪Q|時,有|NB(bQ)|

(2) 否則,即在|NB(bQ)|≥|Q|+k-|∪Q|條件下,簡指派將實施約簡,取|NR(bQ)|=|Q|+k-|∪Q|。但本條件下不一定有|NB(bQ)|≥k,即未必滿足k指派的約簡條件。綜合這一差異,可給出本條件下簡指派較k指派減少計算的鄰點數(shù)量:

min{|∪Q|-|Q|+|NB(bQ)|-k,|∪Q|-|Q|}。

(2)

易知,式(2)必為非負(fù)值,其第一項對應(yīng)本文實施約簡而k指派未實施的情況,第二項對應(yīng)兩者都實施的情況。在第一種情況下|NB(bQ)|

綜合上述條件可知,若用簡指派代替k指派,則IPB主要的增量指派代價不增加,且簡指派圖規(guī)模不超過k指派圖,可以保持增量匹配的時間復(fù)雜度,故其在性能上至少是安全的,不會招致明顯損失。

其中條件(2)使得簡指派真正發(fā)揮作用,并較k指派產(chǎn)生優(yōu)勢。單獨考查一個搜索結(jié)點Q,可知|NB(bQ)|或|∪Q|-|Q|越大,該條件越容易滿足。而滿足后,簡指派將產(chǎn)生式(2)描述的優(yōu)勢。當(dāng)|∪Q|-|Q|越大時,式(2)中min操作所比較的兩項都越大,其比較結(jié)果也越大。當(dāng)|NB(bQ)|

以上考查了簡指派優(yōu)勢在模式剪枝樹中的分布情況,以便分析其整體效果。由于本文關(guān)心“欠約束”實例上的性能,而進(jìn)入該狀態(tài)有提高授權(quán)比例、提高資源配比(本文工作以高資源配比為前提,但其程度存在進(jìn)一步差別)和降低約束密度3種基本手段。在后文實驗部分,將分別改變這些參數(shù),對簡指派的改進(jìn)效果進(jìn)行測試和分析。

接下來面向WS模式枚舉計數(shù)設(shè)置給出本文的約簡增量模式回溯算法。

算法1RIPB(P,&R,M,&S,&U,&A,&X)。

輸入:S,U,A和X描述一個WS問題;P是一個可行模式;&表示其后的參數(shù)為傳址引用;R為P的簡指派圖,本文靈活使用該記號,也將其視為從P中塊到其簡指派鄰域的映射,即R(b)表示P中第b塊的簡指派鄰域;M是R的左完備匹配,本文靈活使用該記號,也將其視為從P中塊到其匹配資源(未匹配時為nil)的映射,還用其表示P中所有塊的匹配資源的集合,尚未匹配時為?;X為約束集,本文靈活使用該記號,也將其視為從任務(wù)到其參與的約束子集的映射,即任務(wù)s參與的約束子集可表示為X(s);

輸出:對問題(S,U,A,X),可由P擴(kuò)展得到的可行模式數(shù)量;

輸出不變式:返回時R與輸入時相同。

1 cnt←0;//子問題可行模式的數(shù)量,初始化

2 if(|∪P|=k){//P為全模式,擴(kuò)展過程終止

3 cnt←1;//擴(kuò)展于P的可行模式數(shù)為1

4 }else{

5 s←SelectLeftTask(P,S);//按排序規(guī)則取一剩余任務(wù)

6 for(1≤b≤|P|+1){//b依次標(biāo)識P中各塊和空塊

7 Pb←(P-)∪{b∪{s}};//s進(jìn)入b后塊標(biāo)識不變

8 if(!Satisfy(Pb,s,X))continue;

9 bak←R(b);//備份新塊的鄰域

10 R(b)←?;//準(zhǔn)備計算新塊的鄰域

11 for(u∈∩{U(t)|t∈b}){//用b表示塊本身

12 R(b)←R(b)∪{u};

13 if(|R(b)|=|Pb|+k-|∪Pb|) break;

14 }//不變式:此時R為Pb的簡指派圖

15 if(|b|=1)//s進(jìn)入空塊形成,此時M(b)=nil

16 M′←Augment(R,M,b);//R上從b增廣M

17 else//|b|>1,M(b)≠nil

18 M′←Augment(R,M-{(b,M(b))},b);

19 if(M′(b)≠nil){//授權(quán)匹配成功

20 c←RIPB(Pb,R,M′,S,U,A,X);;

21 cnt←cnt+c;//按加法原理匯總

22 }

23 R(b)←bak;//恢復(fù)至P的簡指派圖

24 }//for

25}//if-else

26 return cnt;

算法1第2行檢查模式P的完整性,若完整,且按輸入要求也是可行模式,則由第3行計數(shù)為1,由第26行返回結(jié)果;若P不完整,第7行對其進(jìn)行擴(kuò)展,得到子節(jié)點Pb,第8行對Pb進(jìn)行約束驗證,只須驗證s所參與的約束子集X(s),第10～18行對其進(jìn)行授權(quán)驗證,其中第10～14行為增量指派環(huán)節(jié),15～18行為增量匹配環(huán)節(jié)。當(dāng)兩種驗證通過后,第20行深度優(yōu)先搜索下一節(jié)點。若第8行約束驗證失敗,恢復(fù)塊b進(jìn)而恢復(fù)模式P,切換到兄弟節(jié)點繼續(xù)搜索。若授權(quán)驗證失敗,由第23行恢復(fù)第9行備份的R(b),再由第6行循環(huán)控制切換到兄弟節(jié)點。每個兄弟Pb的根子樹搜索完成后返回計數(shù)結(jié)果c,第21行將c累加到父節(jié)點P的計數(shù)器cnt中,當(dāng)各Pb根子樹搜索完成后,cnt就是P根子樹的可行模式數(shù)量,由第26行返回。注意,若沒有Pb通過驗證,則cnt保持第1行賦的0值,由26行返回,表明P根子樹不含可行模式。

如下給出了算法1模式計數(shù)框架的基本特性:

引理1算法1的輸出不變式成立,即對符合要求的輸入,該算法結(jié)束時的R等于輸入時的R。

證明|∪P|作歸納:

(1)基始。當(dāng)|∪P|=k時,算法進(jìn)入第3行的if分支,然后從第26行返回,R顯然不變。

(2)歸納步驟。假設(shè)當(dāng)|∪P|=h+1(0≤h<|S|)時結(jié)論成立,要證|∪P|=h時也成立。此時,因h

綜合基始與歸納步驟,命題得證。

證畢。

算法1的指派約簡不影響授權(quán)驗證,有結(jié)論:

定理3算法1第14行的不變式成立,即該行結(jié)束時的R為Pb的簡指派圖。

證明由于|∪P|=|S|時不經(jīng)過第14行,只須考慮|∪P|<|S|的情況,又分兩種情況:

(1) 當(dāng)P≠?時,同時輸入的R∈R(P)(算法1的輸入要求),要證第14行處R∈R(Pb)。設(shè)全指派圖B=B(P),B′=B(Pb)。這里b是模式Pb相對P的唯一新塊(注意Pb中的塊b包含第5行選擇的s,而P中的塊無論是否標(biāo)識為b,均不含s)。任取Pb中(相對于P)的非新塊d,由定義1可知NB′(d)=NB(d)=∩{U(t)|t∈d}。由引理1的結(jié)論及類似其歸納步驟的分析,第6行控制的每次循環(huán)都處理與輸入時相同的R和P,故第10行面臨的R∈R(P),即R為P的簡指派圖。由定義3可知R(d)?NB(d)(R為B生成子圖),而且:①當(dāng)|NB(d)|≥|P|+k-|∪P|時,|P|+k-|∪P|≤|R(d)|≤k。那么由NB′(d)=NB(d)也必有R(d)?NB′(d),再由式(1)有|P|+k-|∪P|≥|Pb|+k-|∪Pb|,從而必有|NB′(d)|≥|Pb|+k-|∪Pb|,|Pb|+k-|∪Pb|≤|R(d)|≤k。② 當(dāng)|NB(d)|<|P|+k-|∪P|時,R(d)=NB(d)。則若|NB′(d)|<|Pb|+k-|∪Pb|,由|NB(d)|=|NB′(d)|<|Pb|+k-|∪Pb|≤|P|+k-|∪P|,可得R(d)=NB(d)進(jìn)而R(d)=NB′(d)。綜合①和②可知,R(d)也必滿足Pb簡指派圖的要求。再由d作為非新塊的任意性,只要第10～14行按Pb簡指派圖的定義對新塊鄰域R(b)進(jìn)行更新,即可保證R∈R(Pb)。具體來說,由于Pb的全指派圖是B′,更新應(yīng)使R(b)?NB′(b),且當(dāng)|∩{U(t)|t∈b}|=|NB′(b)|≥|Pb|+k-|∪Pb|時,應(yīng)使|Pb|+k-|∪Pb|≤|R(b)|≤k,否則,應(yīng)使R(b)=NB′(b),這正是該段代碼所做的。因此,第14行結(jié)束后,R∈R(Pb)。

(2) 當(dāng)P=?時,只能有Pb={{s}},其中{s}是標(biāo)識為b的塊。由定義1,全指派圖B′=B(Pb)右側(cè)為U,而左側(cè)只有一個塊b,其鄰域為NB′(b)=U(s)。若|NB′(b)|≥|Pb|+k-|∪Pb|=k,由第10～14行代碼,易知其結(jié)束后R(b)?U(b)=U(s),且|Pb|+k-|∪Pb|=k=|R(b)|,而若|NB′(b)|<|Pb|+k-|∪Pb|=k,該段代碼也使得R(b)=NB′(b),滿足Pb簡指派圖的定義,故其結(jié)束后R∈R(Pb)。

證畢。

算法1中增量指派和增量匹配的時間復(fù)雜度分別是O(kn)和O(k2)。第8行的資源獨立約束驗證通?？梢栽贠(k)或O(k2)時間內(nèi)完成。故算法1總時間復(fù)雜度為O(Bk(kn+k2)),其中超指數(shù)函數(shù)Bk是第k貝爾數(shù),等于k集合的劃分?jǐn)?shù),即S的全模式數(shù)量。

算法1的空間占用主要是問題實例的授權(quán)、約束信息以及求解時所用指派圖結(jié)構(gòu),分別占用O(kn)、O(k2)和O(k2)空間,故總的空間復(fù)雜度為O(k2+kn)。

4 實驗研究

本章將簡指派用于IPB模式枚舉計數(shù)的兩種實現(xiàn),以驗證其改進(jìn)效果。首先用C++復(fù)現(xiàn)了IPB,并改造為模式計數(shù)算法,記為IPB21。IPB有公開的C#源代碼(http://researchdata.essex.ac.uk/114)。本文也將其轉(zhuǎn)換為C++,經(jīng)程序優(yōu)化后(在Windows平臺上測試,其性能通常優(yōu)于C#版本),改造為模式計數(shù)算法,記為IPB19。將上述兩種實現(xiàn)所用k指派改為簡指派,分別得到RIPB21和RIPB19。實驗涉及的幾種資源獨立約束很容易快速驗證。4種算法均采用文獻(xiàn)[7](增強(qiáng)約束剪枝)的變量排序規(guī)則。而為突出指派圖結(jié)構(gòu)和指派計算方法所致性能差異,未使用塊指派鄰域緩存技術(shù)。其中21版和19版分別使用文獻(xiàn)[21]的邊界收縮方案和位運(yùn)算來加速指派計算。另外,兩者分別采用深度和廣度優(yōu)先方式進(jìn)行匹配增廣。最后,將根據(jù)19和21版本中較小的改進(jìn)幅度來報告本文方法的優(yōu)勢。

此外,目前尚無基于通用求解器進(jìn)行模式枚舉的工作,作為一條可能的途徑,其建模問題還有待研究。文獻(xiàn)[16]的PDP決策算法系統(tǒng)化構(gòu)造并緩存已找到的所有模式,很容易修改用于模式計數(shù)。本文復(fù)現(xiàn)了該算法,驗證了其決策版本的性能水平,但其計數(shù)版本對后文兩個實驗中各自規(guī)模最小的一批實例,仍無法按時解出,故未納入正式對比。

本文的實驗環(huán)境為:主頻4 GHz/睿頻4.6 GHz的Intel Core i3-9350kf CPU(未超頻)、8 G RAM、CentOS 8、GNU C++(-O3優(yōu)化)、GMP6.2大整數(shù)庫。對每個實例的執(zhí)行時間,以30分鐘為上限。

表1 4種算法的時間(s)和空間(KB)代價

將IPB19與IPB21比較。由表1,在兩者均完全解出的前5組實例上,后者的時間性能高達(dá)前者的1.66～3.45倍。這主要源于以下兩個因素:

(1) IPB19的實現(xiàn)存在一個性能缺陷:若某個模式節(jié)點P所有驗證通過,則深入到以P為根的子樹,當(dāng)根子樹搜索完成回溯到P時,為恢復(fù)P的指派圖,重復(fù)計算了P處新塊(P相對于其父結(jié)點的唯一新塊)的鄰域。在前述公開的C#源代碼(IPB決策版本)中,該缺陷體現(xiàn)為:初次搜索某節(jié)點P時,若其新塊中含多個任務(wù),調(diào)用AddStepsToNode()更新指派圖,而回溯到P時,需要維護(hù)指派圖結(jié)構(gòu),為此調(diào)用RemoveStepsFromNode()。這兩個函數(shù)均調(diào)用ComputeIncidenceList()計算塊鄰域,并在該函數(shù)內(nèi),通過局部變量短暫備份了塊鄰域,以便匹配失敗后恢復(fù),但缺乏穩(wěn)定可持續(xù)的備份,造成了回溯時的重復(fù)計算。該實現(xiàn)的塊鄰域緩存機(jī)制有助于緩解相關(guān)影響,但寫入緩存后進(jìn)入子樹搜索,若期間緩存到達(dá)容量上限而清空,則回溯時無法從緩存中查出,無法保證消除重復(fù)計算。本文實驗中關(guān)閉緩存以對比不同指派圖及計算方法的原始性能差距,會使上述缺陷充分暴露。為分析其影響,本文針對其進(jìn)行優(yōu)化得到IPB19opt,在前5組實例上再次進(jìn)行測試,所得平均時間依次為4.77155、15.5722、1.04655、85.24735和830.7432s。由此重新計算IPB21的性能優(yōu)勢,將分別下降到1.33、1.16、2.39、1.63和1.21倍,仍比較顯著。這表明除了IPB19的自身缺陷,還存在IPB21與IPB19的特性差異,共同導(dǎo)致了IPB21在本實驗中的優(yōu)勢。

(2) IPB21和IPB19的主要差異在于任務(wù)塊指派鄰域的計算加速方式。IPB19在整個資源集U上搜索鄰點,但借助位運(yùn)算快速驗證每個候選資源(預(yù)先為每個資源計算授權(quán)任務(wù)集,用64位圖表示,而任務(wù)塊也有位圖表示,可借助位運(yùn)算判斷前者是否包含了后者),其實際代價為常數(shù),不妨設(shè)為1次操作。但塊越大,其鄰點在U中的分布越稀疏,為找到一個而驗證的候選越多。本實例集互斥約束密度很低,使得剪枝模式樹邊緣更接近完全樹葉端,有利于增大近葉節(jié)點處新塊的大小(從根到葉的每個結(jié)點引入一個新任務(wù),但多數(shù)時候是將其加入舊塊,故所得新塊趨于變大),這對IPB19的性能不利。而IPB21的邊界收縮加速方案利用任務(wù)授權(quán)資源之間的空隙(以及兩側(cè)的邊緣)來縮小搜索范圍,但其可能將一個候選資源與塊中每個任務(wù)進(jìn)行一次授權(quán)關(guān)系判斷,每次判斷需要常數(shù)時間,故候選驗證代價與塊大小有關(guān)。設(shè)給定塊大小為x,驗證一個候選的平均代價是x/y次操作(1≤y≤x,任務(wù)授權(quán)比例越高時,塊授權(quán)資源越稠密,y越趨于1),若塊中存在授權(quán)資源稀疏的任務(wù),可使每個鄰點的搜索范圍縮小z倍,則只要yz>x,IPB21便會優(yōu)于IPB19。降低授權(quán)比例可增大z值和y值,將有利于提高IPB21與IPB19的性能比。若固定授權(quán)比例及相應(yīng)的z和y值,則當(dāng)約束密度降低導(dǎo)致x增大時,IPB19搜索一個鄰點的范圍將指數(shù)級擴(kuò)張,而IPB21驗證每個候選的代價只是線性增大,故IPB21與IPB19的性能比也會提高,而且速度很快。為排除因素(1)的作用,觀察前述IPB21與IPB19opt的比較結(jié)果,可知IPB21處于優(yōu)勢,這與本實例集的低約束密度有關(guān)。進(jìn)而,IPB21的最大/小優(yōu)勢分別出現(xiàn)在第3/2組實例上,分別與其授權(quán)比例較低/高有關(guān)。盡管第5組實例的授權(quán)比例高于第2組,對IPB21優(yōu)勢的抑制作用更強(qiáng),但其資源配比不高,資源數(shù)量較少,影響了要計算的鄰點數(shù),故未更有效地抑制IPB21的優(yōu)勢。

由于IPB21和IPB19作為IPB的不同實現(xiàn)出現(xiàn)了極大性能差異,以上詳細(xì)分析了有關(guān)因素。本文主題在于簡指派對k指派的改進(jìn),后文將重點考查RIPB較對應(yīng)版本IPB的性能提升情況。

現(xiàn)在將IPB21與RIPB21進(jìn)行比較。由表1可知,在兩者均完全解出的前6組實例上,后者的時間性能達(dá)到前者的0.97～1.24倍,平均為1.11倍。這表明使用簡指派圖有效控制了鄰點的計算數(shù)量,進(jìn)而提高了授權(quán)驗證和整體搜索性能。特別地,在第2、5、6組,RIPB21的優(yōu)勢達(dá)到1.15～1.24倍。這幾組實例的特點是資源配比和授權(quán)比例都較高。此時,各任務(wù)的授權(quán)資源集較大,任務(wù)塊的全鄰域較大,有利于達(dá)到第3章的實施條件(2),使簡指派較k指派出現(xiàn)式(2)描述的優(yōu)勢。

再將IPB19與RIPB19進(jìn)行比較。由表1,兩者均完全解出了前5組實例,后者的時間性能達(dá)到前者的1.14～1.43倍,平均為1.3倍。19版本回溯時重復(fù)計算塊鄰域,將導(dǎo)致指派代價在總驗證代價中所占比例擴(kuò)大(注意回溯時不必重新驗證約束),故使用簡指派導(dǎo)致的優(yōu)勢也超過了21版本。

仍對前述50組四參數(shù),將m取作原來的2倍,然后每組生成2次,得到100個較高約束密度的實例,按前述三參數(shù)分10組進(jìn)行測試,結(jié)果如表2所示。相對于表1,同一算法在對應(yīng)實例組上的時間性能大大提高,其原因主要是稠密約束有效增強(qiáng)了剪枝,加快了枚舉計數(shù)搜索。

表2 2倍約束下4種算法的時間(s)和空間(KB)代價

將IPB19與IPB21比較。由表2,在兩者均完全解出的前6組實例上,后者的時間性能達(dá)到前者的1.64～3.18倍。相對于表1,第3、4、5組優(yōu)勢均下降,且3、4組下降較多,只有第2組優(yōu)勢略有提高。再對IPB19opt進(jìn)行測試,在前6組實例上的平均時間依次為1.49175、4.51175、2.21755、44.04355、238.53475和412.5632s,相應(yīng)的IPB21優(yōu)勢為1.32、1.20、2.13、1.30、1.21和1.22倍。相對于約束倍增前,第1、3、4組優(yōu)勢均下降,且3、4組下降較多,只有第2組優(yōu)勢略有提高。與IPB21較IPB19優(yōu)勢的變化相比,基本同步。這表明IPB21對IPB19性能優(yōu)勢在約束倍增后的變化(總體上是下降的)主要不是由IPB19自身缺陷導(dǎo)致的,而與IPB21和IPB19指派計算方式的差異有關(guān)。在之前的因素(2)中,也已分析過較稀疏約束對IPB19更不利的原因。

將IPB21與RIPB21比較。由表2,在兩者均完全解出的前6組實例上,后者的時間性能達(dá)到前者的0.96～1.21倍,平均1.11倍。再將IPB19與RIPB19比較。由表2,在兩者均完全解出的前6組實例上,后者的時間性能達(dá)到前者的1.14～1.40倍,平均為1.26倍?？傮w上,僅約束密度變化時,簡指派較k指派的優(yōu)勢略有下降。這是因為較多的約束增強(qiáng)了剪枝,降低了該技術(shù)發(fā)揮優(yōu)勢的機(jī)會。

上述倍增前后的約束密度均處于較低水平。實驗2將在較復(fù)雜約束配置下,通過施加充分的互斥約束達(dá)到相變條件,然后減少約束觀察其影響。

表1和表2中,4種算法的空間占用相差很小。它們都使用唯一的指派關(guān)系存儲,其內(nèi)容隨著搜索不斷變化,動態(tài)部分在堆上分配。表中RIPB和對應(yīng)IPB的峰值空間完全相同。盡管RIPB使用了更小的簡指派圖,預(yù)期空間占用會有所下降,但系統(tǒng)以4KB頁為單位分配堆空間(表中的空間為平均值,不一定是4KB的整數(shù)倍),每次可能分配較多的頁,除了滿足當(dāng)前申請的需要,還給出較大的預(yù)留,通?？梢匀菁{以字節(jié)為單位的指派圖變化。

現(xiàn)在限定k=16,m=18(ω=15),使μ從200以步長200增加到1000,再分別取AP為L、M和H,得到15組四參數(shù)配置,每個配置生成10個實例,對4種算法進(jìn)行測試,觀察其隨資源配比μ和授權(quán)比例AP增加的變化,結(jié)果如表3所示。

表3 資源增加時3種算法時間(s)與空間(MB)代價

固定AP=L時,隨著μ的增加,每種算法的時間性能呈現(xiàn)出較強(qiáng)的下降趨勢。這是因為μ增加會增大任務(wù)授權(quán)資源集,有利于塊鄰域的擴(kuò)大,這將使授權(quán)匹配更容易成功,剪枝模式樹規(guī)模相應(yīng)擴(kuò)大,而搜索性能隨之降低。而當(dāng)AP=M和L時,性能下降趨勢減緩。這是因為授權(quán)比例較高時,較低的資源配比就可使任務(wù)和塊的授權(quán)資源集足夠大,授權(quán)匹配基本可以成功,故繼續(xù)增加資源配比基本不會導(dǎo)致剪枝樹規(guī)模增大,而只是增加了與n有關(guān)的預(yù)計算開銷。從另一角度觀察表3的數(shù)據(jù),固定μ=200時,隨著AP的升高,每種算法的性能都在下降。而當(dāng)μ達(dá)到400或600以后,隨著AP的升高,同一算法的性能出現(xiàn)明顯的先下降后上升的變化。先下降仍是由于授權(quán)剪枝削弱導(dǎo)致搜索樹規(guī)模增大,后上升是因為剪枝樹規(guī)模基本不變,而同樣任務(wù)塊的授權(quán)資源在U中密度增大,只要檢查更少的候選就可找到足夠的鄰點,導(dǎo)致了塊指派鄰域計算代價下降。

統(tǒng)計表3的數(shù)據(jù),在μ=200的3組實例上:RIPB21(較IPB21)的提升倍數(shù)為0.97～1.17,平均為1.04;RIPB19(較IPB19)的提升倍數(shù)為1.05～1.36,平均為1.17。在μ=600的3組實例上:RIPB21的提升倍數(shù)為0.97～1.20,平均為1.11;RIPB19的提升倍數(shù)為1.18～1.41,平均為1.31。在μ=1000的3組實例上:RIPB21的提升倍數(shù)為0.97～1.29,平均為1.16;RIPB19的提升倍數(shù)為1.28～1.56,平均為1.40。隨著資源配比以步長4增加,簡指派的平均優(yōu)勢在21版本上從1.04增加到1.11再增加到1.16;在19版本上從1.17增加到1.31又增加到1.40。

在AP=L的5組實例上:RIPB21(較IPB21)的提升倍數(shù)為0.967～0.973,平均為0.971;RIPB19(較IPB19)的提升倍數(shù)為1.05～1.28,平均為1.17。在AP=M的5組實例上:RIPB21的提升倍數(shù)為0.98～1.29,平均為1.13;RIPB19的提升倍數(shù)為1.11～1.56,平均為1.37;兩者的最大提升倍數(shù)1.29和1.56均出現(xiàn)在μ=1 000處。在AP=H的5組實例上:RIPB21的提升倍數(shù)為1.17～1.22,平均為1.20;RIPB19的提升倍數(shù)為1.349～1.365,平均為1.358。隨著AP增加,簡指派的平均優(yōu)勢在21版本上從0.97增加到1.13再增加到1.20;在19版本上從1.17增加到1.37又下降到1.36。

下面對上述性能變化的原因進(jìn)行分析。大體上,資源配比或授權(quán)比例越大,任務(wù)授權(quán)資源越多,節(jié)點Q新塊bQ的全鄰域NB(bQ)越大,越有利于條件(2)的滿足,使簡指派較k指派的優(yōu)勢擴(kuò)大。不過,AP從M到L時,RIPB19的優(yōu)勢出現(xiàn)了下降。這是μ=1 000時,AP從M到L時,簡指派優(yōu)勢顯著下降導(dǎo)致的。其原因在于,μ=1 000和AP=M時,NB(bQ)已足夠大,使得簡指派的實施已經(jīng)很充分,繼續(xù)提高授權(quán)比例作用不大。特別地,提高授權(quán)比例仍將增加鄰點在U中的密度,使得搜索更少的資源就可完成指派鄰域計算,且其對19版本特別有利(因其候選驗證代價為常數(shù),指派效率主要取決于搜索范圍)。這就會相應(yīng)降低指派代價在整體驗證中的比例,以及簡指派的優(yōu)勢。

表3的空間數(shù)據(jù)表明,授權(quán)比例的增大對4種算法的峰值空間占用幾乎沒有影響,而資源配比增大使其有微弱增長。這是因為后者顯著增大了資源總數(shù),使以字節(jié)為單位的實例和索引數(shù)據(jù)規(guī)模明顯增大,導(dǎo)致系統(tǒng)分配了更多的4KB頁面。RIPB和對應(yīng)IPB的空間占用都相同,其原因類似于之前的分析。

實驗2文獻(xiàn)[7]配置at-most-r和at-least-r兩種全局約束(分別要求p≥3個任務(wù)至多/至少由3個不同資源執(zhí)行,而p稱為約束的元數(shù))和(2元)互斥約束,研究了相變實例的生成,并公開了有關(guān)實例集(http://researchdata.essex.ac.uk/114)。其生成規(guī)則簡介如下:將每個資源隨機(jī)授權(quán)給[1,0.5k]個任務(wù),相應(yīng)的授權(quán)比例α%約為1/4;分別固定μ%=10和100,讓k從18開始增長;對每個k,分別生成k個5元塊at-most-3和at-least-3約束,以及導(dǎo)致實例難度相變的特定數(shù)量互斥約束,得到1個實例,如此重復(fù)100次,得1組實例。本實驗只對每個算法完全解出的實例組進(jìn)行統(tǒng)計,并對每組100個實例的性能結(jié)果取均值。

先用上述相變實例集測試4種算法,μ%=10和μ%=100的時間結(jié)果分別如圖1和圖2所示。由于k的變化導(dǎo)致最小和最大執(zhí)行時間相差很大,本實驗繪圖均采用了對數(shù)縱坐標(biāo)。其中IPB19較IPB21更有優(yōu)勢,這與實驗1的情況相反。由于IPB19本身尚且存在性能缺陷,該優(yōu)勢必然源于IPB19和IPB21指派計算方式的差異。實驗1中已分析表明,給定授權(quán)比例,則降低約束密度(特別是互斥約束密度)有利于提高IPB21與IPB19的性能比。此處兩個相變實例集在固定1/4授權(quán)比例等條件下,通過增加互斥約束來到達(dá)“欠約束”到“過約束”的臨界點,將快速抑制塊大小,迅速降低IPB21與IPB19的性能比,使后者占據(jù)優(yōu)勢。對于μ%=100設(shè)置下各算法按時解出的實例組,每種算法的平均峰值空間均在19M左右。而在μ%=100的解出實例組上:當(dāng)k從18增至43時,21版本的峰值空間從19M+增至22M+;當(dāng)k從18增至43時,19版本的峰值空間從18M+增至77M+,且當(dāng)k=43時,增至177M+。μ%=100時空間占用的增加較為明顯,主要是問題實例和一些預(yù)計算索引的規(guī)模與n相關(guān),增長更快。特別是19版本,在n>k2時,對指派圖中的塊鄰域使用了耗空間的散列存儲。

統(tǒng)計圖1的原始數(shù)據(jù)可知:在4種算法共同解出的31組實例上,RIPB21的時間性能達(dá)到IPB21的1.03～1.08倍,且隨k的增加呈微弱增大趨勢,平均1.06倍,而RIPB19的時間性能達(dá)到IPB19的1.08～1.17倍,且隨k的增加呈一定增大趨勢,平均1.15倍。本實例子集n/k=10而授權(quán)比例約1/4,故當(dāng)k=18～48時,新塊大小|bQ|最大為4～5(當(dāng)塊增大時,塊鄰點數(shù)首次不足1)。而相應(yīng)的相變點(互斥約束數(shù)量)為27～82(見該子集的e50值表),故k=18和48時,5元塊bQ的互斥約束剪枝概率約為0.84和0.52,相應(yīng)的Q較難進(jìn)入授權(quán)驗證。當(dāng)k增加時,剪枝樹規(guī)模擴(kuò)大和搜索結(jié)點數(shù)增多,只是導(dǎo)致小的新塊更頻繁出現(xiàn)。對|bQ|=3,當(dāng)k=18～48時,|NB(bQ)|約為2.8～7.5,但|∪Q|-|Q|很難達(dá)到16～41,導(dǎo)致條件(2)很難成立,|bQ|=4時更是如此。故RIPB主要在|bQ|≤2時可能取得優(yōu)勢,其整體優(yōu)勢也很受限。|bQ|=1時,|NB(bQ)|≥k,簡指派達(dá)到充分優(yōu)勢|∪Q|-|Q|,當(dāng)k增加導(dǎo)致剪枝樹規(guī)模擴(kuò)大時,|bQ|=1可發(fā)生在更深的結(jié)點處,相應(yīng)的|∪Q|-|Q|會有所擴(kuò)大,有利于簡指派整體優(yōu)勢的擴(kuò)大。在19版本上,簡指派方法導(dǎo)致了更大的平均性能提升,其優(yōu)勢隨k增大的趨勢也更強(qiáng),主要是因為該版本回溯時重新計算指派,擴(kuò)大了指派代價在整體驗證中的比例。

統(tǒng)計圖2的原始數(shù)據(jù)可知:在共同解出的26組實例上,RIPB21的時間性能達(dá)到IPB21的1.13～1.24倍,最大倍數(shù)出現(xiàn)在k=21處,此后有一定下降趨勢,最小倍數(shù)出現(xiàn)在k=42處,平均1.18倍;在共同解出的29組實例上,RIPB19的時間性能達(dá)到IPB19的1.15～1.35倍,最大倍數(shù)出現(xiàn)在k=21處,此后有下降趨勢,最小倍數(shù)出現(xiàn)在k=46處,平均1.25倍。RIPB的優(yōu)勢較圖1明顯擴(kuò)大,但其在k增加時,主要呈下降趨勢。本實例集n/k=100而授權(quán)比例為1/4,當(dāng)k=18～45時,|bQ|最大為6～7。但其相變點為39～125(見該子集的e50值表),故k=18和45時,5元塊bQ的互斥約束剪枝概率為0.93和0.72,故進(jìn)入授權(quán)驗證的bQ較圖1更小一些。對|bQ|=4,當(dāng)k=18～45時,|NB(bQ)|約為7.0～17.6,難以滿足條件(2)。對|bQ|≤3,當(dāng)k=18～45時,|NB(bQ)|至少為28～70,均超過k而使簡指派有充分優(yōu)勢,使其整體優(yōu)勢較圖1明顯擴(kuò)大。但是圖2的剪枝樹達(dá)到更大規(guī)模,但進(jìn)入授權(quán)驗證的bQ反而小于圖1,意味著搜索節(jié)點中有更高比例的剪枝節(jié)點。這不利于RIPB的整體優(yōu)勢(因約束剪枝不進(jìn)入指派,授權(quán)剪枝的|NB(bQ)|通常非常小,簡指派在剪枝處基本沒有優(yōu)勢),只是圖2大量剪枝由快速的約束驗證導(dǎo)致,其負(fù)面作用有限。而當(dāng)k增大導(dǎo)致剪枝樹擴(kuò)張時,這種負(fù)面作用將隨之變得顯著,不利于RIPB整體優(yōu)勢幅度的保持。簡指派在19版本上的性能提升仍然更大,原因也與之前類似。相對于圖1的情況,隨著資源配比的擴(kuò)大(但增加了互斥約束以保持相變),RIPB的性能優(yōu)勢明顯擴(kuò)大。對其原因,將與下面擴(kuò)大授權(quán)的情形一起分析。

對μ%=10的情形,將授權(quán)方式分別改為每個資源[1,0.75k]和[1,k]個任務(wù),相應(yīng)的授權(quán)比例α%≈0.375和0.5分別是原來的1.5倍和2倍,保持其他參數(shù)不變,按前述方式生成實例集,對4種算法進(jìn)行測試。α%≈0.375時的結(jié)果如圖3所示,α%≈0.5時的結(jié)果如圖4所示。4種算法的性能均明顯下降,這是因為擴(kuò)大授權(quán)比例造成實例,進(jìn)入“欠約束”狀態(tài),模式剪枝樹顯著擴(kuò)大,模式枚舉搜索代價相應(yīng)提高。每種算法對上述各解出實例組的平均峰值空間均在19M左右,與之前相近。這是因為擴(kuò)大授權(quán)對實例和預(yù)計算索引的規(guī)模影響不大。

統(tǒng)計圖3原始數(shù)據(jù)可知:在共同解出的20組實例上,RIPB21的時間性能達(dá)到IPB21的1.11～1.24倍,隨k呈增長趨勢,平均1.16倍;在共同解出的20組實例上,RIPB19的時間性能達(dá)到IPB19的1.19～1.48倍,隨k呈增長趨勢,平均1.26倍。統(tǒng)計圖4原始數(shù)據(jù)可知:在共同解出的18組實例上,RIPB21的時間性能達(dá)到IPB21的1.45～2.10倍,隨k呈增長趨勢,平均1.76倍;在共同解出的17組實例上,RIPB19的時間性能達(dá)到IPB19的1.34～2.01倍,隨k呈增長趨勢,平均1.61倍。相對圖1的情況,圖3和圖4中RIPB的優(yōu)勢明顯擴(kuò)大,其原因相似,這里僅分析圖4的情況。該子集的授權(quán)比例為1/2,當(dāng)k=18～35時,|bQ|最大為8～9。但是其相變點(注意授權(quán)比例增大時,原有約束不變)為27～62,故k=18和35時,5元bQ的互斥約束剪枝概率約為0.84和0.65,較難進(jìn)入授權(quán)驗證。而當(dāng)|bQ|≤3時,必有|NB(bQ)|≥k,簡指派均有充分優(yōu)勢,故其整體優(yōu)勢較圖1明顯擴(kuò)大。同時由于k增大時,簡指派優(yōu)勢不充分的|bQ|=4節(jié)點比例提高有限,簡指派的優(yōu)勢也將隨k增大而明顯增長。2倍授權(quán)時,簡指派在21版本上取得了更大優(yōu)勢,這是因為該實例集資源配比和授權(quán)比例都較大,任務(wù)和塊的授權(quán)資源密度很高,對19版本的指派計算方式非常有利。這使得在19版本中,盡管存在重復(fù)指派缺陷,但指派代價占總驗證代價的比例仍然低于21版本,從而簡指派的改進(jìn)效果相對難以凸顯。

增大授權(quán)比例明顯擴(kuò)大了簡指派方法的優(yōu)勢,而有關(guān)原因在實驗1中已進(jìn)行過分析。但這里2倍授權(quán)比例就導(dǎo)致了較10倍資源配比更大的優(yōu)勢,原因在于:

(1) 增大資源配比提升了資源總數(shù),在固定的授權(quán)比例下,各任務(wù)的授權(quán)資源將更為分散。此時雖然每個任務(wù)的授權(quán)資源集擴(kuò)大了,但其交集的擴(kuò)大幅度會受到抑制,|NB(bQ)|只是按資源配比的增大倍數(shù)擴(kuò)大。而增大授權(quán)比例時,資源數(shù)量不變,不僅每個任務(wù)的授權(quán)資源集擴(kuò)大,而且其交集的擴(kuò)大幅度會增強(qiáng),|NB(bQ)|按授權(quán)比例增大倍數(shù)的|bQ|次冪擴(kuò)大,會使更多節(jié)點達(dá)到簡指派的實施條件。

(2)μ%=100的相變實例集在增大資源配比時,也增加了約束數(shù)量。后者導(dǎo)致剪枝模式空間不會明顯擴(kuò)大,抑制了較大|∪Q|-|Q|值的增多。而由圖2和圖4相關(guān)分析可知,該值對簡指派的優(yōu)勢程度起很大作用。而增大授權(quán)比例讓實例進(jìn)入“欠約束”狀態(tài),剪枝模式樹邊緣更逼近完全樹葉端,導(dǎo)致更多較大的|∪Q|-|Q|值,從而簡指派的作用效果也隨之提升。

現(xiàn)在對μ%=10的情形,將約束數(shù)量減少為原來的0.75和0.5倍,保持其他參數(shù)不變,按前述方式生成實例集,對4種算法進(jìn)行測試。0.75倍約束時的結(jié)果如圖5所示,0.5倍約束的結(jié)果如圖6所示。每種算法對上述各解出實例組的平均峰值空間均在19M左右,與之前相近。這是因為減少約束對實例和預(yù)計算索引的規(guī)模影響也不大。

統(tǒng)計圖5原始數(shù)據(jù)可知:在共同解出的19組實例上,RIPB21的時間性能達(dá)到IPB21的1.03～1.13倍,平均1.09倍;在共同解出的18組實例上,RIPB19的時間性能達(dá)到IPB19的1.16～1.36倍,平均1.25倍。相對圖1的情況,RIPB的優(yōu)勢有一定擴(kuò)大。這主要是因為減少約束使實例偏離相變點,進(jìn)入“欠約束”狀態(tài),使更多簡指派有潛在優(yōu)勢的搜索結(jié)點Q(位于原來的剪枝邊緣或其下方)進(jìn)入了授權(quán)匹配驗證。這些節(jié)點Q位置較深,其|bQ|必須很小,才能使|NB(bQ)|取滿足條件(2)的值。而深度越大,這樣的結(jié)點相對越少,故RIPB的優(yōu)勢較圖1提高不多。

由統(tǒng)計圖6原始數(shù)據(jù)可知:在共同解出的8組實例上,RIPB21的時間性能達(dá)到IPB21的1.06～1.12倍,平均1.09倍;在共同解出的8組實例上,RIPB19的時間性能達(dá)到IPB19的1.31～1.39倍,平均1.35倍。而在圖5的前8組實例上,RIPB21的時間性能只是達(dá)到IPB21的1.03～1.10倍,平均1.07倍?？梢?隨著約束進(jìn)一步減少,RIPB的優(yōu)勢仍有微弱擴(kuò)大,其原因仍類似于圖5相關(guān)分析。0.5倍約束的影響明顯弱于2倍授權(quán)比例,這是因為單純降低約束對簡指派優(yōu)勢的影響比較局限,特別是不能增大NB(bQ)的值。

5 結(jié)束語

本文面向云/服務(wù)化資源環(huán)境和WS可行解尋優(yōu)場景,研究資源獨立WS在模式枚舉計數(shù)設(shè)置下的求解技術(shù)。對此類WS的最高效求解途徑IPB進(jìn)行改進(jìn),建立了簡指派優(yōu)化技術(shù)。將本文方法應(yīng)用于IPB的兩種實現(xiàn)(包括原始C#實現(xiàn)的移植版本),在兩個隨機(jī)實例集上進(jìn)行實驗,結(jié)果表明:

(1)為最大化可滿足決策難度而生成的相變實例集對IPB并非最難的,而在偏離相變區(qū)的“欠約束”實例集上,該方法的性能急劇下降。這表明模式枚舉設(shè)置的求解難度有著顯著的特點,給現(xiàn)有最好的技術(shù)路線帶來了新的挑戰(zhàn)。

(2)通過降低約束密度,或提高資源配比,特別是通過增大授權(quán)比例的方式進(jìn)入“欠約束”狀態(tài)后,本文方法較IPB有明顯的優(yōu)勢。另外在相變實例集上,本文的方法也有一定優(yōu)勢。

下一步將結(jié)合增量模式回溯法研究的新進(jìn)展,繼續(xù)優(yōu)化模式枚舉/計數(shù)的性能,并尋求在非資源獨立約束條件下的擴(kuò)展。