吳亞光

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：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)研究與應用的發(fā)展歷史中，它的應用范圍已經(jīng)遠遠超出了計算機科學的領域，成為研究離散事件動態(tài)系統(tǒng)的一種有用工具。如今，Petri網(wǎng)模型在眾多方面得以應用，如分布式軟件系統(tǒng)，分布式數(shù)據(jù)庫系統(tǒng)，并發(fā)并行計算，柔性制造系統(tǒng)，多處理機系統(tǒng)，邏輯推理，辦公自動化系統(tǒng)，形式語言，神經(jīng)元網(wǎng)絡和決策模型等。Petri網(wǎng)在如今各個科學領域都已經(jīng)有了重要的地位，Petri網(wǎng)的分析方法和應用范疇也在被不斷擴展，因此實用的Petri分析工具的開發(fā)研制也受到各國Petri網(wǎng)研究者的重視。

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

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

2 算法實現(xiàn)

2.1 畫圖界面的算法

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

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

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

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

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

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

1）通過鼠標所在的坐標確定該點的性質。

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

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

2.2 可達狀態(tài)計算的算法

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

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

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

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

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

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

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

3 程序功能演示

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

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

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

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

情況1：給庫所P0，P4，P8的初始Token置為1，其余庫所的Token為全0。運行軟件進行計算。

情況2：給庫所P0，P4，P8的初始Token置為2，其余庫所的Token為全0.運行軟件進行計算

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

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

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

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

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

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

5 結束語

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

參考文獻：

[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)導論（重點大學計算機教材）[M]. 北京：機械工業(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] 林闖. 隨機Petri網(wǎng)和系統(tǒng)性能評價[M]. 北京：清華大學出版社，2000：89-120.

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