工作流可滿足決策（≠）的完備獨(dú)立樹(shù)分解回溯法*

翟治年，盧亞輝，余法紅，高慧敏

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

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

3.嘉興學(xué)院 數(shù)理與信息工程學(xué)院，浙江 嘉興 314001

4.嘉興學(xué)院 機(jī)電工程學(xué)院，浙江 嘉興 314001

1 引言

工作流技術(shù)通過(guò)形式化建模與分析，實(shí)現(xiàn)業(yè)務(wù)執(zhí)行的自動(dòng)調(diào)度，在云制造、眾包等平臺(tái)中起著重要作用。工作流每個(gè)步驟有一個(gè)授權(quán)（資源）列表，某些步驟的執(zhí)行資源之間須滿足一定約束。所謂工作流可滿足決策（workflow satisfiability decision，*WS）尋求滿足授權(quán)和約束的任一資源分配解，可為業(yè)務(wù)正確執(zhí)行提供最低限度的保證。由于互斥是廣泛存在的職責(zé)分離等多種約束類型的特殊情形，并經(jīng)常參與各種組合約束配置，故僅含互斥約束的*WS是一個(gè)基本問(wèn)題，記為*WS（≠）。它具有NP完全性[1]，且實(shí)用中可能涉及多達(dá)上百個(gè)步驟，故其算法的理論和實(shí)際性能是研究社區(qū)關(guān)注的焦點(diǎn)。

WS（≠）的早期研究[2-4]中，求解方法均為各種形式的窮舉搜索，時(shí)間復(fù)雜度通常為O*(|U||S|)級(jí)（U、S分別為資源集和步驟集），隨著步驟集規(guī)模增長(zhǎng)，實(shí)際性能下降很快。2011年，Basin等人對(duì)帶選擇分支的工作流研究了互斥和綁定約束下的*WS，并給出了一種多項(xiàng)式時(shí)間近似算法，但其依賴于大量資源和授權(quán)均勻分布假設(shè)，且某些有解的情況會(huì)被判定為無(wú)解[5]。2013年，Crampton等人將多種*WS（≠）歸約為集合最大權(quán)劃分，得到了小底數(shù)的指數(shù)時(shí)間復(fù)雜度，其*WS（≠）情形的時(shí)間復(fù)雜度為O*(2|S|(|X|+|U|2))[6]（X為互斥約束集），這是目前最好的結(jié)果。但其空間代價(jià)為指數(shù)級(jí)，嚴(yán)重限制了求解規(guī)模。2014年，Cohen等人識(shí)別了一大類約束的正規(guī)性或資源獨(dú)立性特征，據(jù)此提出了模式編碼技術(shù)，并給出了相應(yīng)*WS的動(dòng)態(tài)規(guī)劃算法，其時(shí)間復(fù)雜度為O*(3|S|wlbw)，其中w是正規(guī)性等價(jià)關(guān)系關(guān)于資源集的分散度[7]，隨后又針對(duì)資源獨(dú)立性計(jì)數(shù)約束的*WS，給出了類似的算法[8]。2014年，Yang等人對(duì)考慮控制流結(jié)構(gòu)的*WS進(jìn)行了較全面的復(fù)雜性歸類[9]，但未求解其中的NP難問(wèn)題。2015年，Karapetyan等人將模式編碼與回溯搜索結(jié)合，提出了*WS的模式回溯算法，在正規(guī)性約束下具有目前最好的實(shí)際性能[10]。2016年，Crampton等人將資源獨(dú)立約束推廣為類獨(dú)立約束，給出了層次組織約束*WS的模式回溯算法[11]，其關(guān)于資源獨(dú)立約束的退化情形即為Karapetyan的算法。對(duì)于資源獨(dú)立約束，模式回溯算法的空間復(fù)雜度為O(|S|×|U|)，但其時(shí)間復(fù)雜度為O*(B|S|)，B|S|為第|S|個(gè)貝爾數(shù)[10]。由于B|S|的增長(zhǎng)比2|S|和3|S|等指數(shù)函數(shù)快得多，上述結(jié)果仍然很不理想?？偟膩?lái)說(shuō)，現(xiàn)有*WS（≠）研究取得了多方面進(jìn)展，出現(xiàn)了一些代表性算法，但其對(duì)理論或?qū)嶋H性能、時(shí)間或空間優(yōu)化往往會(huì)犧牲相對(duì)的指標(biāo)，失衡情況嚴(yán)重，亟待研究綜合性能良好的新型算法。

工作流可滿足性是約束可滿足問(wèn)題（constraint satisfaction problem，CSP）在訪問(wèn)控制約束下的特殊情形。在CSP研究中，約束圖樹(shù)分解是保證理論性能的重要方法，可得到以樹(shù)分解寬度+1為冪指數(shù)的時(shí)間復(fù)雜度。同時(shí)，回溯法深度優(yōu)先和及時(shí)剪枝的搜索方式契合CSP尋找第一個(gè)可行解的問(wèn)題性質(zhì)，是其完備求解的主要方式。2003年，Jegou等人將兩種技術(shù)結(jié)合，提出了樹(shù)分解回溯（backtracking treedecomposition，BTD）的方法[12]，以兼顧理論和實(shí)際時(shí)間性能，但緩存造成了較高的空間復(fù)雜度。根據(jù)*WS（≠）的特點(diǎn)，本文擬利用BTD來(lái)解決前述性能失衡問(wèn)題。這是因?yàn)椋汗ぷ髁骷s束用來(lái)表達(dá)關(guān)鍵性業(yè)務(wù)規(guī)則，其密度通常較低，有利于控制樹(shù)分解寬度；BTD的回溯搜索有很大機(jī)會(huì)快速找到一個(gè)解，并由此避免緩存過(guò)度擴(kuò)張。

然而，BTD在確定兄弟子問(wèn)題的相互獨(dú)立性時(shí)，僅以待賦值變量集之間的約束不相關(guān)性為依據(jù)，而未證明其變量不相交，無(wú)法保證子問(wèn)題的解兼容。隨后，BTD得到了不同角度的增強(qiáng)和應(yīng)用，如2003年和2004年將BTD用于求解Valued CSP和Max-CSP問(wèn)題的工作[13-14]，2007年關(guān)于BTD中變量排序規(guī)則的研究[15-16]，2009年將BTD應(yīng)用于#CSP的#BTD算法[17]，2014年為包連通樹(shù)寬概念給出樹(shù)分解算法并將其引入BTD的工作[18]，2016年對(duì)#BTD的全局一致性改進(jìn)[19]，2017年通過(guò)重啟搜索來(lái)提高BTD性能的研究[20]，等等。這些變種算法研究均以BTD子問(wèn)題獨(dú)立性為基礎(chǔ)，但未見(jiàn)指出其成立條件缺失問(wèn)題，并給出變量不相關(guān)性證明，故BTD的成立基礎(chǔ)仍比較脆弱，亟待進(jìn)行相關(guān)的理論研究。

本文從低約束密度下的技術(shù)選型出發(fā)，通過(guò)深入BTD基本理論的研究，得到了*WS（≠）性能平衡問(wèn)題的一種正確有效的解決方案，其主要貢獻(xiàn)是：（1）從變量不相交和約束不相關(guān)兩個(gè)角度提出了一種完備的BTD子問(wèn)題獨(dú)立性，克服了現(xiàn)有BTD不能證明子問(wèn)題變量不相交的基本缺陷，進(jìn)而給出了相應(yīng)的部分解緩存原理。（2）通過(guò)逐級(jí)分解為獨(dú)立子問(wèn)題，并利用緩存避免重復(fù)求解，設(shè)計(jì)了一種WS（≠）決策算法，并通過(guò)交替歸納的方法證明其正確性。該算法時(shí)間復(fù)雜度為O*(|S|3×dW+1)，冪指數(shù)可小于步驟集規(guī)模，且在較低約束密度下實(shí)測(cè)性能突出。

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

本章介紹CSP及約束網(wǎng)絡(luò)樹(shù)分解的概念。

定義1（約束可滿足問(wèn)題）CSP定義為四元組＜V,D,E,R>，其中：V是有限變量集，每個(gè)v∈V存在有限值域dv，D={dv|v∈V}，E是2V子集的多重集，表示約束集，每個(gè)e={v1,v2,…,vk}∈E有值域de?dx1&dx2&…&dxk（&表示無(wú)序卡氏積），而R={de|e∈E}。圖＜V,E>稱為該CSP的約束網(wǎng)絡(luò)。

定義2（賦值與可行解）給定前述的CSP，對(duì)任何Y?V，稱函數(shù)是Y的賦值。由于值域已確定，此函數(shù)可記為α:Y，若Y可由上下文確定，也可記為α。

若任取v∈Y，均有α(v)∈dv，則稱α符合變量值域。若對(duì)任何e={v1,v2,…,vk}∈E且e?Y，均有{α(v1),α(v2),…,α(vk)}∈de，則稱α符合約束值域。若α同時(shí)符合變量和約束值域，則其是合法的。整個(gè)V的合法賦值稱為CSP的可行解。

按求解目標(biāo)的差異，CSP分為三類：求任意一個(gè)可行解（或指出其不存在）的，稱為CSP決策；僅判斷可行解存在與否的，稱為CSP判定（determining CSP）；求所有可行解個(gè)數(shù)的，稱為CSP計(jì)數(shù)（counting CSP，#CSP）。

CSP的搜索求解可能用到以下概念：

定義3（賦值投影）給定賦值α:Y′，若Y?Y′，則α在Y上的投影α↑Y是Y的賦值，且任取v∈Y，有α↑Y(v)=α(v)。

定義4（賦值兼容）設(shè)賦值α1:Y1和α2:Y2均合法，若存在合法賦值α:Y1?Y2，使α↑Y1=α1且α↑Y2=α2，則稱α1和α2兼容，否則稱兩者沖突。

定義5（賦值擴(kuò)展） 設(shè)有賦值α:Y和α′:Y′，且Y?Y′，若α′↑Y=α，則稱α′是α在Y′-Y上的擴(kuò)展。顯然，若α和α′都合法，則兩者一定兼容。

為了分解約束網(wǎng)絡(luò)的復(fù)雜性，介紹如下概念：

定義6（圖的樹(shù)分解）給定圖＜V,E>，其樹(shù)分解定義為二元組＜C,T>，其中T=＜I,F>是頂點(diǎn)集為I、邊集為F的樹(shù)，而C={Ci|i∈I}是V的子集族。因T的每個(gè)頂點(diǎn)i對(duì)應(yīng)一個(gè)變量簇集Ci，＜C,T>可視作以C為頂點(diǎn)集的樹(shù)。它滿足以下性質(zhì)：

（2）任取e∈E，存在i∈I使得e?Ci。

（3）任取i,j,k∈I，若在樹(shù)T中k位于從i到j(luò)的路徑上，則Ci?Cj?Ck。

W=maxi∈I|Ci|-1稱為樹(shù)分解的寬度。CSP的樹(shù)寬w定義為其約束網(wǎng)絡(luò)所有樹(shù)分解的最小寬度。

對(duì)i,j∈I，約定：C(i)表示Ci各祖先結(jié)點(diǎn)的變量集，則C[i]=C(i)?Ci表示Ci及其祖先結(jié)點(diǎn)的變量集；sup(i)和subs(i)分別表示i的父親和所有兒子；Desc(j)表示j及其所有后代，而。

3 工作流可滿足決策（≠）

約定S表示工作流的步驟集，U表示其資源集。

3.1 問(wèn)題定義

本節(jié)給出互斥約束WS決策問(wèn)題的定義。

定義7（授權(quán)）授權(quán)A={UA(s)|s∈S}，其中UA(s)是步驟s的授權(quán)資源（即候選執(zhí)行者）列表。

定義8（互斥約束集）互斥約束集X?S&S，表示步驟間的二元職責(zé)分離關(guān)系：若{s,s′}∈X，則對(duì)工作流的同一案例，s和s′的執(zhí)行資源不能相同。

定義9（資源分配）資源分配π:S→U為工作流案例的每個(gè)步驟指派唯一的執(zhí)行資源。

定義 10（*WS(≠)問(wèn)題）*WS(≠)定義為四元組＜S,U,A,X>，須求任一資源分配π:S→U，使任取s∈S，π(s)∈UA(s)，任取{s,s′}∈X，π(s)≠π(s′)。

3.2 問(wèn)題求解

3.2.1 BTD的子問(wèn)題獨(dú)立性缺陷

BTD的核心概念是如下描述的子問(wèn)題獨(dú)立性。

定理1[12]設(shè)圖＜V,E>有樹(shù)分解＜C,T>，其中T=＜I,F>，且I的先根遍歷序列Γ=1,2,…,|I|。若i,j∈I,i＜j且i=sup(j)，則沒(méi)有和v∈Desc(Cj)-Ci?Cj使得{u,v}∈E。

該定理表明：若刪除Ci?Cj所含變量，則Desc(Cj)中各簇集所含剩余變量與Cj之前所有簇集所含剩余變量之間的約束聯(lián)系將被切斷。在此基礎(chǔ)上，現(xiàn)有BTD導(dǎo)出了相應(yīng)的子問(wèn)題獨(dú)立性關(guān)系。設(shè)j1＜j2＜…＜jq均為i的兒子，1≤p＜q，由定理1：Desc(Cjp)-的合法賦值不會(huì)因彼此約束而發(fā)生沖突。若Ci已合法賦值，則其每個(gè)兒子Cjk(1≤k≤p)代表的子問(wèn)題（須為Desc(Cjk)-Ci賦值）可依次獨(dú)立求解。然而，完成子問(wèn)題求解后，須將相應(yīng)部分解組合進(jìn)父問(wèn)題的部分解。若Cjp和Cjq相應(yīng)子問(wèn)題的變量集，即Desc(Cjp)-Ci與Desc(Cjq)-Ci，存在重疊變量v，則它們的獨(dú)立求解可能對(duì)v賦不同的值，從而導(dǎo)致兩個(gè)部分解沖突。

為保證BTD的正確性，約束不相關(guān)和變量不相交條件缺一不可。前者可由定理1加以保證，但后者尚未從理論上得到證明。由子問(wèn)題獨(dú)立性衍生的BTD緩存設(shè)計(jì)原理（見(jiàn)文獻(xiàn)[12]引理1）也存在類似缺陷，即不能保證緩存部分解與其他部分解兼容。

3.2.2 新的BTD子問(wèn)題獨(dú)立性及其緩存原理

針對(duì)BTD的上述缺陷，本文將建立一種完備的子問(wèn)題獨(dú)立性。首先給出本文的基本定理。

定理2設(shè)i,j∈I，f={i,j}∈F，從T中刪除f得到兩個(gè)連通片Ti=＜Ii,Fi>和Tj=＜Ij,Fj>，其中i∈Ii，j∈Ij，則：

證明（1）用反證法。假設(shè)，則必存在p∈Ii和q∈Ij使得v∈Cp?Cq。由于Ti和Tj是T刪除f所得兩個(gè)連通片，因此p和q在樹(shù)T中經(jīng)f連通，即連通二者的路徑經(jīng)過(guò)i和j。由定義6（3）可知，Cp?Cq?Ci?Cj，從而v∈Ci?Cj，與矛盾。

任何變量簇集Ck都位于Ti或Tj之一，而Ci?Cj是兩者的交界。該定理表明：（1）刪除Ci?Cj中的變量，則剩余所有變量分為不相交的兩部分；（2）這兩部分之間無(wú)約束（易知（2）是定理1的推廣）。這樣，只有Ci?Cj的賦值才會(huì)影響的賦值。該定理有如下推論（設(shè)i,j∈I，且sup(j)=i）：

推論1

證明由于，只須證明Desc(Cj)-即可。反設(shè)存在v屬于前者而不屬于后者，則必有。由于，又有，與定理2（1）矛盾。

該推論表明確定C[i]、Ci或Ci?Cj的賦值后，對(duì)以Cj為根的子樹(shù)，將得到同樣的剩余變量集。由此可給出子問(wèn)題的三種等價(jià)條件，其中第一種用于設(shè)計(jì)算法的遞歸結(jié)構(gòu)，第三種用于部分解的緩存。

現(xiàn)在給出本文的子問(wèn)題獨(dú)立性概念，表述如下：

定理3設(shè)j1＜j2＜…＜jk為i∈I的所有子結(jié)點(diǎn)。若給定C[i]中所有變量的合法賦值，則任取1≤p≠不相交，且兩者之間無(wú)約束。

證明設(shè)fp={i,jp}，則T-fp分為兩個(gè)連通片，一個(gè)由導(dǎo)出，設(shè)為，另一個(gè)設(shè)為，則必有，即，則由推論1：

再由定理2即可導(dǎo)出本命題的結(jié)論。

該定理表明：在樹(shù)分解中，當(dāng)所有祖先結(jié)點(diǎn)中所含變量已合法賦值時(shí)，對(duì)兩棵兄弟子樹(shù)各自的剩余變量進(jìn)行賦值，將是完全獨(dú)立的子問(wèn)題。若其都有與前提兼容的部分解，則可以無(wú)沖突地合并。這就為設(shè)計(jì)CSP的遞歸算法提供了依據(jù)。在C[sup(i)]合法賦值后，為求解Ci代表的子問(wèn)題（對(duì)Desc(Ci)中剩余變量賦值），可先對(duì)Ci（中剩余變量）嘗試賦值，對(duì)它的每一種（與C[sup(i)]兼容的）合法賦值，求解各子問(wèn)題Cjt(1≤t≤k)。

由推論1，子問(wèn)題Cjt的變量集Desc(Cjt)-C[i]=Desc(Cjt)-Ci?Cjt，而定理2表明，其賦值只受Ci?Cjt的賦值影響。于是，子問(wèn)題Cjt僅以Ci?Cjt的賦值為條件。若Ci的不同賦值在Ci?Cjt上投影相同，則相應(yīng)子問(wèn)題Cj只須求解一次。進(jìn)而，可建立如下緩存原理：

定理4設(shè)＜C,T>是CSP約束圖＜V,E>的樹(shù)分解，T=＜I,F>，i,j∈I，且sup(j)=i。又設(shè)變量集Y≠Y′滿足Ci?Cj?Y,Y′?V-(Desc(Cj)-C[i])。若α:Y和α′:Y′均合法，且在Ci?Cj上投影相同，則有：

（1）α在Desc(Cj)-C[i]上有合法擴(kuò)展，當(dāng)且僅當(dāng)α′在Desc(Cj)-C[i]上有合法擴(kuò)展。

（2）設(shè)αX是α在Desc(Cj)-C[i]上的合法擴(kuò)展，則αX↑(Desc(Cj)-C[i])與α′:Y′兼容。

證明（1）只證必要性，充分性類似。反設(shè)α′:Y′在Desc(Cj)-C[i]上無(wú)合法擴(kuò)展。由定理?xiàng)l件可知Desc(Cj)-C[i]與Y′不相交，且由結(jié)論（1）左端不難得出Ci?Cj和Desc(Cj)-C[i]各自有合法賦值且兩者兼容，故Desc(Cj)-C[i]與Y′-Ci?Cj之間必然存在約束。但Y′-Ci?Cj?V-(Desc(Cj)-C[i])-Ci?Cj=(V-Ci?Cj)-(Desc(Cj)-Ci?Cj)=(V-Desc(Cj))-Ci?Cj，由定理2（2）不難推出Y′-Ci?Cj與Desc(Cj)-C[i]=Desc(Cj)-Ci?Cj間無(wú)約束，矛盾。

（2）易知αX、α和α′在Ci?Cj上的投影均相同。由αX合法知該投影與αX↑(Desc(Cj)-C[i])兼容。又Y′-Ci?Cj與Desc(Cj)-C[i]不相交、無(wú)約束，故整個(gè)α′:Y′與αX↑(Desc(Cj)-C[i])也兼容。

該定理表明：不同前提下的子問(wèn)題Cj是等價(jià)的，只要前提在Ci?Cj上的投影相同，且一個(gè)前提下的部分解與另一個(gè)前提兼容。在某個(gè)前提及相應(yīng)Ci?Cj賦值下求出子問(wèn)題Cj的部分解后，可將其寫(xiě)入緩存，若在新前提下求解子問(wèn)題Cj，只要Ci?Cj的賦值相同，均可讀取緩存結(jié)果，避免重復(fù)求解。

3.2.3 WS（≠）決策的BTD算法

本節(jié)基于上述理論建立一種新的*WS（≠）算法。目前已有工作將#BTD用于WS（≠）計(jì)數(shù)[21]，但其未從理論上識(shí)別和解決前述的獨(dú)立性問(wèn)題，算法的結(jié)果構(gòu)造、搜索組織和緩存利用方式也不同于本文。下面給出本文算法的描述（因不同連通片對(duì)應(yīng)獨(dú)立的問(wèn)題，只須考慮連通約束圖）。

算法1*WS（≠）-BTD//A1

輸入：α,Ci,Ri，其中Ci是＜S,X>樹(shù)分解的當(dāng)前結(jié)點(diǎn)，α是對(duì)C[sup(i)]中所有和Ci-C[sup(i)]中部分步驟的合法賦值，而Ri是Ci-C[sup(i)]的α未賦值變量集，故Dom(α)=C[i]-Ri。

輸出：與α兼容的合法賦值β:Desc(Ci)-Dom(α)，或當(dāng)其不存在時(shí)，返回β=NULL。β可看作單變量賦值的集合，故其為?表示無(wú)剩余步驟須賦值。

初始調(diào)用為A1(α:?,C1,C1)，C1為樹(shù)分解的根。

若算法1是正確的，即其任何對(duì)滿足輸入要求的α,Ci,Ci，均可返回滿足輸出要求的β，則其對(duì)滿足Dom(α)=C[1]-C1=? 的初始調(diào)用，若返回β:Desc(Ci)-Dom(α)，即為樹(shù)中也是問(wèn)題所有變量的一個(gè)合法賦值，若返回β=NULL，上述合法賦值必?zé)o解。該*WS（≠）算法的正確性已蘊(yùn)涵其完備性。

為證明算法1正確，根據(jù)其結(jié)構(gòu)特點(diǎn)，本文將分條件按兩個(gè)值做歸納：（1）若Ri≠?，按|Ri|做歸納，其基始為Ri=? 的情況，歸納假設(shè)定義于Ri的基數(shù)為|Ri|-1的真子集；（2）若Ri=?，按Ci與其后代葉子的最小高差做歸納，基始為Ci為葉的情況，歸納假設(shè)定義于Ci的每個(gè)兒子。兩種基始情況疊加即為整個(gè)證明的基始。若忽略約束滿足要求，則任意待證情形都可還原至這一基始，只須交替向兩種歸納假設(shè)針對(duì)的情形轉(zhuǎn)化。對(duì)（1）的情況，連續(xù)轉(zhuǎn)化至對(duì)應(yīng)歸納假設(shè)，最終將變?yōu)椋?）的情況，此時(shí)若當(dāng)前結(jié)點(diǎn)Ci非葉，則向?qū)?yīng)的歸納假設(shè)轉(zhuǎn)化，將對(duì)其每個(gè)兒子，得到（1）的情形，如此交替，直至在每個(gè)葉子上都有Ri=?。而若考慮約束要求，某些中間情形可能找不到合法賦值，此時(shí)可直接判定其無(wú)解，不必還原至基始。具體的歸納證明如下：

基始。Ci為葉且Ri=? 時(shí)，須驗(yàn)證A1(α,Ci,Ri)正確返回。此時(shí)，第2行返回? 。因β的定義域Desc(Ci)-Dom(α)=Ci-(C[i]-?)=?，返回正確。

歸納步驟。對(duì)Ci非葉或Ri≠? 的情況，目標(biāo)是基于如下歸納假設(shè)，證明A1(α,Ci,Ri)正確返回：

（1）待證情形滿足Ri≠ ? 時(shí)，假設(shè)任取s∈Ri，A1(α:C[i]-(Ri-{s}),Ci,Ri-{s})正確返回。

（2）待證情形滿足Ri=? 時(shí)，若Ci為葉，則為基始情形，已驗(yàn)證成立；否則任取Cj∈subs(Ci)，假設(shè)A1(α:C[j]-(Cj-Ci),Cj,Cj-Ci)正確返回。

歸納步驟的證明如下：

若Ri≠ ?，第22～33行將尋找s∈Ri，及其與α兼容的（合法）賦值s→u。若找到，由歸納假設(shè)（1），第 30 行調(diào)用 A1(α:C[i]-(Ri-{s}),Ci,Ri-{s})將正確返回。若β≠ NULL，則與 (α:C[i]-Ri)?{s→u}兼容，且其定義域?yàn)椋?/p>

第31行為其附加s→u后返回，恰為(Desc(Ci)-Ci)?Ri的α:C[i]-Ri兼容賦值，因而正確。若窮盡UA(s)都找不到兼容的s→u，或者每次找到后第30行都返回NULL，則α:C[i]-Ri無(wú)合法擴(kuò)展，從而第 34 行返回NULL也正確。

若Ri=?，考查Ci。若其為葉，則落入基始情形。若其非葉，第4～19行對(duì)每個(gè)Cj∈subs(Ci)調(diào)用A1(αj:C[j]-(Cj-Ci),Cj,Cj-Ci)（或讀取緩存），得到βj。由歸納假設(shè)（2），調(diào)用都將正確返回（而緩存是之前的調(diào)用結(jié)果），故所得βj都是正確的。若某個(gè)βj=NULL，則α:C[i]不可能有合法擴(kuò)展，故第16行返回NULL是正確的。否則，每個(gè)βj都是Desc(Cj)-(C[j]-(Cj-Ci))的αj兼容賦值。由于C[j]-(Cj-Ci)=(C[j]-Cj)?(Ci?Cj)=(C[i]-Cj)?(Ci?Cj)（注意C[j]=C[i]?Cj）=(C[i]-Ci?Cj)?(Ci?Cj)（由定理 2（1）推導(dǎo)可知，C[i]?Cj?，有αj=α和Dom(βj)=Desc(Cj)-C[i]。由定理3，各Dom(βj)不相交，無(wú)約束，故第19行返回是（注意且Ci?C[i]）=Desc(Ci)-(C[i]-?)的α兼容賦值，是正確的。

綜合基始與歸納步驟，算法1是正確的。

算法1的時(shí)間代價(jià)分為三部分：（1）每個(gè)結(jié)點(diǎn)內(nèi)的回溯搜索（第22～32行）。（2）整體結(jié)構(gòu)上深度優(yōu)先處理相關(guān)代價(jià)，包括取下一子結(jié)點(diǎn)（第6～8行），合并子問(wèn)題部分解（第15～17行）。（3）緩存查找（第9行）和插入（第13行）。各自分析如下：

（1）由于緩存的使用，相應(yīng)于Cj?Ci的每一合法賦值，對(duì)Cj-Ci的回溯搜索至多執(zhí)行一次，故每結(jié)點(diǎn)內(nèi)的回溯搜索至多執(zhí)行一次。每個(gè)結(jié)點(diǎn)所含變量至多W+1個(gè)，其值域大小至多，又每個(gè)變量至多與|X|-1個(gè)變量互斥，每次賦值后至多驗(yàn)證min{|X|,|S|}個(gè)約束，而結(jié)點(diǎn)數(shù)為O(|S|)，故這部分的總代價(jià)為O*(|S|2×dW+1)。

（2）由于深度優(yōu)先處理可能回溯到父結(jié)點(diǎn)和重新進(jìn)入子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可多次到達(dá)，但次數(shù)不超過(guò)其父結(jié)點(diǎn)局部解空間的大小（只有父結(jié)點(diǎn)被搜索時(shí)，才可能進(jìn)入其子結(jié)點(diǎn)，而父結(jié)點(diǎn)至多執(zhí)行一次完整的回溯搜索），即為O(dW+1)次，每次到達(dá)需要取該結(jié)點(diǎn)的所有兒子，所有子問(wèn)題遞歸調(diào)用結(jié)束后執(zhí)行部分解合并，均需要O(|S|)代價(jià)，由于總結(jié)點(diǎn)數(shù)為O(|S|)，這部分的總代價(jià)為O*(|S|2×dW+1)。

（3）對(duì)樹(shù)分解每條邊對(duì)應(yīng)的割集，設(shè)一個(gè)平衡二叉查找樹(shù)作為緩存，割集大小即關(guān)鍵字比較代價(jià)，不超過(guò)，每一緩存的關(guān)鍵字?jǐn)?shù)量為O(dw)個(gè)，讀取/寫(xiě)入一個(gè)解的代價(jià)為O(|S|)，故每次查找/插入代價(jià)為O*(|S|wlb(dw))，又每個(gè)緩存可被訪問(wèn)O(dW+1)次（子結(jié)點(diǎn)到達(dá)次數(shù)），故這部分的總代價(jià)為O*(|S|×dW+1wlb(dw))=O*(|S|3×dW+1)。

綜上知算法1的時(shí)間復(fù)雜度為O*(|S|3×dW+1)，因(W+1)/|S|不超過(guò)1且可能相當(dāng)小，若d也較小則可優(yōu)于文獻(xiàn)[6]的O*(2|S|(|X|+|U|2))時(shí)間。

算法1的空間代價(jià)主要是緩存，由前述分析，每一緩存占O((w+|S|)dw)=O(|S|×dw)空間，而緩存?zhèn)€數(shù)或割集數(shù)為O(|S|)，故總的空間為O(|S|2×dw)。

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

本章對(duì)算法1的性能進(jìn)行實(shí)驗(yàn)研究。本文和對(duì)比算法均以C++實(shí)現(xiàn)，并使用GMP算術(shù)庫(kù)處理大整數(shù)。實(shí)驗(yàn)環(huán)境為：3.4 GHz Core i3 CPU、16 GB RAM、RedHat Enterprise Linux 7（64 bit）虛擬機(jī)（宿主系統(tǒng)為Windows 7），GNU C++編譯器。

二元隨機(jī)CSP的標(biāo)準(zhǔn)模型采用變量個(gè)數(shù)、值域大小、約束密度和約束緊度四個(gè)參數(shù)控制實(shí)例生成。對(duì)于*WS（≠），須增加反映變量值域差異的參數(shù)，且互斥約束兩端的變量值域即可決定其緊度（違反約束的元組數(shù)/該約束值域中所有可能的元組數(shù)）。本文通過(guò)以下參數(shù)控制實(shí)例生成：步驟集規(guī)模|S|、資源比例μ=|U|/|S|（取資源集規(guī)模|U|=|S|×μ）、約束密度ω=2|X|/(|S|×(|S|-1))（以概率ω決定在每一對(duì)步驟之間是否生成約束）、每個(gè)步驟s的授權(quán)比例k=UA(s)/|U|（從U中隨機(jī)取|U|×k個(gè)資源作為s的授權(quán)資源集UA(s)）。

實(shí)驗(yàn)1現(xiàn)有*WS（≠）算法中，文獻(xiàn)[6]（記為C13）具有最低的時(shí)間復(fù)雜度，文獻(xiàn)[10]（記為PB）具有最好的實(shí)測(cè)時(shí)間性能，本實(shí)驗(yàn)將與它們進(jìn)行性能對(duì)比，驗(yàn)證算法1的優(yōu)勢(shì)。算法1和PB兩種回溯算法的實(shí)現(xiàn)，均未采用變量排序等額外優(yōu)化。測(cè)試數(shù)據(jù)模擬較低約束密度下通常規(guī)模范圍內(nèi)的工作流，單個(gè)實(shí)例的生成規(guī)則如表1第一行所示。

首先取l=10,u=30，按規(guī)則生成400個(gè)隨機(jī)實(shí)例，對(duì)三種算法的運(yùn)行時(shí)間和峰值空間進(jìn)行測(cè)試。在5 min內(nèi)，算法1解出了全部實(shí)例，PB有1個(gè)實(shí)例未解出，C13只解出了95個(gè)實(shí)例。三者在解出實(shí)例上的平均時(shí)間：算法1為688 μs，PB為1 199 μs，而C13為52 s。C13最多只能求解|S|=17的實(shí)例，而算法1和PB均可求解|S|=30的實(shí)例。C13在95個(gè)解出實(shí)例上的最低運(yùn)行時(shí)間為448 ms，而算法1和PB在同樣實(shí)例上的最大運(yùn)行時(shí)間分別為500 μs和391 μs。盡管C13有最低的時(shí)間復(fù)雜度，但其實(shí)際時(shí)間性能與后二者差距很大。一個(gè)重要原因是C13基于組合計(jì)數(shù)而非搜索策略，且空間代價(jià)為指數(shù)級(jí)，僅空間初始化就要相當(dāng)時(shí)間，后二者均為回溯搜索，有機(jī)會(huì)快速找到一個(gè)解。在各自解出實(shí)例上的峰值空間：算法1為13.0～13.1 MB，平均13.0 MB，PB始終為12.8 MB，而C13為56.7 MB～14 GB，平均2.9 GB，其最大值已接近測(cè)試機(jī)物理內(nèi)存容量。實(shí)際上，C13進(jìn)程在未解出實(shí)例上往往運(yùn)行不足5 min，即因內(nèi)存分配失敗被殺死。根據(jù)上述實(shí)驗(yàn)，算法1和PB在實(shí)測(cè)時(shí)間和空間性能上遠(yuǎn)優(yōu)于C13，而兩者之間相對(duì)接近，算法1的解出率和平均時(shí)間較優(yōu)，而空間占用略高。

Table 1 Generating rules for test instance表1 測(cè)試實(shí)例生成規(guī)則

進(jìn)一步取l=31,u=100，按規(guī)則生成600個(gè)實(shí)例，對(duì)算法1和PB進(jìn)行擴(kuò)展測(cè)試。算法1仍然在5 min內(nèi)解出全部實(shí)例，PB的未解出實(shí)例為26個(gè)。兩者在解出實(shí)例上的平均時(shí)間，算法1為23 ms，PB為406 ms。算法1的解出率和平均時(shí)間取得了更大的優(yōu)勢(shì)。在共同解出實(shí)例上的峰值空間，算法1為13.0～18.9 MB，平均14.3 MB，PB為12.8～13.2 MB，平均12.8 MB。算法1的空間性能仍然略弱于PB。

基于前述1 000個(gè)實(shí)例的測(cè)試結(jié)果，圖1給出了算法1和PB在973個(gè)共同解出實(shí)例上的運(yùn)行時(shí)間（μs）對(duì)比。圖中每個(gè)點(diǎn)對(duì)應(yīng)一個(gè)實(shí)例，其橫、縱坐標(biāo)分別為算法1和PB的運(yùn)行時(shí)間。以x=1 500和y=1 500將該圖分為4個(gè)象限。在第4象限的實(shí)例中，PB均優(yōu)于算法1，不過(guò)最多只快2.9 ms。在第3象限的大部分實(shí)例中，PB算法占優(yōu)，但最多只比算法1快1.1 ms。在第2象限的全部和第1象限的多數(shù)實(shí)例上，算法 1 優(yōu)于 PB，比后者快 32 μs～31 s，平均約158 ms，在剩余實(shí)例上，PB比算法1快1 μs～83 ms，平均約18 ms。相對(duì)于在另外兩個(gè)象限的劣勢(shì)，算法1在這兩個(gè)象限取得了非常顯著的優(yōu)勢(shì)。對(duì)973個(gè)實(shí)例整體進(jìn)行統(tǒng)計(jì)，算法1的平均時(shí)間為13 ms，而PB的平均時(shí)間為240 ms，算法1比PB快17倍以上。從分布情況來(lái)看，算法1的執(zhí)行時(shí)間集中在較小的區(qū)間內(nèi)，而PB的執(zhí)行時(shí)間更為分散。統(tǒng)計(jì)可知，算法1的標(biāo)準(zhǔn)差與平均值之比為1.6，而PB為23.6，算法1圍繞均值的平均波動(dòng)幅度比PB小13倍以上。

綜合實(shí)驗(yàn)1的結(jié)果可知：算法1的解出率、時(shí)間和空間性能均遠(yuǎn)優(yōu)于C13；算法1較PB有略高的5 min解出率，在解出實(shí)例上有13倍以上的平均時(shí)間和穩(wěn)定性優(yōu)勢(shì)，其空間性能略弱于后者。

Fig.1 Comparison between runtime ofA1 and PB圖1 算法1與PB的執(zhí)行時(shí)間對(duì)比

實(shí)驗(yàn)2實(shí)驗(yàn)1表明了算法1在較低約束密度下的優(yōu)勢(shì)，下面進(jìn)一步考查約束密度增加對(duì)其時(shí)間性能的影響，即固定|S|和μ，觀察算法1執(zhí)行時(shí)間隨ω的變化。實(shí)例生成規(guī)則如表1第二行所示，對(duì)每一組|S|.μ.ω，重復(fù)生成30個(gè)實(shí)例，取其中30 min解出實(shí)例的平均時(shí)間作為測(cè)試結(jié)果，以消除具體約束分布造成的偶然性。

在生成的4組960個(gè)實(shí)例上執(zhí)行算法1，得到如圖2所示的4條結(jié)果曲線。每條曲線中，運(yùn)行時(shí)間均隨約束密度而增加。|S|=200且μ=35的曲線，在ω=75時(shí)出現(xiàn)了比較明顯的抬升。該點(diǎn)的運(yùn)行時(shí)間約為8 s，是18個(gè)重復(fù)實(shí)例的平均值。該配置集中了960個(gè)實(shí)例的所有超時(shí)情形，有12個(gè)實(shí)例未在30 min內(nèi)解出，而其余所有解出實(shí)例的最大耗時(shí)僅為8 s左右。這就表明，當(dāng)約束密度大到一定程度時(shí)，對(duì)于步驟數(shù)量很大的實(shí)例，算法1的時(shí)間性能可能會(huì)發(fā)生惡化。

Fig.2 Runtime changes with constraint density圖2 運(yùn)行時(shí)間隨約束密度的變化

圖3給出了上述4組實(shí)例樹(shù)分解寬度W的變化情況，每條曲線的走勢(shì)與圖2中對(duì)數(shù)縱坐標(biāo)下對(duì)應(yīng)的曲線大體相仿，兩張圖中4條曲線之間的差距情況也基本一致。這說(shuō)明當(dāng)約束密度ω增加時(shí)，算法1時(shí)間效率的降低主要是由W增加引起的。進(jìn)一步觀察可知，當(dāng)ω較小時(shí)，圖2中每條曲線的增長(zhǎng)比較接近甚至慢于圖3中對(duì)應(yīng)曲線，而當(dāng)約束密度較大時(shí)，圖2中曲線的增長(zhǎng)快于圖3中對(duì)應(yīng)曲線，甚至末端明顯抬升。主要原因是W達(dá)到一定大小前，算法可能很快找到一個(gè)解，之后由于解空間指數(shù)級(jí)膨脹，這種機(jī)會(huì)性急劇降低，使算法效率更接近其理論最壞情形（上述每組實(shí)例的資源數(shù)均大于10，其最壞情形都是比10W+1更陡峭的曲線），圖2曲線的增長(zhǎng)速度也隨之顯現(xiàn)。故約束密度較低時(shí)，W的值和算法1的時(shí)間復(fù)雜度更容易受到控制，而實(shí)際性能也更容易利用回溯搜索的機(jī)會(huì)性取得好的表現(xiàn)。

Fig.3 Tree-decomposition width changes with constraint density圖3 樹(shù)分解寬度隨約束密度的變化

5 結(jié)束語(yǔ)

本文根據(jù)工作流的低約束密度特征，利用樹(shù)分解回溯技術(shù)研究性能平衡的WS（≠）決策算法，從理論上解決了該技術(shù)的完備獨(dú)立分解問(wèn)題，建立了相應(yīng)的緩存原理，設(shè)計(jì)和證明了正確的算法。算法時(shí)間復(fù)雜度為O*(|S|3×dW+1)，而(W+1)/|S|≤1可取得相當(dāng)小的值，相對(duì)于現(xiàn)有算法時(shí)間復(fù)雜度均以|S|為指數(shù)的情況，一定條件下具有理論優(yōu)勢(shì)。實(shí)驗(yàn)表明，本文算法有良好的時(shí)間性能，明顯優(yōu)于現(xiàn)有實(shí)測(cè)性能最好和時(shí)間復(fù)雜度最低的算法。盡管其空間復(fù)雜度為指數(shù)級(jí)，但實(shí)測(cè)空間性能也有較好表現(xiàn)。