文/王博　代飛　黃苾

Petri網(wǎng)是1962年由德國科學家Carl Adam Petri博士在他的博士論文《用自動機通信》中創(chuàng)立的一種網(wǎng)狀結構。本質上，它是一個有向二分圖，由庫所和變遷組成。

可達圖作為分析Petri網(wǎng)動態(tài)性質的一種重要分析技術，被大量廣泛使用。但是，基于可達圖的狀態(tài)空間搜索方法需要考慮并發(fā)事件間所有的交織可能，進而導致狀態(tài)空爆炸。也就是說，使用基于可達圖的狀態(tài)空間搜索方法對并發(fā)系統(tǒng)進行分析時，常常面臨效率低下的問題。

針對上述問題，McMillan在1995提出了展開（unfolding）的概念。與基于可達圖的狀態(tài)空間搜索方法相比，基于展開的狀態(tài)空間搜索方法不需要考慮并發(fā)事件間的所有可能交織，可避免狀態(tài)空間爆炸。本文將給出展開Petri網(wǎng)的算法，通過一個例子，直觀比較可達圖和出現(xiàn)網(wǎng)（Occurrence Net，由展開Petri網(wǎng)得到）的規(guī)模。

圖1：一個Petri網(wǎng)

圖2：可達圖

1　Petri網(wǎng)的可達圖和出現(xiàn)網(wǎng)

定義1（Petri網(wǎng)）Petri網(wǎng)是一個四元組∑=(P, T; F, M)，其中：

（4） 映 射 M：P→ {0, 1, 2, 3...}稱 為Petri網(wǎng)的一個標識。通常用M0表示Petri網(wǎng)的初始標識。

通常，庫所使用圓圈表示，變遷使用方框表示，流關系使用有向線段表示，托肯使用實心小黑點表示。

定義2（可達標識集）設∑=(P, T; F, M0)是一個Petri網(wǎng)，其中M0是初始情態(tài)。S的可達標識集R(M0)為滿足下面條件的最小集合：

（1）M0∈ R(M0)；

（2）若M∈R(M0)，且存在t∈T，使得M[t＞M’，則M’∈R(M0)。

可達標識集R(M0)描述了∑所有可能的狀態(tài)。若以R(M0)中的元素為節(jié)點，有向弧描述標識間的后繼關系，可構造出∑的可達圖。

定義3（可達圖）設∑=(P, T; F, M0)是Petri網(wǎng)，其中M0是初始情態(tài)。∑的可達圖定義為一個三元組RG(Σ)=(R(M0), E, Tran)，其中：

（1）E={(Mi, Mj)|Mi, Mj∈ R(M0),tk∈ T:Mi[tk＞Mj}；

（2） 映 射Tran:E→T稱 為 遷 移，Tran(Mi, Mj)=tk當且僅當 Mi[tk＞Mj；

稱 R(M0)為 RG(Σ)的頂點集，E 為 RG(Σ)的弧集。若Tran(Mi, Mj)=tk，稱tk為弧(Mi, Mj)的旁標，通常，將其記為

定義4（出現(xiàn)網(wǎng)）設Σ=(P, T; F, M0)是一個Petri網(wǎng)，Σ的展開是一個出現(xiàn)網(wǎng)O=(P', T', F';L)，其中:

（1）L：P'∪T'→P∪T是標號函數(shù)，用于建立P'到P及T'到T的映射，通常稱P'為條件集，T'為事件集，：

圖3：出現(xiàn)網(wǎng)

2　展開Petri網(wǎng)的算法

對于任意給定的一個Petri網(wǎng)，可由算法1構造得到出現(xiàn)網(wǎng)。

算法1 展開Petri網(wǎng)。

輸入：任意一個Petri網(wǎng)是Σ=(P, T; F, M)；

輸出：該Petri網(wǎng)的出現(xiàn)網(wǎng)O=(P', T', F'; L)。

（1）將Petri網(wǎng)中每一個初始托肯所在的庫所復制到出現(xiàn)網(wǎng)中；

（2）從Petri網(wǎng)中選擇一個變遷t；

（3）對于·t中的每個庫所，在出現(xiàn)網(wǎng)中尋找其副本，如果無法找到，返回步驟2。對于一個變遷，不要兩次選擇相同的庫所子集；

（4）如果被選中的一對庫所是沖突關系或者有前后關系（即它們不是并發(fā)的），則返回步驟2；

（5）將t復制到出現(xiàn)網(wǎng)中，稱為t'。從步驟3中找到的每個庫所畫一條弧到t'；

（6）對于t·中的每個庫所，將其復制到出現(xiàn)網(wǎng)中，并從t'畫一條弧到這些庫所；

（7）無限地重復步驟2～6。

如上所述，算法1構造的出現(xiàn)網(wǎng)是一個無限網(wǎng)，它在保持Petri網(wǎng)中的各變遷間的關系（順序、沖突、并發(fā)等）的同時，表示了網(wǎng)內所有托肯的轉移過程。

3　例子

下面通過一個例子，來直觀比較可達圖和出現(xiàn)網(wǎng)的規(guī)模。

圖1所示的是一個Petri網(wǎng)。在Petri網(wǎng)存在多個變遷間的并發(fā)關系，例如變遷t1和t2，變遷t2和t3，變遷t1和t3，變遷t1和t5等。

圖2是使用開源工具PIPE 4.3生成的圖1所示Petri網(wǎng)的可達圖截圖。

從圖2可以看出：圖1所示Petri網(wǎng)對應的可達圖有29個狀態(tài)，在圖2中用橢圓表示。其中，狀態(tài)s1-s27刻畫了并發(fā)變遷產生的狀態(tài)遷移關系。進一步分析，不難看出：隨著Petri網(wǎng)中并發(fā)變遷的數(shù)量增加，可達圖中的狀態(tài)呈指數(shù)增長，不可避免地會出現(xiàn)狀態(tài)空間爆炸。

圖3是根據(jù)算法1生成的圖1所示Petri網(wǎng)的出現(xiàn)網(wǎng)。其中，p0-1表示原Petri網(wǎng)中庫所p0在出現(xiàn)網(wǎng)的生成次序；t0-1表示原Petri網(wǎng)中變遷t0在出現(xiàn)網(wǎng)的生成次序。

對比圖2和圖3，可以看出：圖3所示出現(xiàn)網(wǎng)的規(guī)模遠遠小于圖2所示可達圖的規(guī)模。由此可以說明：基于展開的狀態(tài)空間搜索方法可避免狀態(tài)空間爆炸問題

4　總結

通過一個例子，直觀對比了基于展開的狀態(tài)空間搜索方法和基于可達圖的狀態(tài)空間搜索方法，以說明基于展開的狀態(tài)空間搜索方法可避免狀態(tài)空間爆炸問題。