基于Petri網(wǎng)局部性的極大沖突集枚舉算法

潘 理,鄭 紅,劉顯明,楊 勃

(1.湖南理工學(xué)院信息與通信工程學(xué)院,湖南岳陽(yáng) 414006;2.華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237;3.江西省電力公司信息通信分公司,江西南昌 330077)

?

基于Petri網(wǎng)局部性的極大沖突集枚舉算法

潘 理1,鄭 紅2,劉顯明3,楊 勃1

(1.湖南理工學(xué)院信息與通信工程學(xué)院,湖南岳陽(yáng) 414006;2.華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237;3.江西省電力公司信息通信分公司,江西南昌 330077)

沖突是Petri網(wǎng)研究的重要主題.目前Petri網(wǎng)沖突研究主要集中于沖突建模和沖突消解策略,而對(duì)沖突問(wèn)題本身的計(jì)算復(fù)雜性卻很少關(guān)注.提出Petri網(wǎng)的沖突集問(wèn)題,并證明沖突集問(wèn)題是NP(Non-deterministic Polynomial)完全的.提出極大沖突集動(dòng)態(tài)枚舉算法,該算法基于當(dāng)前標(biāo)識(shí)的所有極大沖突集,利用Petri網(wǎng)實(shí)施局部性,僅計(jì)算下一標(biāo)識(shí)中受局部性影響的極大沖突集,從而避免重新枚舉所有極大沖突集.該算法時(shí)間復(fù)雜度為O(m2n),m是當(dāng)前標(biāo)識(shí)的極大沖突集數(shù)目,n是變遷數(shù).最后證明自由選擇網(wǎng)、非對(duì)稱選擇網(wǎng)的極大沖突集枚舉算法復(fù)雜度可降至O(n2).極大沖突集枚舉算法研究將為Petri網(wǎng)沖突問(wèn)題的算法求解提供理論參考.

Petri網(wǎng);沖突集問(wèn)題;NP(Non-deterministic Polynomial)完全性;極大沖突集枚舉算法

電子學(xué)報(bào)URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.013

1 引言

沖突是Petri網(wǎng)理論的重要概念.沖突的本質(zhì)是資源競(jìng)爭(zhēng)[1].當(dāng)多個(gè)沖突變遷競(jìng)爭(zhēng)有限資源,若其中一個(gè)獲得資源,其它與之沖突的變遷就會(huì)喪失使能.若變遷集合中的任意兩個(gè)變遷都是沖突的,稱這個(gè)集合為沖突集.現(xiàn)有Petri網(wǎng)沖突研究主要集中于沖突處理策略和沖突問(wèn)題建模.經(jīng)典Petri網(wǎng)采用不確定選擇策略處理變遷沖突[2];優(yōu)先級(jí)Petri網(wǎng)通過(guò)設(shè)置優(yōu)先級(jí)來(lái)解決沖突[3];時(shí)間Petri網(wǎng)則利用時(shí)間競(jìng)爭(zhēng)來(lái)處理變遷之間的沖突[4];謂詞/變遷網(wǎng)通過(guò)謂詞來(lái)控制沖突變遷的實(shí)施[5];隨機(jī)Petri網(wǎng)則引入某種實(shí)施概率分布來(lái)處理變遷間的沖突[6,7].在建模方面,近期Zeng等利用Petri網(wǎng)方法探討應(yīng)急響應(yīng)過(guò)程中資源沖突偵測(cè)和消解[8];Tian等利用時(shí)間Petri網(wǎng)的時(shí)間約束特性處理實(shí)時(shí)系統(tǒng)的沖突問(wèn)題[9];Popescu等利用Petri網(wǎng)方法解決面向服務(wù)制造系統(tǒng)調(diào)度過(guò)程中的資源沖突[10].

上述研究注重沖突問(wèn)題建模及沖突消解策略,而對(duì)沖突問(wèn)題本身的計(jì)算復(fù)雜性卻很少關(guān)注.現(xiàn)實(shí)系統(tǒng)中的沖突情況往往非常復(fù)雜,枚舉系統(tǒng)的極大沖突集,對(duì)于全面了解系統(tǒng)沖突、尋求沖突消解方案是非常重要的.因此,對(duì)沖突集問(wèn)題復(fù)雜度進(jìn)行界定,并提出基于Petri網(wǎng)特征的枚舉算法,將為Petri網(wǎng)沖突問(wèn)題的計(jì)算求解提供一種探索途徑.目前已有大量文獻(xiàn)研究Petri網(wǎng)的死鎖問(wèn)題、活性問(wèn)題、可達(dá)性問(wèn)題、合法實(shí)施序列問(wèn)題、合成問(wèn)題、步問(wèn)題等,得出了一系列有價(jià)值的計(jì)算復(fù)雜性結(jié)論[11-16].但這些結(jié)論并沒(méi)涉及沖突集問(wèn)題.本文嘗試以沖突集問(wèn)題為研究對(duì)象,通過(guò)從已知NP完全問(wèn)題歸約到?jīng)_突集問(wèn)題,證明沖突集問(wèn)題的NP完全性;然后利用Petri網(wǎng)實(shí)施的局部性特征,提出動(dòng)態(tài)枚舉算法,降低極大沖突集枚舉的計(jì)算成本,為沖突集問(wèn)題的復(fù)雜性研究提供有益參考.

2 沖突集問(wèn)題

2.1 基本定義

用N表示自然數(shù)集{0,1,2,…},用Z+表示正整數(shù)集.

定義1[1]一個(gè)Petri網(wǎng)是一個(gè)四元組Σ=(P,T,F,M0),其中:

(1)P是庫(kù)所集;(2)T是變遷集,且P∩T=?;(3)F?(P×T)∪(T×P)是流關(guān)系;(4)M0:P→N是初始標(biāo)識(shí).

標(biāo)識(shí)M可表示為一個(gè)|P|元向量,第i個(gè)元素表示庫(kù)所pi中的令牌數(shù).流關(guān)系F可表示為特征函數(shù)的形式,即F:(P×T)∪(T×P)→{0,1}.用·p={t|(t,p)∈F}和p·={t|(p,t)∈F}表示庫(kù)所p的輸入變遷集和輸出變遷集;類似的,用·t和t·表示變遷t的輸入庫(kù)所集和輸出庫(kù)所集.

定義2[1]一個(gè)變遷t∈T在標(biāo)識(shí)M是使能的,當(dāng)且僅當(dāng)?p∈P,F(p,t)≤M(p).用En(M)表示標(biāo)識(shí)M下所有使能變遷的集合.

定義3[1]如果tf在標(biāo)識(shí)M是使能的,那么tf可以實(shí)施并產(chǎn)生一個(gè)新的后繼標(biāo)識(shí)M′,且?p∈P,M′(p)=M(p)-F(p,tf)+F(tf,p).

定義4[1]給定t1,t2∈En(M),若?p∈P,使F(p,t1)+F(p,t2)>M(p),則稱變遷t1和t2在標(biāo)識(shí)M是(有效)沖突的,用t1Mt2表示.

定義5 給定一個(gè)變遷集U?T,如果?t1,t2∈U,有t1Mt2,則U是標(biāo)識(shí)M的一個(gè)沖突集.若不存在其它沖突集U′,使U?U′,則稱U是M的極大沖突集.用MCS(M)表示在標(biāo)識(shí)M下的所有極大沖突集的集合.

2.2 沖突集問(wèn)題

定義6[17]復(fù)雜類P表示用確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可解決的判定問(wèn)題集,NP表示用非確定型圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可解決的判定問(wèn)題集.

定義7[17]若判定問(wèn)題A屬于NP,且所有其它NP問(wèn)題都能多項(xiàng)式時(shí)間多一歸約到A,則稱A是NP完全的.

引理1[17]對(duì)于判定問(wèn)題A,若存在NP完全問(wèn)題B,使B多項(xiàng)式時(shí)間多一歸約到A,則A是NP困難的.若A是NP困難的且A∈NP,則A是NP完全的.

定義8 (沖突集問(wèn)題,CS)給定Petri網(wǎng)Σ=(P,T,F,M0),標(biāo)識(shí)M∈RS(M0)和正整數(shù)k≤|T|,問(wèn)在標(biāo)識(shí)M是否包含變遷數(shù)至少為k的沖突集?

接下來(lái),通過(guò)從已知NP完全問(wèn)題(團(tuán)問(wèn)題)歸約到?jīng)_突集問(wèn)題,來(lái)證明沖突集問(wèn)題的NP完全性.

設(shè)G=(V,E)是簡(jiǎn)單無(wú)向圖,這里V是頂點(diǎn)集,E是邊集.給定一個(gè)頂點(diǎn)子集A?V,用G(A)表示由A誘導(dǎo)的子圖.

定義9[18]給定圖G=(V,E),如果?u,w∈V,有(u,w)∈E,則稱G是完全的.若G(Q)是完全圖,則稱Q是G的一個(gè)團(tuán).

定義10[18](團(tuán)問(wèn)題,CLIQUE)給定簡(jiǎn)單無(wú)向圖G=(V,E)和正整數(shù)k≤|V|,問(wèn)G是否包含基數(shù)至少為k的團(tuán)?

引理2[18]團(tuán)問(wèn)題是NP完全的.

定理1 沖突集問(wèn)題是NP完全的.

證明 (1)首先證明沖突集問(wèn)題是NP困難的.

考慮從團(tuán)問(wèn)題多項(xiàng)式時(shí)間多一歸約到?jīng)_突集問(wèn)題.設(shè)簡(jiǎn)單無(wú)向圖G=(V,E)和正整數(shù)s是團(tuán)問(wèn)題的一個(gè)實(shí)例,要構(gòu)造沖突集問(wèn)題的一個(gè)實(shí)例:Petri網(wǎng)Σ、標(biāo)識(shí)M和正整數(shù)k,使Σ在標(biāo)識(shí)M有一個(gè)大小至少為k的沖突集當(dāng)且僅當(dāng)G有一個(gè)大小至少為s的團(tuán).按照下面的方式進(jìn)行構(gòu)造:

(ⅰ)vi∈V當(dāng)且僅當(dāng)ti∈T,即Petri網(wǎng)Σ中的每個(gè)變遷t1,t2,…,tn對(duì)應(yīng)圖G中的每個(gè)頂點(diǎn)v1,v2,…,vn.

(ⅱ)(vi,vj)∈E當(dāng)且僅當(dāng)pij∈P∧M(pij)=1∧F(pij,ti)=1∧F(pij,tj)=1.換句話說(shuō),兩頂點(diǎn)vi和vj相鄰當(dāng)且僅當(dāng)ti與tj共享輸入庫(kù)所pij,庫(kù)所pij中放置1個(gè)令牌,且弧(pij,ti)和(pij,tj)的權(quán)值均為1.

(ⅲ)vi是孤立點(diǎn)當(dāng)且僅當(dāng)pi∈P∧M(pi)=1∧F(pi,ti)=1.即vi是孤立點(diǎn)當(dāng)且僅當(dāng)ti有一個(gè)輸入庫(kù)所pi,庫(kù)所pi中放置1個(gè)令牌,且弧(pi,ti)的權(quán)值為1.

(ⅳ)k=s.

從上面構(gòu)造可以看出,Petri網(wǎng)Σ的每個(gè)變遷對(duì)應(yīng)圖G的每個(gè)頂點(diǎn),且每個(gè)變遷在M都使能;兩個(gè)變遷共享一個(gè)庫(kù)所當(dāng)且僅當(dāng)圖G中對(duì)應(yīng)的兩個(gè)頂點(diǎn)是相鄰的.如圖1(a)所示,圖G有4個(gè)頂點(diǎn)v1,v2,v3,v4,其中包含一個(gè)s=3的團(tuán){v1,v2,v3}.通過(guò)上述構(gòu)造得到Petri網(wǎng)Σ和標(biāo)識(shí)M,如圖1(b)所示,Σ有4個(gè)變遷t1,t2,t3,t4,4個(gè)庫(kù)所p12,p13,p23,p4,每個(gè)庫(kù)所中都有1個(gè)令牌,4個(gè)變遷均使能.容易看出,Petri網(wǎng)Σ在M包含一個(gè)k=3的沖突集{t1,t2,t3}.

現(xiàn)在證明Petri網(wǎng)Σ在標(biāo)識(shí)M有一個(gè)大小至少為k的沖突集當(dāng)且僅當(dāng)G有一個(gè)大小至少為s的團(tuán).Q是G的一個(gè)團(tuán)且|Q|≤s,當(dāng)且僅當(dāng)?vi,vj∈Q,(vi,vj)∈E;由上面構(gòu)造步驟,當(dāng)且僅當(dāng)?shù)玫綄?duì)應(yīng)的變遷集U,|U|=|Q|,U?En(M)且?ti,tj∈U,F(pij,ti)+F(pij,tj)>M(pij);即U在標(biāo)識(shí)M是一個(gè)沖突集且|U|≤k.

進(jìn)一步分析這是一個(gè)多項(xiàng)式時(shí)間的構(gòu)造.設(shè)|V|=n,則V,E和k的輸入長(zhǎng)度分別為O(n),O(n2)和O(n),故實(shí)例的輸入總長(zhǎng)度是O(n2).構(gòu)造步(ⅰ)根據(jù)頂點(diǎn)集V確定變遷集T,故|T|=n;構(gòu)造步(ⅱ)和(ⅲ)根據(jù)邊集E確定庫(kù)所集P,故|P|=O(n2);標(biāo)識(shí)M的規(guī)模是|P|=O(n2),流關(guān)系F的規(guī)模是|P‖T|=O(n3).因此整個(gè)構(gòu)造需時(shí)間O(n3),即從CLIQUE能多項(xiàng)式時(shí)間歸約到?jīng)_突集問(wèn)題.由于CLIQUE是NP完全的(引理2),根據(jù)引理1,沖突集問(wèn)題是NP困難的.

(2)證明沖突集問(wèn)題屬于NP.

對(duì)于Petri網(wǎng)Σ,對(duì)任何標(biāo)識(shí)M∈RS(M0),給出一個(gè)驗(yàn)證沖突集問(wèn)題的非確定型算法(見(jiàn)算法1).

假設(shè)|P|=m,|T|=n.則P,T,F,M和k的長(zhǎng)度分別是O(m),O(n),O(mn),O(m)和O(n),故輸入的總長(zhǎng)度是O(mn).U的長(zhǎng)度是O(n),驗(yàn)證(ⅰ)需時(shí)間O(n),驗(yàn)證(ⅱ)需時(shí)間O(mn2),故驗(yàn)證(ⅰ)和(ⅱ)需時(shí)間O(mn2).這是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證沖突集問(wèn)題的非確定型算法.因此沖突集問(wèn)題屬于NP.

綜合(1)和(2)的證明,根據(jù)引理1,沖突集問(wèn)題是NP完全的.證畢.

3 極大沖突集枚舉算法

3.1 極大沖突集枚舉問(wèn)題

定義11[17]復(fù)雜類FP表示用確定型圖靈機(jī)在多項(xiàng)式時(shí)間可解決的函數(shù)問(wèn)題集.

定義12 (極大沖突集枚舉問(wèn)題)給定Petri網(wǎng)Σ=(P,T,F,M0)和標(biāo)識(shí)M∈RS(M0),求Petri網(wǎng)Σ在標(biāo)識(shí)M的所有極大沖突集.

Petri網(wǎng)的極大沖突集枚舉問(wèn)題,可以使用已有的極大團(tuán)枚舉算法來(lái)求解.不幸的是,極大團(tuán)枚舉問(wèn)題是一個(gè)已知的NP困難問(wèn)題.求解這個(gè)問(wèn)題最有效的算法是由Bron和Kerbosch提出的分支限界算法[19],文獻(xiàn)[20]證明這種算法在最壞情況下的時(shí)間復(fù)雜度為O(nn/3).幸運(yùn)的是,Petri網(wǎng)的實(shí)施具有局部性特征.每一次變遷實(shí)施僅僅改變與該變遷相關(guān)的前集和后集.因此,每一次變遷實(shí)施之后,并不需要重新生成所有的極大沖突集,而只需考慮受實(shí)施變遷局部環(huán)境影響的那些極大沖突集,這無(wú)疑將降低極大沖突集枚舉問(wèn)題的計(jì)算復(fù)雜度.3.2 極大沖突集枚舉算法

接下來(lái)討論極大沖突集枚舉問(wèn)題的算法求解.為了簡(jiǎn)化算法描述,我們假設(shè)Petri網(wǎng)是安全的.用MCS(M,ti)表示在標(biāo)識(shí)M下包含變遷ti的極大沖突集的集合.進(jìn)一步,用MCS(M,S)表示包含S中所有變遷的極大沖突集的集合,即這些極大沖突集均包含變遷子集S.

Petri網(wǎng)變遷實(shí)施可分為兩步,第一步根據(jù)流關(guān)系,從變遷的輸入庫(kù)所中取出相應(yīng)數(shù)量的令牌;第二步根據(jù)流關(guān)系,將相應(yīng)數(shù)量的令牌放置到變遷的輸出庫(kù)所.第一步可能使某些原來(lái)沖突的變遷變?yōu)椴粵_突,第二步可能新增一些沖突關(guān)系.下面根據(jù)影響沖突關(guān)系變化的兩個(gè)步驟,定義兩個(gè)相應(yīng)的基本操作:

(1)操作del(M,t):執(zhí)行M-F(·,t),刪除不再?zèng)_突的關(guān)系；(2)操作add(M,t):執(zhí)行M-F(·,t)+F(t,·),添加新的沖突關(guān)系.

用Dis(M,t)=En(M)En(M-F(·,t))在標(biāo)識(shí)M實(shí)施t后喪失使能的變遷集.操作del(M,t)如算法2所示.對(duì)標(biāo)識(shí)M下的每個(gè)極大沖突集c,在標(biāo)識(shí)M-F(·,t),若c包含非使能變遷,則刪除非使能變遷.再判斷c是否包含在其它極大沖突集中,若包含,則說(shuō)明c不是標(biāo)識(shí)M-F(·,t)的極大沖突集,刪除c.

設(shè)|T|=n,|MCS(M)|=m.變遷t的實(shí)施通常只會(huì)影響少量極大沖突集,但最壞情況下,可能涉及絕大多數(shù)極大沖突集.因此,求解MCS(M,c)通常需O(n),但最壞情況下需O(mn).若循環(huán)m次,則該操作的時(shí)間復(fù)雜度通常為O(mn),最壞情況下為O(m2n).

用Newly(M,t)=En(M′)En(M-F(·,t))表示在新標(biāo)識(shí)M′=M-F(·,t)+F(t,·)新使能的變遷集合.操作add(M,t)如算法3所示.對(duì)每個(gè)新使能的變遷ti,若ti不與任何極大沖突集相沖突,則ti獨(dú)自構(gòu)成極大沖突集;若ti與某個(gè)極大沖突集c的所有變遷沖突,則ti并入c;若ti與極大沖突集c的部分變遷沖突,且這部分變遷不是其它極大沖突集的子集,則ti與部分變遷構(gòu)成新的極大沖突集.

設(shè)|T|=n,|MCS(M)|=m,|Newly(M,t)|=k.外層for循環(huán)k次,內(nèi)層for循環(huán)m次,內(nèi)層循環(huán)體通常需O(n);最壞情況下變遷實(shí)施影響多數(shù)極大沖突集,則需O(mn).故整個(gè)算法通常情況需O(kmn),最壞情況下需O(km2n).極大沖突集動(dòng)態(tài)枚舉算法enum(M,t)如算法4所示,算法思路如下:若在標(biāo)識(shí)M實(shí)施變遷t,首先使用del(M,t)從所有極大沖突集中刪除喪失使能的變遷,計(jì)算得到標(biāo)識(shí)M-F(·,t)的極大沖突集;然后在標(biāo)識(shí)M-F(·,t)+F(t,·),對(duì)所有新增使能變遷,使用add(M,t)添加新的沖突關(guān)系,得到新標(biāo)識(shí)下所有極大沖突集.

由于新使能變遷數(shù)k通常遠(yuǎn)小于變遷數(shù)n,根據(jù)del和add操作的復(fù)雜度分析,極大沖突集動(dòng)態(tài)枚舉算法的時(shí)間復(fù)雜度通常情況為O(mn),最壞情況下需O(m2n).下面舉例說(shuō)明極大沖突集動(dòng)態(tài)枚舉算法.如圖2所示.

在初始標(biāo)識(shí)M0=(1 1 1 0 1 0),En(M0)={t1,t2,t3,t4,t7},使用add(M0,λ)得到MCS(M0)={{t1,t2},{t2,t3},{t4},{t7}},這里λ是空變遷.

4 特殊子問(wèn)題

下面介紹三種典型的特殊子網(wǎng):自由選擇網(wǎng)、擴(kuò)展自由選擇網(wǎng)和非對(duì)稱選擇網(wǎng).

定義13[2]給定Petri網(wǎng)Σ=(P,T,F,M0),且所有弧的權(quán)值為1.

已經(jīng)證明,這三種子網(wǎng)具有包含關(guān)系:FC?EFC?AC[7].因此,從AC獲得的結(jié)論,對(duì)FC和EFC仍是有效的.定義變遷集T上的結(jié)構(gòu)沖突關(guān)系R={(t1,t2)∈T2|·t1∩·t2≠?}.

定理2 對(duì)于非對(duì)稱選擇網(wǎng),結(jié)構(gòu)沖突關(guān)系R是等價(jià)關(guān)系.

證明 ?t∈T,有·t∩·t≠?,即(t,t)∈R,故R是自反的.

?t1,t2∈T,若(t1,t2)∈R,即·t1∩·t2≠?,則·t2∩·t1≠?,即(t2,t1)∈R,故R是對(duì)稱的.

因此R是等價(jià)關(guān)系.證畢.

用[t]={t(|t∈T∧(t,t′)∈R}表示t關(guān)于R的等價(jià)類.

定理3 若t是AC的一個(gè)變遷,則?p∈·t,使p·=[t].

證明 根據(jù)AC的定義,?p′,P∈·t,有p′·?p·或p·?p′·,故?是一個(gè)全序關(guān)系.由于·t是有限集,故必有最大元,不妨設(shè)為p·.又?ti∈ [t],有·t∩·ti≠?,不妨設(shè)pi∈·t∩·ti,于是t∈p·∩pi·,故pi·?p·或p·?pi·.由于p·是·t上關(guān)于?的最大元,即有pi·?p·,故得ti∈p·.于是p·? [t].

假設(shè)?ti∈p·但ti[t],則有p∈·t∩·ti,即(t,ti)∈R,于是有ti∈[t],矛盾.因此,p·= [t].證畢.

依據(jù)等價(jià)關(guān)系R,可以將變遷集劃分成互不相交的子集,每個(gè)子集就是一個(gè)等價(jià)類.因此,每個(gè)變遷僅屬于一個(gè)等價(jià)類.

定理4 若t∈En(M),則(·t)·∩En(M)是極大沖突集.

證明 由定理3可知,(·t)·是t關(guān)于R的等價(jià)類[t],即等價(jià)類中的變遷相互沖突,因此(·t)·∩En(M)是沖突集;又[t]中變遷不屬于任何其他等價(jià)類,因此(·t)·∩En(M)是極大沖突集.證畢.

定理5 對(duì)于非對(duì)稱選擇網(wǎng),求解極大沖突集枚舉問(wèn)題的時(shí)間復(fù)雜度為O(n2),這里|T|=n.

證明 非對(duì)稱選擇網(wǎng)的極大沖突集枚舉算法如算法5所示.首先算法初始化MCS(M)為空集.然后求出每個(gè)變遷的關(guān)于有效沖突關(guān)系R的等價(jià)類,每個(gè)等價(jià)類即為一個(gè)極大沖突集.

先證明算法的正確性.

(ⅰ)由于En(M)是有限集,故for循環(huán)的次數(shù)是有限的.它根據(jù)等價(jià)類產(chǎn)生極大沖突集,因此for循環(huán)執(zhí)行完成后,極大沖突集的數(shù)目不超過(guò)|En(M)|.因此算法一定會(huì)終止.

(ⅱ)根據(jù)定理4,對(duì)任何ti∈En(M),(·ti)·∩En(M)是一個(gè)極大沖突集.由定理2和定理3可知,根據(jù)沖突關(guān)系R,可以將En(M)中所有變遷劃分到不同的等價(jià)類(極大沖突集),且每個(gè)使能變遷對(duì)應(yīng)一個(gè)等價(jià)類(極大沖突集).在循環(huán)過(guò)程中,每得到一個(gè)等價(jià)類,就會(huì)從En(M)中刪除該等價(jià)類中所有變遷,因此,不會(huì)出現(xiàn)重復(fù)的極大沖突集.因此算法最終返回的MCS(M)一定包含所有極大沖突集.

再分析算法的復(fù)雜性.設(shè)|T|=n.循環(huán)次數(shù)不超過(guò)n,每次循環(huán)需時(shí)間O(n),因此整個(gè)算法需時(shí)間O(n2).證畢.

5 結(jié)論

沖突的本質(zhì)是系統(tǒng)資源的競(jìng)爭(zhēng),對(duì)沖突問(wèn)題的研究是Petri網(wǎng)的重要主題之一.本文提出Petri網(wǎng)的沖突集問(wèn)題,并利用Petri網(wǎng)的實(shí)施局部性,提出極大沖突集枚舉動(dòng)態(tài)算法.文章的主要結(jié)論有:(1)Petri網(wǎng)的沖突集問(wèn)題是NP完全的;(2)所提極大沖突集枚舉算法的時(shí)間復(fù)雜度為O(m2n),其中m是當(dāng)前標(biāo)識(shí)的極大沖突集數(shù)目,n是變遷數(shù);(3)極大沖突集枚舉問(wèn)題對(duì)自由選擇網(wǎng)、非對(duì)稱選擇網(wǎng)的復(fù)雜度為O(n2).下階段工作將運(yùn)用上述研究結(jié)論,探索混合語(yǔ)義時(shí)間Petri網(wǎng)模型的調(diào)度策略[21],處理調(diào)度過(guò)程中面臨的資源沖突問(wèn)題,并應(yīng)用于柔性制造系統(tǒng)、工作流系統(tǒng)的調(diào)度問(wèn)題研究.

[1]Girault C,Valk R.Petri Nets for Systems Engineering:A Guide to Modeling,Verification,and Applications[M].Berlin:Springer-Verlag,2013.

[2]Murata T.Petri nets:Properties,Analysis and Applications[J].Proceedings of the IEEE,1989,77(4):541-580.

[3]Yen H C.Priority conflict-free Petri nets[J].Acta informatica,1998,35(8):673-688.

[4]Merlin P M,et al.Recoverability of communication protocols-Implications of a theoretical study[J].IEEE Transactions on Communications,1976,24(9):1036-1043.

[5]Genrich H J.Predicate/Transition Nets[M].Berlin:Springer-Verlag Petri Nets:Central Models and Their Properties,1987.

[6]林闖.隨機(jī) Petri 網(wǎng)和系統(tǒng)性能評(píng)價(jià)[M],北京:清華大學(xué)出版社,2009.

[7]Balbo G.Introduction to Stochastic Petri Nets[M].Berlin:Springer-Verlag Lectures on Formal Methods and PerformanceAnalysis,2001.

[8]Zeng Q,Liu C,Duan H.Resource conflict detection and removal strategy for nondeterministic emergency response processes using Petri nets[J].Enterprise Information Systems,2015:1-22.

[9]Tian Z,Zhang Z D,Ye Y D,et al.Analysis of real-time system conflict based on fuzzy time Petri nets[J].Journal of Intelligent & Fuzzy Systems:Applications in Engineering and Technology,2014,26(2):983-991.

[10]Popescu C,Soto M C,Lastra J L M.A Petri net-based approach to incremental modelling of flow and resources in service-oriented manufacturing systems[J].International Journal of Production Research,2012,50(2):325-343.

[11]Cheng A,et al.Complexity results for 1-safe nets[J].Theoretical Computer Science,1995,147(1-2):117-136.

[12]Esparza J.Reachability in live and safe free-choice Petri nets is NP-complete[J].Theoretical Computer Science,1998,198(1):211-224.

[13]Esparza J.Decidability and Complexity of Petri Net Problems—an Introduction[M].Berlin Heidelberg Springer:Lectures on Petri Nets I:Basic Models,1998:374-428.

[14]Jiang C.Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets[J].Science in China Series:Information Sciences,2001,44(3):226-233.

[15]Badouel E,Bernardinello L,Darondeau P.The synthesis problem for elementary net systems is NP-complete[J].Theoretical Computer Science,1997,186(1):107-134.

[16]潘理,趙衛(wèi)東,王志成,等.Petri網(wǎng)的步問(wèn)題研究[J].軟件學(xué)報(bào),2009,20(3):505-514.

Li Pan,Weidong Zhao,Zhicheng Wang.On the step problem for Petri nets[J].Journal of Software,2009,20(3):505-514 (in Chinese)

[17]Papadimitriou C H.Computational Complexity[M].Chichester:John Wiley and Sons Ltd.,2003.

[18]Garey M R,Johnson D S.Computers and Intractability[M].New York:W.H.Freeman & Co Ltd,2002.

[19]Bron C,Kerbosch J.Algorithm 457:finding all cliques of an undirected graph[J].Communications of the ACM,1973,16(9):575-577.

[20]Tomita E,Tanaka A,Takahashi H.The worst-case time complexity for generating all maximal cliques and computational experiments[J].Theoretical Computer Science,2006,363(1):28-42.

[21]潘理,丁志軍,郭觀七.混合語(yǔ)義時(shí)間Petri網(wǎng)模型[J].軟件學(xué)報(bào),2011,22(6):1199-1209.

Li Pan,Zhijun Ding,Guanqi Guo.Time Petri net model with mixed semantics[J].Journal of Software,2011,22(6):1199-1209.(in Chinese)

潘 理 男,1975年出生,湖南平江人.博士,湖南理工學(xué)院副教授.研究方向?yàn)镻etri網(wǎng)、形式化建模與優(yōu)化.

E-mail:panli.hnist@gmail.com

鄭 紅(通信作者) 女,1973年出生,博士,華東理工大學(xué)副教授,美國(guó)加州大學(xué)河濱分校訪問(wèn)學(xué)者.研究方向?yàn)槠者m計(jì)算、Petri網(wǎng)應(yīng)用.

E-mail:zhenghong@ecust.edu.cn

Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets

PAN Li1,ZHENG Hong2,LIU Xian-ming3,YANG Bo1

(1.SchoolofInformationandCommunicationEngineering,HunanInstituteofScienceandTechnology,Yueyang，Hunan414006,China;2.InformationScienceandEngineeringCollege,EastChinaUniversityofScienceandTechnology,Shanghai,200237China;3.InformationandCommunicationBranch,JiangxiElectricPowerCompany,Nanchang,Jiangxi330077,China)

Conflict is an essential concept in Petri net theory.The existing research focuses on the modelling and resolution strategies of conflict problems,but less on the computational complexity of the problems theirselves.In this paper,we propose the conflict set problem for Petri nets,and prove that the conflict set problem is NP-complete.Furthermore,we present a dynamic algorithm for the maximal conflict set enumeration.Our algorithm only computes those conflict sets that are affected by local firing,which avoids enumerating all maximal conflict sets at each marking.The algorithm needs time O(m2n) where m is the number of maximal conflict sets at the current marking and n is the number of transitions.Finally,we show that the maximal conflict set enumeration problem can be solved in O(n2) for free-choice nets and asymmetric choice nets.The results on complexity of thel conflict set problem provide a theoretical reference for solving conflict problems of Petri nets.

Petri nets;conflict set problem;NP completeness;maximal conflict set enumeration algorithm

2015-05-12;

2015-11-09;責(zé)任編輯:馬蘭英

國(guó)家自然科學(xué)基金(No.61473118);湖南省教育廳科學(xué)研究重點(diǎn)項(xiàng)目(No.15A079);湖南省科技計(jì)劃項(xiàng)目(No.2014GK3026);江西省電力公司科技項(xiàng)目(No.5218351400A1)

TP301

A

0372-2112 (2016)08-1858-06