＊WS-RI增量模式回溯的邊界收縮加速

翟治年，盧亞輝，周武杰，3，彭艷斌，鄭志軍，俞 堅(jiān)，豐明坤

1.浙江科技學(xué)院 信息與電子工程學(xué)院，杭州310023

2.深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院，廣東 深圳518060

3.浙江大學(xué) 信息與電子工程學(xué)院，杭州310027

1 引言

正隨著云制造[1]等眾包業(yè)務(wù)模式的發(fā)展，更多工作流開始依賴于第三方資源。此類資源通過云平臺(tái)，以虛擬服務(wù)形式接入[2]，容易隱匿惡意，威脅業(yè)務(wù)安全。為防止惡意資源提供者獲取關(guān)鍵數(shù)據(jù)，須對有關(guān)步驟施加授權(quán)約束。但其可能破壞資源分配可行性。相應(yīng)的驗(yàn)證與決策，稱為工作流可滿足決策（Workflow Satisfiability Decision，*WS）[3]。*WS 屬于NP 難問題[4]，僅在少數(shù)約束配置[3]或特定約束圖規(guī)范[5]下多項(xiàng)式時(shí)間可解。通常的搜索會(huì)因“組合爆炸”產(chǎn)生性能瓶頸。而蟻群等智能算法難以保證完備性，不利于無解判定[6]。一個(gè)可能的優(yōu)化方向是打破對稱（Symmetry Breaking）[7]。即分析約束集中的對稱因素，避免重復(fù)搜索對稱不可行解，從而降低驗(yàn)證開銷。

2014年，Cohen等識(shí)別了多種安全約束的資源獨(dú)立（Resource Independent）性質(zhì)[8]。相應(yīng)約束下的*WS 記為*WS-RI。定義了*WS-RI 的合格（滿足所有約束）資源分配模式。相同模式的資源分配合格性等價(jià)。為利用這種對稱性，建立了借助模式壓縮緩存的動(dòng)態(tài)規(guī)劃算法。其時(shí)間復(fù)雜度為O*(3||Vwlbw)，式中V是步驟集，w是資源分散度。但其空間復(fù)雜度仍為指數(shù)級，制約了實(shí)際性能表現(xiàn)。2016年，通過約束傳播、消除無用資源和預(yù)處理，使模式動(dòng)態(tài)規(guī)劃獲得了優(yōu)化的時(shí)間性能[9]。2015 年，Karapetyan 等將模式引入回溯搜索，建立了*WS-RI的模式回溯法[10]。其出發(fā)點(diǎn)是在與步驟授權(quán)集無關(guān)的模式空間上搜索真實(shí)、合格資源分配。為此，解決了模式真實(shí)性（即該模式是否可能滿足授權(quán)）的驗(yàn)證問題，方法是計(jì)算模式中步驟塊到資源集的指派（二分）圖，然后求其單向完備匹配。而模式合格性可以根據(jù)文獻(xiàn)[8]的結(jié)論來驗(yàn)證。模式回溯具有多項(xiàng)式空間復(fù)雜度，而時(shí)間復(fù)雜度為O*(B|V|)，其中B|V|為第 |V|個(gè)Bell數(shù)。起初，僅對葉模式進(jìn)行充要的真實(shí)性驗(yàn)證，而對其祖先僅做必要的快速驗(yàn)證[10]。2018年，翟治年等表明對每個(gè)模式進(jìn)行充要的真實(shí)性驗(yàn)證，可以平衡剪枝能力與驗(yàn)證代價(jià)，增強(qiáng)宏觀性能表現(xiàn)[11]。不過，在驗(yàn)證模式真實(shí)性時(shí)，文獻(xiàn)[11]沿用了文獻(xiàn)[10]的做法，從頭計(jì)算完全指派圖并求其匹配。設(shè)D表示資源集，一次真實(shí)性驗(yàn)證耗時(shí)O(|V|2|D|)。但其可能在每一個(gè)搜索結(jié)點(diǎn)處發(fā)生，且 |D|可比 |V|大得多[12-13]，故其3 次多項(xiàng)式的代價(jià)仍然偏高。2019 年，Karapetyan 等利用父子模式的差異，給出了增量化的真實(shí)性驗(yàn)證方法。一次驗(yàn)證耗時(shí)O(|V|2+|V||D|)[14]，降至二次多項(xiàng)式。由此建立了增量模式回溯（Incremental Pattern Backtracking，IPB）的方法。實(shí)驗(yàn)表明，相對于包括文獻(xiàn)[9]在內(nèi)的各種代表性方法，IPB 具有突出的性能優(yōu)勢，是目前求解*WS-RI最高效的方法。

模式技術(shù)引起了理論和應(yīng)用上的進(jìn)一步探索，例如文獻(xiàn)[15]在強(qiáng)指數(shù)時(shí)間假設(shè)下，證明模式動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度的最優(yōu)性，文獻(xiàn)[16]將模式回溯法進(jìn)行推廣，應(yīng)用于層次化類獨(dú)立約束*WS的求解等。

本文將對IPB 的真實(shí)性驗(yàn)證過程進(jìn)行改進(jìn)。針對其計(jì)算差異塊鄰域時(shí)，在整個(gè)資源集中展開搜索的缺陷，給出了一種邊界收縮的加速方法。實(shí)驗(yàn)表明，改進(jìn)方法在時(shí)間性能上獲得了較明顯的提升，且在資源集和步驟集規(guī)模較大時(shí)更有優(yōu)勢。

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

*WS-RI是一個(gè)三元組＜V,d,C ＞。其中V是步驟集，d:V→2D是步驟授權(quán)集，D是資源集。C是約束集，每個(gè)c∈C有作用域Vc?V，值域Dc?。且|Vc|＞1 ，稱為c的元數(shù)。對任意資源分配π:V'→D(V'?V)，若任取v∈V'，π(v)∈d(v)，稱π是授權(quán)的。任取約束c∈C，若在Vc上的限制π↑Vc∈Dc，稱π滿足c。任何c∈C都具有資源獨(dú)立性，即若π滿足c，則對任意的θ:D→D,θ(π)也滿足c。稱滿足所有c∈C的π合格，授權(quán)、合格的π有效，完整（即V'=V）、有效的π可行。*WS-RI 求任意一個(gè)可行資源分配，或判定其不存在。

V'模式是V'的劃分(V'?V)。給定＜V,d,C ＞，相應(yīng)*WS-RI 的任何資源分配π:V'→D都會(huì)產(chǎn)生一個(gè)V'模式Pπ={π-1(u)|u∈π(V')}，稱其為π的模式。任何V'模式P都會(huì)產(chǎn)生一個(gè)資源分配集ΠP={π:V'→D|Pπ=P}。若任取π∈ΠP都合格，稱P合格。若存在授權(quán)的π∈ΠP，稱P真實(shí)。稱真實(shí)、合格的模式有效、完整（即V'=V）、有效的模式可行。模式空間描述了向空劃分逐漸加入步驟，擴(kuò)展為更大劃分的過程。每個(gè)新步驟要么放入一個(gè)已有劃分塊，要么形成一個(gè)新塊。用同一步驟擴(kuò)展不同劃分，得不到同一劃分，故模式空間呈樹結(jié)構(gòu)。

模式回溯法對模式空間進(jìn)行深度優(yōu)先搜索，通過合格與真實(shí)性驗(yàn)證加以剪枝，找到可行模式后，將其轉(zhuǎn)換為可行資源分配。模式合格性通常根據(jù)約束語義來驗(yàn)證。而模式P的真實(shí)性驗(yàn)證分兩階段：計(jì)算其指派圖BP，再求其單向（從左到右）完備匹配。BP的左側(cè)頂集為P，右側(cè)頂集為D。任取塊b∈P和資源u∈D，(b,u)∈E(BP)當(dāng)且僅當(dāng)對任何v∈b均有u∈d(v)。將模式中每個(gè)塊匹配的資源分配給塊中所有變量，即可得到一個(gè)符合該模式的授權(quán)資源分配。

文獻(xiàn)[14]的IPB 改進(jìn)了真實(shí)性驗(yàn)證過程。對BP左側(cè)的每個(gè)頂點(diǎn)，只計(jì)算 |V|個(gè)鄰點(diǎn)（不足 |V|時(shí)完全計(jì)算）。當(dāng)回溯搜索驗(yàn)證模式P的真實(shí)性時(shí)，其父模式sup(P)已通過驗(yàn)證，求得指派圖Bsup(P)及其單向完備匹配Msup(P)。而P 相對其父的差異塊bP-sup(P)是唯一的。計(jì)算該塊的鄰域，并沿用其他塊的鄰域，即可由Bsup(P)得到BP。在求BP的單向完備匹配時(shí)，以其他塊在Msup(P)中的匹配邊集為初始匹配，求一條源自bP-sup(P)的增廣路即可。

3 基于邊界收縮的塊指派算法

圖IPB 在搜索過程中頻繁進(jìn)行模式真實(shí)性驗(yàn)證。每次都需要計(jì)算模式的指派圖。其計(jì)算效率對算法的整體性能影響很大。對每個(gè)模式P，IPB僅計(jì)算差異塊bP-sup(P)的指派鄰域。然而，它是從整個(gè)資源集D中尋找bP-sup(P)的鄰點(diǎn)。對每個(gè)u∈D，為驗(yàn)證是否對任何v∈bP-sup(P)均有u∈d(v) ，需要O(|bP-sup(P)|)=O(|V|) 時(shí)間。在很大的D中找一個(gè)鄰點(diǎn)，驗(yàn)證開銷也很大。由于每個(gè)步驟v∈bP-sup(P)的授權(quán)集d(v)都是分散落入整個(gè)D的，尋找一個(gè)位于所有d(v)中的資源，可以在D中跳躍進(jìn)行，減少對無效資源的驗(yàn)證。為此，給出一種基于邊界收縮的塊指派（Block Assigning via Boundary Shrinking，BABS）算法，其偽代碼描述如下（next(d(vi),l)表示d(vi)中大于l的第一個(gè)值，不存在時(shí)取∞）。

算法1 BABS(b,l,h)

輸入：b 為待指派鄰點(diǎn)的塊，l,h ∈D 是b 鄰域的任意下界和上界（設(shè)D 上定義有全序關(guān)系）。

輸出：返回b 在[l,h]之間的 ||V 個(gè)鄰點(diǎn)（不足時(shí)全部返回）。

更新模式P的指派圖時(shí)，算法1 和文獻(xiàn)[14]的IPB一樣，僅計(jì)算差異塊bP-sup(P)的 |V|個(gè)鄰點(diǎn)，僅當(dāng)其不足時(shí)完全計(jì)算。由于每個(gè)塊的鄰域在其為差異塊時(shí)計(jì)算完成，故整個(gè)指派圖中，塊鄰域大小均不超過 |V|。而文獻(xiàn)[10]和文獻(xiàn)[11]的模式真實(shí)性驗(yàn)證使用了P的完全指派圖）。在單向匹配的存在性上，上述兩種指派圖是等價(jià)的，但文獻(xiàn)[14]只是默認(rèn)使用了這一結(jié)論。本文補(bǔ)充其證明如下：根據(jù)Hall定理，二分圖BP存在左到右完備匹配，當(dāng)且僅當(dāng)任取Q?P,|N(Q) |≥ |Q|,這里N(Q)=N(b)，而N(b)是b在BP中的鄰域。任取塊b∈P，若其鄰域大小達(dá)到 |V|，包含該塊的任何Q滿足|N(Q) |≥|V|≥ |P|≥ |Q|。此時(shí)計(jì)算其所有鄰點(diǎn)或者恰好 |V|個(gè)鄰點(diǎn)，對整個(gè)BP的單向匹配存在性沒有影響。由b的任意性得證。

故此，算法1 和IPB 對BP結(jié)構(gòu)的簡化不影響P的真實(shí)性驗(yàn)證結(jié)果，也不會(huì)損失授權(quán)剪枝能力。文獻(xiàn)[14]的變量排序規(guī)則，可以在統(tǒng)計(jì)意義上增強(qiáng)約束剪枝能力。不過，本文沒有對此作出優(yōu)化。

用算法1 計(jì)算任意塊b的鄰域，時(shí)間復(fù)雜度是O(|D||b|)=O(|D||V|)。但其既是尋找僅一個(gè)鄰點(diǎn)，也是尋找所有鄰點(diǎn)的最壞理論代價(jià)，很難準(zhǔn)確反映實(shí)際的鄰域計(jì)算開銷。算法1 利用步驟授權(quán)資源的分布邊緣和間隙跳躍取值，可有效改善這一計(jì)算的實(shí)際性能。該算法依賴于外部指定的初始邊界l和h。在比較粗糙的情況下，可以將它們?nèi)∽鱩inD和maxD。下一章將利用IPB的搜索結(jié)構(gòu)，以每個(gè)模式處常數(shù)時(shí)間的代價(jià)計(jì)算更緊的初始邊界。

4 邊界收縮增量模式回溯算法

下面給出本文的改進(jìn)IPB，稱為邊界收縮增量模式回溯（Incremental Pattern Backtracking via Boundary Shrinking，IPB-BS）。它在搜索過程中以增量方式計(jì)算差異塊鄰域的初始邊界，以此為參數(shù)調(diào)用BABS完成該塊的鄰域計(jì)算。其偽代碼描述如下。

算法2 IPB-BS(P,&B,M) //遞歸函數(shù)

輸入：模式P；傳址的二分圖變量B=BP；M 是B 的單向完備匹配。初始調(diào)用置P ←?，B ←?，M ←?。

輸出：返回＜V,d,C ＞的可行解，或其不存在時(shí)，返回UNSAT

return M ；// M 可視為V →D 映射

} else {

計(jì)算將v 加入P 形成的合格模式集X(P,v)；

for (P'∈X(P,v)) {//X(P,v)是用步驟v 擴(kuò)展模式P可能得到的所有子模式

if (bP'-P={v}) {//v 單獨(dú)成塊。bP'-P表示模式P' 相對其父模式P 的唯一差異塊，其中必含步驟v

將d(v)中的前 ||V 個(gè)（不足時(shí)取全部）指派給bP'-P，將B轉(zhuǎn)換為B' ，并備份更改；//B 可視為P →2D映射，為P 中每個(gè)塊確定一個(gè)指派鄰域

lbP'-P←min d(v)；//設(shè)置下界初值，lbP'-P是塊bP'-P的指派鄰域下界

hbP'-P←max d(v)；//設(shè)置上界初值，hbP'-P是塊bP'-P的指派鄰域上界

} else {//P' 是將v 加入P 中原有塊而形成的，bP'-P∈P'在P 中對應(yīng)的塊為bP'-P-{v}

if (lbP'-P-{v}∈d(v)) lbP'-P←lbP'-P-{v}；//v 加入前的下界仍然有效

else lbP'-P←next(d(v),lbP'-P-{v}) ；//下界失效，用d(v)中大于lbP'-P-{v}的第一個(gè)值對其進(jìn)行修正

if (hbP'-P-{v}∈d(v)) hbP'-P←hbP'-P-{v}；//v 加 入前的上界仍然有效

else hbP'-P←prev(d(v),hbP'-P-{v})；//上界失效，用d(v)中小于hbP'-P-{v}的第一個(gè)值對其進(jìn)行修正

調(diào)用BABS(bP'-P,lbP'-P,hbP'-P)計(jì)算bP'-P的鄰域，將B 轉(zhuǎn)換為B'，并備份更改；

從M 中刪去bP'-P所關(guān)聯(lián)的邊；

}

以M 為初始匹配，用Hungary算法求B'的最大匹配M'；

if (| M' |= |P'|) {// M'是B'的單向完備匹配π ←IPBBS( P',B',M' )；

if (π ≠UNSAT) return π；

else {利用備份恢復(fù)B；}

} else {利用備份恢復(fù)B；}

}//for

return UNSAT；

}

在搜索時(shí)，IPB-BS 對每個(gè)當(dāng)前模式相對父模式的差異塊進(jìn)行判斷（第7 行）。若其為新步驟單獨(dú)形成的塊，直接設(shè)置初始下界和上界（第9 和10 行）。否則，利用新步驟的授權(quán)資源集，對差異塊的下界和上界加以修正（第12～15行）。這部分工作只需常數(shù)時(shí)間，不影響真實(shí)性驗(yàn)證的時(shí)間復(fù)雜度。同時(shí)，IPB-BS改用BABS計(jì)算塊鄰域，但其時(shí)間復(fù)雜度仍為O(|V||D|)。BABS 依賴于一些全局性索引數(shù)組，可以多項(xiàng)式時(shí)間預(yù)計(jì)算，不占用搜索時(shí)間。故IPB-BS 的整體時(shí)間復(fù)雜度和IPB 一樣，為O(B|V|(f(|C|)+|V|2+|V||D|)) ，其中f(|C|) 是 |C|的函數(shù)，表示單結(jié)點(diǎn)處的約束驗(yàn)證代價(jià)。特別地，單結(jié)點(diǎn)處的真實(shí)性驗(yàn)證代價(jià)仍為O(|V|2+|V||D|)。IPB-BS為實(shí)現(xiàn)邊界收縮附加的全局和局部數(shù)據(jù)均只占用多項(xiàng)式空間，因而整體上和IPB一樣，具有多項(xiàng)式空間復(fù)雜度。

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

本章將IPB-BS與MPB[11]、IPB[14]等國內(nèi)外新近工作對比。用C++實(shí)現(xiàn)各算法（統(tǒng)一采用IPB的變量排序規(guī)則，求匹配增廣路時(shí)采用寬度優(yōu)先方式），編譯運(yùn)行環(huán)境是：GNU C++、24 GB RAM 的CentOS 7 虛擬機(jī)、3.4 GHz Intel Core i3 CPU。單個(gè)實(shí)例執(zhí)行時(shí)間上限為30 min。

實(shí)驗(yàn)1 本實(shí)驗(yàn)采用文獻(xiàn)[11]的二元隨機(jī)模型生成僅含互斥約束的測試實(shí)例。其參數(shù)有 |V|、資源比例μ%=|D|/|V|、約束密度ω%=2|C|/(|V|(|V|-1)) 和授權(quán)比例k%=|d(v)|/|D|(v∈V)。它主要通過授權(quán)比例的變化來制造困難實(shí)例的生成機(jī)會(huì)。取10 ≤ |V|≤100可以覆蓋大多數(shù)工作流的步驟集規(guī)模，50 ≤μ≤200 反映普通的資源比例，10 ≤ω≤25 反映工作流應(yīng)用約束密度較低的特點(diǎn)。然后以不同跨度和分布，生成4組k值區(qū)間（第1 組：[1，33]、[17，49]、[34，66]、[50，82]、[68，100]；第2組：[8，27]、[24，43]、[41，60]、[57，76]、[75，94]；第3 組：[1，5]、[21，25]、[41，45]；第4 組：[2，4]、[22，24]、[42，44]），每個(gè)區(qū)間隨機(jī)生成50 個(gè)實(shí)例，共800 個(gè)實(shí)例。三種算法在四組實(shí)例上的運(yùn)行結(jié)果如表1所示。

表1 三種算法四組實(shí)例結(jié)果統(tǒng)計(jì)

除第3組的[1，5]區(qū)間以外，三種算法在各區(qū)間的解出率均相同。在[1，5]區(qū)間，兩種IPB較MPB多解出了2個(gè)實(shí)例，解出率高了4%。在所有區(qū)間上，兩種IPB的未解出實(shí)例都相同，且其中不存在MPB 的解出實(shí)例。這表明兩種IPB 較MPB 有微弱、確定的解出率優(yōu)勢。在各算法都完全解出的13個(gè)區(qū)間上，IPB的平均時(shí)間性能是MPB 的2.93 倍（各區(qū)間上平均時(shí)間之比的平均值），IPB-BS 是MPB 的2.56 倍。在其余3 個(gè)區(qū)間（第1 組的[1，33]、第3組的[1，5]和第4組的[2，4]）的共同解出實(shí)例上，IPB的平均時(shí)間性能是MPB的9.69倍，而IPB-BS是MPB 的35.9 倍?？梢娫诠餐獬鰧?shí)例上，兩種IPB 較MPB有顯著的時(shí)間性能優(yōu)勢。這主要因?yàn)閷τ诿總€(gè)當(dāng)前模式，兩種IPB 無需計(jì)算每個(gè)塊的完全鄰域，而只需計(jì)算差異塊的鄰域，且至多計(jì)算 ||V個(gè)鄰點(diǎn)，消除了重復(fù)計(jì)算，并進(jìn)一步減少了計(jì)算的鄰點(diǎn)個(gè)數(shù)。在完全解出的13個(gè)區(qū)間上，IPB的平均性能是IPB-BS的1.03倍，但在其余3 個(gè)區(qū)間的共同解出實(shí)例上，IPB-BS 的平均性能是IPB 的4.57 倍（在[1，33]區(qū)間為1.14 倍，[1，5]區(qū)間4.90倍，[2，4]區(qū)間7.65倍）。出現(xiàn)這種反差的原因在于：IPB-BS為了實(shí)現(xiàn)邊界收縮，預(yù)先計(jì)算了若干索引數(shù)組，但其降低了搜索階段指派鄰點(diǎn)的計(jì)算代價(jià)。對于前13個(gè)區(qū)間搜索很快完成的實(shí)例，IPB-BS 的預(yù)計(jì)算負(fù)擔(dān)可能使其較IPB 處于劣勢，但對于后3 個(gè)區(qū)間搜索相對耗時(shí)的實(shí)例，IPB-BS就表現(xiàn)出了自己的優(yōu)勢。特別地，取得了高達(dá)4.57倍的性能優(yōu)勢，其原因有兩點(diǎn)：首先，測試實(shí)例中僅含互斥約束，其檢查非常高效，使得真實(shí)性驗(yàn)證代價(jià)以及指派圖計(jì)算開銷對整體性能產(chǎn)生了更大的影響。進(jìn)而，這3個(gè)區(qū)間（特別是[1，5]和[2，4]）的步驟授權(quán)比例很低。IPB在原始的資源集中搜索指派鄰點(diǎn)，需要檢查可高達(dá)數(shù)十倍的無效資源。IPB-BS避免了這種不必要的代價(jià)，從而獲得了很高的性能收益。

實(shí)驗(yàn)2本實(shí)驗(yàn)將采用文獻(xiàn)[14]的相變實(shí)例生成模型，將兩種IPB作進(jìn)一步對比，探究IPB-BS的其他適用條件。該模型具有更高的資源比例，通過約束數(shù)量的調(diào)節(jié)來生成困難實(shí)例。每個(gè)實(shí)例包含互斥、五元at-most-3和五元at-least-3三種約束。其參數(shù)有 |V|、|D|、at-most-3/at-least-3 約束數(shù)γ和互斥約束數(shù)e。令 |V|從18 開始增加。將資源比例μ取作10和100，以反映第三方資源環(huán)境的特點(diǎn)。該模型對每個(gè)u∈D，從V中隨機(jī)選擇1～|V|/2 個(gè)不同的授權(quán)步驟。這將使得授權(quán)比例k%≈1/4。at-most-3/at-least-3約束不如綁定/互斥約束常見，故只取γ=|V|。然后根據(jù)有解概率恰為50%（即欠約束和過約束兩種易解情形中間的位置）的實(shí)例難度相變要求，通過估計(jì)和驗(yàn)證，確定剩余參數(shù)e的值。每組參數(shù)都生成了100 個(gè)實(shí)例，其中有/無解的數(shù)量相當(dāng)，均為理論上的困難實(shí)例。將對每組參數(shù)下的實(shí)例運(yùn)行結(jié)果分有/無解情形取平均值，消除隨機(jī)性影響后，觀察參數(shù)變化的性能影響。若出現(xiàn)超時(shí)實(shí)例，不再計(jì)算該組參數(shù)下的平均值。同時(shí)停止實(shí)驗(yàn)，不再求解更大參數(shù)的實(shí)例。

先在μ=10 的實(shí)例集上運(yùn)行兩種算法。每種算法在有/無解情形下，執(zhí)行時(shí)間隨 ||V值變化的對數(shù)坐標(biāo)曲線如圖1。

圖1 IPB-BS與IPB執(zhí)行時(shí)間對比(μ=10)

每種算法在無解實(shí)例上求解性能，通常都弱于有解實(shí)例。這主要是因?yàn)闊o解時(shí)必然遍歷解空間。在|V|=18～38 區(qū)間，IPB-BS 處于相對劣勢。這主要是因?yàn)镮PB-BS 的預(yù)計(jì)算以及邊界維護(hù)代價(jià)。但是，對作圖數(shù)據(jù)的統(tǒng)計(jì)表明，由此導(dǎo)致的IPB-BS絕對劣勢很小，在有/無解情形下平均差距僅為0.17 s 和0.31 s，最高差距僅為1.55 s。從 |V|=39 開始，不論有/無解情形，IPB-BS都開始取得優(yōu)勢：較IPB平均降低了32.8%的時(shí)間代價(jià)；最多降低了33.9%，出現(xiàn)在有解情形 |V|=46 處；最少降低了31.6%，出現(xiàn)在無解情形 |V|=39 處。整體上，隨著|V|的增大，IPB-BS 不僅開始表現(xiàn)出相對優(yōu)勢，而且其優(yōu)勢逐漸擴(kuò)大。這是因?yàn)閮煞NIPB 的單結(jié)點(diǎn)真實(shí)性驗(yàn)證時(shí)間為O(|V||D|)=O(10|V|2)，而在本實(shí)驗(yàn)配置下的約束驗(yàn)證時(shí)間為O(|V|2)，前者會(huì)隨著 |V|增加更快增長，在總代價(jià)中占據(jù)更高的比例。而IPB-BS 在真實(shí)性驗(yàn)證中較IPB 具有優(yōu)勢。當(dāng) |V|增加時(shí)，這種優(yōu)勢隨著真實(shí)性驗(yàn)證代價(jià)所占比例的提高，得到了更明顯的表現(xiàn)。就絕對差距而言，在 |V|=39～47 區(qū)間，在有/無解情形下，IPB-BS 較IPB 平均減少了16.9 s 和29.3 s 的執(zhí)行時(shí)間，最高差距達(dá)到71 s。

進(jìn)一步擴(kuò)大資源比例，對μ=100 的情形進(jìn)行實(shí)驗(yàn)，結(jié)果如圖2所示。

圖2 IPB-BS與IPB執(zhí)行時(shí)間對比(μ=100)

此時(shí)，IPB-BS的性能優(yōu)勢更為明顯。在時(shí)限內(nèi)，較IPB 多計(jì)算了 |V|=45 和 |V|=46 兩組實(shí)例。在 |V|=18～44 區(qū)間，相對于IPB，在有/無解情形下平均降低了45.7%和48.7%的時(shí)間代價(jià)。在有解情形下：最多降低了66.5%的時(shí)間代價(jià)，出現(xiàn)在 |V|=44 處；最少降低了6.0%，出現(xiàn)在 |V|=19 處。在無解情形下：最多降低了67.0%的時(shí)間代價(jià)，出現(xiàn)在 |V|=44 處；最少降低了10.6%，出現(xiàn)在 |V|=18 處。相對于μ=10 的情形，IPB-BS不僅取得了更大優(yōu)勢，而且在不同的 |V|處始終處于優(yōu)勢。這主要是因?yàn)椋罕窘M實(shí)例的原始資源集D擴(kuò)大了10 倍，使得從D中搜索鄰點(diǎn)的IPB，其真實(shí)性驗(yàn)證代價(jià)相對于約束驗(yàn)證代價(jià)，以及輔助的初始和維護(hù)代價(jià)，所占比例更為突出，從而IPB-BS 在真實(shí)性驗(yàn)證上的優(yōu)勢表現(xiàn)得更為充分。

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

本文對*WS-RI 的新近算法IPB 進(jìn)行優(yōu)化，給出了一種基于邊界收縮的加速方法。利用步驟授權(quán)資源的分布邊緣和間隙，通過邊界對齊和滑動(dòng)的方式，逐步找出步驟塊各指派鄰點(diǎn)，加快了模式真實(shí)性的驗(yàn)證過程。在隨機(jī)實(shí)例集上的實(shí)驗(yàn)表明，本文提出的IPB-BS 算法較非增量模式回溯法優(yōu)勢顯著。并且對如下的常見應(yīng)用條件，較IPB有比較明顯的性能優(yōu)勢：（1）工作流應(yīng)用典型的低約束密度，結(jié)合此時(shí)容易導(dǎo)致困難實(shí)例的低授權(quán)比例，以及能夠高效驗(yàn)證的約束類型。該條件下IPB-BS較IPB具有可高達(dá)數(shù)倍的性能優(yōu)勢。授權(quán)比例越低，優(yōu)勢越明顯。（2）第三方資源環(huán)境下典型的高資源比例，結(jié)合適當(dāng)?shù)氖跈?quán)比例，以及可導(dǎo)致相變的、適當(dāng)類型和數(shù)量的約束。該條件下IPB-BS較IPB具有比較明顯的性能優(yōu)勢。且資源比例越高，步驟數(shù)量越多，優(yōu)勢越明顯。下一步將對塊鄰域緩存的設(shè)計(jì)利用進(jìn)行研究。