基于時(shí)延peri網(wǎng)求解網(wǎng)絡(luò)最短路的仿真方法

基于時(shí)延peri網(wǎng)求解網(wǎng)絡(luò)最短路的仿真方法

網(wǎng)絡(luò)中的最短面是圖論中的一個(gè)經(jīng)典問題，它被廣泛應(yīng)用于許多領(lǐng)域。給定有向加權(quán)圖G=(V,E),在其上定義加權(quán)函數(shù)w:E→R為邊到實(shí)型權(quán)值的映射。路徑p=(v0,v1,…,vk)的權(quán)是其組成邊的所有權(quán)值之和:定義從u到v的最短路的權(quán)為:在研究網(wǎng)絡(luò)最短路問題上,Dijkstra算法是其中最為經(jīng)典的算法之一。筆者在Dijkstra并行算法的基礎(chǔ)上提出一種更高效的基于Petri網(wǎng)的并發(fā)仿真算法,并將它擴(kuò)展到隨機(jī)網(wǎng)絡(luò)情形。1dijkstra算法1.1到其他控制的最短路單源最短路問題所求的是從某結(jié)點(diǎn)s到其他所有結(jié)點(diǎn)的最短路。這是最短路問題的基礎(chǔ)問題。其他的最短路問題都可以轉(zhuǎn)化為單源最短路問題進(jìn)行求解。1.2dijpstor算法設(shè)一個(gè)有向圖G=(V,E),的加權(quán)鄰接矩陣為W,且w(i,j)表示邊(i,j)的長度,若i與j之間不存在有向邊,則w(i,j)為∞,1≤i,j≤n,i,j∈V,S(n)為已找到的從頂點(diǎn)Vi出發(fā)的最短路的終點(diǎn)的集合數(shù)組(1≤i≤n),數(shù)組中各個(gè)集合的初始狀態(tài)為空集。從vi出發(fā)到圖中其余各個(gè)頂點(diǎn)的vj(1≤j≤n,j≠i)的初始值為D[j]=arcs[locateVex(G,V)[j]],vj∈V。Dijkstra算法的基本思想是按路徑長度遞增的次序產(chǎn)生最短路,可由下式給出:Dijkstra算法解決了有向加權(quán)圖的最短路問題。它可以解決單源最短路問題,如果以每個(gè)點(diǎn)作為源都做一次Dijkstra算法,則可以求出每對結(jié)點(diǎn)間的最短路。該算法的條件是所有邊的權(quán)值都非負(fù)。1.3同步通信算法采用的是Dijkstra算法,先求一個(gè)結(jié)點(diǎn)到其他所有結(jié)點(diǎn)的單源最短路,然后推廣到多個(gè)點(diǎn)。算法要點(diǎn)是將V分成兩個(gè)集合S(開始只包含源點(diǎn))和V-S。每一步從V-S中選一結(jié)點(diǎn)加入S,使S中從源點(diǎn)到其余各結(jié)點(diǎn)的路長最短。由上述算法可知,Dijkstra算法不存在數(shù)據(jù)的流相關(guān),因此在計(jì)算過程中不存在同步通信問題。根據(jù)這個(gè)特點(diǎn),進(jìn)一步假定路權(quán)為正整數(shù)。2隨著時(shí)間的推移，最好的并發(fā)癥模擬算法被提出2.1狀態(tài)標(biāo)識(shí)系統(tǒng)Petri網(wǎng)是PETRI在1962年創(chuàng)立的一種描述條件和事件關(guān)系的數(shù)學(xué)工具,在離散事件動(dòng)態(tài)系統(tǒng)(DEDS)中成為一種很有效的描述方法。定義1一個(gè)基本Petri網(wǎng)的結(jié)構(gòu)是一個(gè)6元組Σ=(P,T;F,W,M,M0),P={P1,P2,…,Pn}(n≥0)為庫所節(jié)點(diǎn)的有限集合,T={T1,T2,…,Tm}(m≥0)為變遷節(jié)點(diǎn)的有限集合,P∪T≠Φ,P∩T=Φ,F為連接庫所節(jié)點(diǎn)和變遷節(jié)點(diǎn)的有向弧集,即Fue020P×T∪T×P,W∶F→{1,2,3,…}為有向弧的權(quán)值函數(shù);M∶P→{0,1,2,3,…}為狀態(tài)標(biāo)識(shí),代表網(wǎng)中托肯的分布狀況;M0∶P→{0,1,2,3,…}為庫所的初始標(biāo)記。定義2時(shí)延Petri網(wǎng)是在標(biāo)識(shí)Petri網(wǎng)基礎(chǔ)上發(fā)展起來的,用來描述與時(shí)間相關(guān)的系統(tǒng),Q=(R,Σ),Σ為與所有變遷相聯(lián)系的時(shí)延。時(shí)延Petri網(wǎng)很好地體現(xiàn)了某一事件發(fā)生的開始與結(jié)束之間的一段時(shí)間的停滯。2.2資源存在與事件擴(kuò)網(wǎng)論認(rèn)為,并發(fā)關(guān)系是所有系統(tǒng)共有的最基本現(xiàn)象,處于概念級別的最底層。所謂并發(fā),指的是事件之間沒有必然的先后之分,也指資源的共存。若資源存在于事件發(fā)生之前、之中及之后而沒有改變,資源和事件也稱為并發(fā)。參與系統(tǒng)活動(dòng)的每個(gè)個(gè)體都有自己的活動(dòng)蹤跡,這是一條全序的時(shí)間線。不同個(gè)體共同參與的活動(dòng)是它們的時(shí)間線的交點(diǎn),從而為不同個(gè)體的狀態(tài)與活動(dòng)分出先后。分不出先后的事件及狀態(tài)就是并發(fā)的。Petri網(wǎng)的創(chuàng)始人PETRI指出,通用網(wǎng)論除了準(zhǔn)確描述相關(guān)性(依賴性、因果關(guān)系、順序關(guān)系)和不相關(guān)性(并發(fā))外,還正視所有資源都是有限的事實(shí)。2.3基于petri網(wǎng)的最短路算法Dijkstra算法是最短路算法中最常用的算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路。主要特點(diǎn)是以起始節(jié)點(diǎn)S為中心向外層擴(kuò)展,直到擴(kuò)展到目標(biāo)節(jié)點(diǎn)T為止?；跁r(shí)延Petri網(wǎng)求解最短路算法也沿用這種思路,并利用了Petri網(wǎng)的并發(fā)特性與資源約束?；跁r(shí)延Petri網(wǎng)的求解最短路的仿真算法的基本思想是從起始節(jié)點(diǎn)S出發(fā),將網(wǎng)絡(luò)中的弧比作水管,利用水流流經(jīng)網(wǎng)絡(luò),最先到達(dá)目標(biāo)節(jié)點(diǎn)T的水流所經(jīng)過的路徑就是最短路?；跁r(shí)延Petri網(wǎng)的求解最短路算法的具體步驟如下:(1)將求解最短路網(wǎng)絡(luò)圖映射為時(shí)延Petri網(wǎng);(2)設(shè)置一個(gè)資源控制層,使路徑上的每個(gè)非初始庫所的托肯僅僅由某一個(gè)輸入弧提供;(3)添加一個(gè)標(biāo)號層來表示標(biāo)號過程;(4)運(yùn)行該P(yáng)etri網(wǎng)結(jié)束時(shí),就可以根據(jù)標(biāo)號情況得知最短路。2.4《petri網(wǎng)》單行線交通網(wǎng)如圖1所示,每弧旁的數(shù)字表示通過這條單行線所需要的費(fèi)用?，F(xiàn)在某人要從v1出發(fā),通過這條交通網(wǎng)到達(dá)v8,求使總費(fèi)用最小的旅行路線。求解過程在Petri網(wǎng)軟件HPSim平臺(tái)上進(jìn)行,該軟件集成了基本Petri網(wǎng)、帶抑制弧的Petri網(wǎng)、時(shí)延Petri網(wǎng)與隨機(jī)Petri網(wǎng)的功能。(1)將圖1中的點(diǎn)vi(i=1,2,…,9)映射為庫所,弧(vi,vj)(i,j=1,2,…,9)映射為變遷,弧上的權(quán)映射為對應(yīng)的時(shí)延變遷的時(shí)延時(shí)間。設(shè)定各庫所的容量為由該庫所輸出的弧的總數(shù),如v1向v2、v3、v43個(gè)庫所輸出共3條弧,故v1的容量為3。設(shè)定各變遷的輸入弧的權(quán)重為1,輸出弧的權(quán)重為該弧所指向庫所的輸出弧的總數(shù)。設(shè)定v1的初始托肯數(shù)為3。將該最短路問題映射為用時(shí)延Petri網(wǎng)表述的形式,如圖2所示。(2)Dijkstra方法的基本思想是從v1出發(fā),逐步地向外探尋最短路。按照Dijkstra方法的要求,設(shè)置每個(gè)非初始庫所的托肯僅僅由某一個(gè)輸入弧提供,即設(shè)置資源的獨(dú)占性。這可以另外設(shè)置一個(gè)資源控制層來實(shí)現(xiàn)。如輸入庫所v2的托肯可能來自于v1或v3,由變遷(v1,v2)或(v3,v2)提供,于是設(shè)置一個(gè)資源控制庫所連接變遷(v1,v2)與(v3,v2),每個(gè)資源控制庫所中僅含有一個(gè)托肯,這樣就保證了v2中的托肯僅僅由變遷(v1,v2)與(v3,v2)中的某一個(gè)提供(實(shí)際上是由從v1出發(fā)耗時(shí)最少的路徑提供)。其他庫所的路由控制情況如圖3所示。路徑上輸入弧只有一條的庫所的資源控制庫所在圖中就省略掉了。(3)Dijkstra方法要求在執(zhí)行過程中,與每個(gè)節(jié)點(diǎn)(這里是路徑上的庫所)對應(yīng),記錄下一個(gè)數(shù),稱為它的標(biāo)號。映射為Petri網(wǎng)后,添加一個(gè)標(biāo)號層來表示該標(biāo)號過程。記錄標(biāo)號如圖4所示,網(wǎng)絡(luò)中的每個(gè)變遷向標(biāo)號層輸出一個(gè)庫所,庫所的容量為對應(yīng)變遷的時(shí)延數(shù),初始容量為零,連接弧的權(quán)重也是對應(yīng)變遷的時(shí)延數(shù)。這樣當(dāng)某一個(gè)變遷所對應(yīng)的路徑有托肯經(jīng)過,則該變遷對應(yīng)的標(biāo)號庫所就有個(gè)數(shù)相當(dāng)于對應(yīng)變遷的時(shí)延數(shù)的托肯輸入。(4)運(yùn)行該P(yáng)etri網(wǎng),可以看到尋找最短路的動(dòng)態(tài)演示過程。運(yùn)行結(jié)束時(shí),就可以根據(jù)標(biāo)號情況得知最短路,將該路徑上的變遷對應(yīng)標(biāo)號庫所中的托肯數(shù)累加就得到最短路值。經(jīng)過整理后的最短路如圖5所示。這樣從v1到v8的最短路是(v1,v3,v2,v5,v8),最短路值為3+2+1+6=12。由圖5可得到v1點(diǎn)到其他各點(diǎn)的最短路,即Petri網(wǎng)解法同樣有解的豐富性。3隨機(jī)網(wǎng)絡(luò)中的最短距離問題3.1隨機(jī)網(wǎng)絡(luò)的最短路問題隨著實(shí)踐的發(fā)展,越來越多的應(yīng)用領(lǐng)域提出了弧權(quán)是隨機(jī)變量的最短路問題。FRANK和MIR-CHANDANI將交通網(wǎng)絡(luò)上的路段運(yùn)行時(shí)間看作一個(gè)隨機(jī)變量,考慮了最短路的概率分布問題。董振寧等對隨機(jī)網(wǎng)絡(luò)的最短路問題進(jìn)行了研究,并給出了一個(gè)啟發(fā)式算法。柳亞玲等研究了隨機(jī)時(shí)間依賴網(wǎng)絡(luò),并基于標(biāo)號修正算法,提出了求所有節(jié)點(diǎn)到單一終點(diǎn)的最短路的算法,以及該路徑實(shí)現(xiàn)的概率。另外許多學(xué)者從不同實(shí)際需要對隨機(jī)網(wǎng)絡(luò)的最短路問題進(jìn)行了研究。筆者所討論的隨機(jī)網(wǎng)絡(luò),是指網(wǎng)絡(luò)中每一條弧的權(quán)是一個(gè)隨機(jī)變量,盡管不知道它的準(zhǔn)確值,但知道它的分布函數(shù)。在進(jìn)入每一條弧之前,并不知道該弧的權(quán)值,只有通過了該弧,才知道其權(quán)值。換句話說,在弧沒有被選定之前,所有弧的權(quán)都不知道。而隨機(jī)網(wǎng)絡(luò)中的最短路問題是指假定弧權(quán)是隨機(jī)變量時(shí)求網(wǎng)絡(luò)的最短路。這里用隨機(jī)時(shí)延Petri網(wǎng)作為仿真工具來分析隨機(jī)網(wǎng)絡(luò)最短路的概率分布問題。3.2庫所集的資源函數(shù)定義3稱6元組SPN=(P,T;F,K,M0,λ)為一個(gè)隨機(jī)Petri網(wǎng)。有:(1)(P,T;F)是一個(gè)網(wǎng),P為狀態(tài)庫所集,T為狀態(tài)變遷集,F為連接庫所集與變遷集的弧集;(2)K為庫所P的容量函數(shù),也稱為資源函數(shù);(3)M0為隨機(jī)Petri網(wǎng)的初始標(biāo)識(shí),也是系統(tǒng)的初始狀態(tài);(4)λ為狀態(tài)變遷的平均觸發(fā)速率集合;(5)引發(fā)規(guī)則。設(shè)M為系統(tǒng)的一個(gè)狀態(tài),對于t∈T,,M(p)>0,則稱t是可觸發(fā)的,并且若M經(jīng)t觸發(fā)到M′(記為M[t>M′),則也是系統(tǒng)的一個(gè)狀態(tài),且3.3資源控制層基于隨機(jī)時(shí)延Petri網(wǎng)的求解隨機(jī)網(wǎng)絡(luò)最短路算法的具體步驟如下:(1)將要求解最短路的隨機(jī)網(wǎng)絡(luò)圖映射為隨機(jī)時(shí)延Petri網(wǎng);(2)設(shè)置一個(gè)資源控制層,使路徑上的每個(gè)非初始庫所的托肯僅僅由某一個(gè)輸入弧提供;(3)添加一個(gè)標(biāo)號層來表示標(biāo)號過程;(4)運(yùn)行該P(yáng)etri網(wǎng)足夠次數(shù),根據(jù)標(biāo)號情況得到每次運(yùn)行后的最短路,運(yùn)行結(jié)果可能不同,記下它們的頻數(shù),由此可以構(gòu)造該隨機(jī)網(wǎng)絡(luò)最短路的經(jīng)驗(yàn)分布。3.4隨機(jī)網(wǎng)絡(luò)最短路問題在圖1所示的單行線交通網(wǎng)基礎(chǔ)上,每弧旁的數(shù)字表示通過這條單行線所需費(fèi)用,設(shè)各費(fèi)用是一個(gè)隨機(jī)變量ξi(i=1,…,16),服從負(fù)指數(shù)分布,其數(shù)學(xué)期望為弧旁的數(shù)字?，F(xiàn)在某人要從v1出發(fā),通過這條交通網(wǎng)到達(dá)v8,求使總費(fèi)用最小的旅行路線的分布。將該隨機(jī)網(wǎng)絡(luò)最短路問題映射為隨機(jī)時(shí)延Petri網(wǎng),如圖2所示。要求各個(gè)變遷的時(shí)延數(shù)為隨機(jī)變量ξi(i=1,…,16),服從負(fù)指數(shù)分布,其數(shù)學(xué)期望為變遷旁的數(shù)字。設(shè)置一個(gè)資源控制層,如圖3所示。添加一個(gè)標(biāo)號層來表示該標(biāo)號過程,如圖4所示。運(yùn)行該P(yáng)etri網(wǎng)100次,記下每次運(yùn)行后的最短路,計(jì)算它們的頻數(shù),如表1所示,由此可以構(gòu)造該隨機(jī)網(wǎng)絡(luò)最短路的經(jīng)驗(yàn)分布。從表1中可以看出,當(dāng)單行線上所需費(fèi)用為隨機(jī)變量時(shí),最短路不一定是確定的,假定服從負(fù)指數(shù)分布,其數(shù)學(xué)期望為弧旁的數(shù)字時(shí),從v1到v8的最短路不再肯定是(v1,v3,v2,v5