開放Petri網(wǎng)可達(dá)狀態(tài)求解系統(tǒng)的開發(fā)與實(shí)現(xiàn)

吳亞光

摘要：Petri網(wǎng)模型是理論計(jì)算機(jī)科學(xué)包括自動(dòng)機(jī)模型和形式語(yǔ)言理論的一個(gè)分支，具有自然、直觀、簡(jiǎn)單易懂等特點(diǎn)。開放Petri網(wǎng)是Petri網(wǎng)的一種擴(kuò)充，在并行模型分析，協(xié)議的驗(yàn)證，自動(dòng)控制等方面有廣泛的應(yīng)用。該文的主要工作在于開發(fā)一個(gè)可以生成開放Petri網(wǎng)的軟件，并能夠求解其所有的可達(dá)狀態(tài)，最后通過這樣一個(gè)軟件來(lái)研究開放Petri網(wǎng)的可達(dá)狀態(tài)總數(shù)隨網(wǎng)的規(guī)模變化和初始Token數(shù)變化而變化的情況。我們得到的結(jié)論是在這兩種情況下可達(dá)狀態(tài)數(shù)都是呈指數(shù)增長(zhǎng)的。

關(guān)鍵詞：開放Petri網(wǎng) ； Petri網(wǎng)生成 ； 可達(dá)狀態(tài) ； Petri網(wǎng)規(guī)模

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）02-0213-03

Abstract： The model of Petri Net is a branch of theoretical computer science with automaton model and theory of formal language. It is nature， intuitive and easy understanding. Open Petri Net is an expansion of Petri Net and widely used in analysis of parallel model， protocol verification and automatic control. The main work of this subject is to develop a software to build a open Petri Net and calculate all its reachable markings， which meanwhile outputs them. In the end we study the changes of reachable markings when the scale of Nets is increasing by the software. The conclusion we got is that the reachable markings are growing exponentially when the scale of Petri Nets and the initial Tokens are increasing.

Key words： Open Petri Nets； Generation of Petri Nets； Collection of Reachable Markings； Scale of a Petri Net

1 問題的提出

在Petri網(wǎng)研究與應(yīng)用的發(fā)展歷史中，它的應(yīng)用范圍已經(jīng)遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)科學(xué)的領(lǐng)域，成為研究離散事件動(dòng)態(tài)系統(tǒng)的一種有用工具。如今，Petri網(wǎng)模型在眾多方面得以應(yīng)用，如分布式軟件系統(tǒng)，分布式數(shù)據(jù)庫(kù)系統(tǒng)，并發(fā)并行計(jì)算，柔性制造系統(tǒng)，多處理機(jī)系統(tǒng)，邏輯推理，辦公自動(dòng)化系統(tǒng)，形式語(yǔ)言，神經(jīng)元網(wǎng)絡(luò)和決策模型等。Petri網(wǎng)在如今各個(gè)科學(xué)領(lǐng)域都已經(jīng)有了重要的地位，Petri網(wǎng)的分析方法和應(yīng)用范疇也在被不斷擴(kuò)展，因此實(shí)用的Petri分析工具的開發(fā)研制也受到各國(guó)Petri網(wǎng)研究者的重視。

可達(dá)性研究是研究一個(gè)Petri網(wǎng)的可能達(dá)到的狀態(tài)和各個(gè)狀態(tài)之間的關(guān)系。我們想清楚得到需要研究的網(wǎng)的每個(gè)可達(dá)狀態(tài)和它們之間的關(guān)系，通過研究開放Petri網(wǎng)的可達(dá)狀態(tài)隨著網(wǎng)的規(guī)模的變化而變化的情況，來(lái)給基于Petri網(wǎng)建模的實(shí)際應(yīng)用系統(tǒng)的研究提供依據(jù)，這也就是本文的研究意義。

由于Petri網(wǎng)研究在各個(gè)領(lǐng)域的重要意義，我們希望能夠開發(fā)一個(gè)用于計(jì)算并輸出開放Petri網(wǎng)可達(dá)狀態(tài)的可視化軟件，并以此來(lái)研究開放Petri網(wǎng)的可達(dá)狀態(tài)數(shù)隨網(wǎng)規(guī)模變化而變化的情況

2 算法實(shí)現(xiàn)

2.1 畫圖界面的算法

在軟件運(yùn)行以后，先選擇工具欄上的一個(gè)按鈕，在空白的空間上進(jìn)行繪制。繪制會(huì)啟動(dòng)一個(gè)鼠標(biāo)左鍵的點(diǎn)擊判定（OnLButtonDown）。如果選擇的是添加庫(kù)所按鈕，則先判斷改點(diǎn)與已有的庫(kù)所或者變遷點(diǎn)之間的距離（DistanceBetweenPoints），如果該距離過小，則無(wú)法添加，這也是防止兩個(gè)庫(kù)所或者變遷元素在圖形上過近甚至重合，影響圖形的正確性和美觀。如果是安全距離，則將庫(kù)所數(shù)（PlaceNum）加1，并將目前的PlaceNum-1作為該庫(kù)所的標(biāo)識(shí)。同理如果點(diǎn)擊的是添加變遷按鈕，經(jīng)過相同的判斷來(lái)決定添加情況。

如果選擇的是添加流關(guān)系按鈕（界面上顯示是箭頭），則需要通過以下步驟的驗(yàn)證：

1）通過起始點(diǎn)（FirstPoint）的坐標(biāo)讀取該點(diǎn)的數(shù)據(jù)，判斷它是庫(kù)所還是變遷。

2）通過終點(diǎn)（SecondPoint）的坐標(biāo)讀取該點(diǎn)的數(shù)據(jù)，判斷它是庫(kù)所還是變遷。

3）如果兩者性質(zhì)不同，則建立兩者間的連線，并將存儲(chǔ)網(wǎng)中庫(kù)所和變遷關(guān)系的數(shù)組Connec[100][100]中的相應(yīng)項(xiàng)置為1，表示庫(kù)所和變遷的連接，否則視為無(wú)效操作。

如果選擇的是庫(kù)所刪除或者變遷刪除按鈕，則需要通過以下步驟的驗(yàn)證：

1）通過鼠標(biāo)所在的坐標(biāo)確定該點(diǎn)的性質(zhì)。

2）如果是庫(kù)所（變遷）的話則刪除該元素點(diǎn)，找出標(biāo)識(shí)小于該庫(kù)所（變遷）的庫(kù)所（變遷），將其標(biāo)識(shí)減1，并在Connec[100][100]數(shù)組中把所有關(guān)于該庫(kù)所（變遷）的數(shù)置為0，表現(xiàn)為刪除所有關(guān)于該庫(kù)所（變遷）的連接。

如果是流關(guān)系刪除按鈕，則在Connec[100][100]中將該連接的數(shù)據(jù)置為0，并表現(xiàn)為刪除該箭頭。

2.2 可達(dá)狀態(tài)計(jì)算的算法

按提示輸入各個(gè)庫(kù)所的標(biāo)識(shí)（token）數(shù)，點(diǎn)擊計(jì)算結(jié)果按鈕，會(huì)在下面的框中出現(xiàn)所有的可達(dá)狀態(tài)并統(tǒng)計(jì)其數(shù)量。下面我們先從整體上討論一下算法的思想。算法包含以下幾個(gè)函數(shù)：

GatherData（）：比較TempToken數(shù)組中的標(biāo)識(shí)是否與Token數(shù)組中已有的各組標(biāo)識(shí)，若和已有的標(biāo)識(shí)組完全不同，則將TempToken中的標(biāo)識(shí)作為新的一組標(biāo)識(shí)統(tǒng)計(jì)到Token數(shù)組中，表示又得到一組新的可達(dá)狀態(tài)，否則舍棄。這里我們定義一個(gè)變量k=庫(kù)所數(shù)量，利用一個(gè)嵌套的循環(huán)來(lái)逐個(gè)比較臨時(shí)狀態(tài)數(shù)組TempToken和已有的Token數(shù)組里面的狀態(tài)，如果不是每一個(gè)都相等那么k將通過自減運(yùn)算成為0，觸發(fā)下一個(gè)循環(huán)，將TempToken里的狀態(tài)復(fù)制到Token數(shù)組中存儲(chǔ)，并將總的狀態(tài)數(shù)DifferCount加1。如果循環(huán)過后k等于0，那么說(shuō)明TempToken中的狀態(tài)是和已有的狀態(tài)之一重復(fù)的，那么我們?cè)谶@里break，繼續(xù)下一步的動(dòng)作。

Fire（）：這個(gè)函數(shù)里面我們先定義了兩個(gè)容器test和canf，然后同樣通過一個(gè)循環(huán)來(lái)依次檢測(cè)當(dāng)前token數(shù)下的每一個(gè)變遷是否可以觸發(fā)。我們下面用一段偽代碼來(lái)簡(jiǎn)單說(shuō)明一下具體的算法思想。

當(dāng)一個(gè)變遷T的所有前置庫(kù)所P都至少有一個(gè)Token，那么該變遷是可以激發(fā)的。激發(fā)之后該變遷的每個(gè)前置庫(kù)所的Token減1，每個(gè)后置庫(kù)所的Token加1?？杉ぐl(fā)的算法運(yùn)行時(shí)先檢測(cè)Connec數(shù)組中與當(dāng)前變遷有關(guān)的部分，如果Connec[P][T]=-1，說(shuō)明P是該變遷的前置，如果Connec[P][T]=1，則P是該變遷的后置。容器test的作用是存儲(chǔ)該變遷每個(gè)前置庫(kù)所是否有Token，如果有Token則在test中存入1，沒有就存入0，最后讓test容器中的所有數(shù)自乘，如果得到的數(shù)非0，則表示該變遷的每個(gè)前置庫(kù)所都是有Token的，也就是說(shuō)該變遷可以觸發(fā)，如果得到的數(shù)是0，則表明該變遷的前置庫(kù)所中必然至少有一個(gè)的Token數(shù)為0，也就是該變遷在當(dāng)前狀態(tài)下不能觸發(fā)。這樣用循環(huán)依次檢測(cè)以后將可以觸發(fā)的變遷T存入canf容器中。

完成上面的步驟以后，canf容器中應(yīng)該都是可以觸發(fā)的變遷的序號(hào)了。依次取出這些序號(hào)按順序觸發(fā)，觸發(fā)成功就會(huì)將該變遷的前置庫(kù)所的Token減1，后置庫(kù)所的Token加1，得到一個(gè)新的可達(dá)狀態(tài)，調(diào)用GatherData（）函數(shù)，將得到的可達(dá)狀態(tài)與已有的Token數(shù)組中的狀態(tài)進(jìn)行比較來(lái)決定是否存儲(chǔ)。至此Fire（）函數(shù)的功能介紹完畢。

FireSelect（）：從Token數(shù)組中依次取出各組標(biāo)識(shí)存入PresentToen進(jìn)行觸發(fā)計(jì)算，如此往返遞歸直到Token數(shù)組的大小不變?yōu)橹梗吹玫搅丝蛇_(dá)狀態(tài)的總數(shù)并且能夠輸出每個(gè)可達(dá)狀態(tài)。

Output（）：輸出Token數(shù)組中所存儲(chǔ)的所有可達(dá)狀態(tài)和它的序號(hào)，并通過Num數(shù)組的計(jì)算輸出其直接可達(dá)狀態(tài)的序號(hào)，最終輸出總的可達(dá)狀態(tài)數(shù)。

3 程序功能演示

使用Visual C++的MFC對(duì)實(shí)現(xiàn)上述功能。軟件實(shí)現(xiàn)界面如圖1，左側(cè)為Petri網(wǎng)繪制界面，右側(cè)為可達(dá)狀態(tài)集計(jì)算界面。

4 開放Petri網(wǎng)可達(dá)狀態(tài)數(shù)變化情況的研究

4.1 可達(dá)狀態(tài)數(shù)隨初始Token數(shù)變化的研究

繪制圖2左側(cè)的Petri網(wǎng)并按照下列四種情況給Token賦值：

情況1：給庫(kù)所P0，P4，P8的初始Token置為1，其余庫(kù)所的Token為全0。運(yùn)行軟件進(jìn)行計(jì)算。

情況2：給庫(kù)所P0，P4，P8的初始Token置為2，其余庫(kù)所的Token為全0.運(yùn)行軟件進(jìn)行計(jì)算

情況3：同樣的做法，將初始Token置為3，其余全0。

情況4：初始Token為4，其余全0。

最終得到圖2右側(cè)的可達(dá)狀態(tài)集變化曲線。

4.2 可達(dá)狀態(tài)數(shù)隨網(wǎng)的規(guī)模變化的研究

繪制不同規(guī)模的4個(gè)Petri網(wǎng)，如圖3所示：

結(jié)論：由以上的數(shù)據(jù)和生成的曲線圖可以知道，雖然在每個(gè)庫(kù)所數(shù)由5增加到6的時(shí)候可達(dá)狀態(tài)不升反減，這可能是由于我們的網(wǎng)都是用戶隨機(jī)生成的，其中的流關(guān)系會(huì)直接影響到可達(dá)狀態(tài)數(shù)的數(shù)量，在后來(lái)的檢查中我們也驗(yàn)證了這一情況。所以總的來(lái)說(shuō)，我們可以很有把握地推斷開放Petri網(wǎng)的可達(dá)狀態(tài)數(shù)是隨Petri網(wǎng)規(guī)模的增大而指數(shù)增長(zhǎng)的。

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

本文給出了開放Petri網(wǎng)生成及其可達(dá)狀態(tài)集計(jì)算的算法，并用C++語(yǔ)言進(jìn)行實(shí)現(xiàn)，編寫出了繪制和計(jì)算可達(dá)狀態(tài)集的界面。使用該軟件分別對(duì)開放Petri網(wǎng)隨其初始Token數(shù)和網(wǎng)的規(guī)模變化而變化的情況進(jìn)行分析，最終得到開放Petri網(wǎng)的可達(dá)狀態(tài)數(shù)在上述兩種情況下都是呈指數(shù)增長(zhǎng)的。

參考文獻(xiàn)：

[1] （德）Petri C A. Fundamentals of a Theory of Asynchronous Information Flow[J]. Proceedings of IFIP Congress 62，1963，12（4）：86-90.

[2] 吳哲輝. Petri網(wǎng)導(dǎo)論（重點(diǎn)大學(xué)計(jì)算機(jī)教材）[M]. 北京：機(jī)械工業(yè)出版社， 2006：56-62.

[3] Enric Pastor， Jordi Cortadella， Oriol Roig. Symbolic Analysis of BoundedPetri Nets[J]. IEEE Transaction On Computers，2001，50（5）： 432-448.

[4] 袁崇義.Petri網(wǎng)原理[M]. 北京：電子工業(yè)出版社，1998：13-22.

[5] 林闖. 隨機(jī)Petri網(wǎng)和系統(tǒng)性能評(píng)價(jià)[M]. 北京：清華大學(xué)出版社，2000：89-120.

[6] Murata T. Petri Nets： Properties， Analysis and Applications[J].Proceedings of the IEEE，1989， 77（4）： 541-580.