基于t-不變量的Petri網(wǎng)狀態(tài)空間壓縮算法.pdf

1、Petri網(wǎng)是Carl Adam Petri于1962年首先提出來的。由于其直觀性和內(nèi)在的并發(fā)性，Petri網(wǎng)在建模、分析、驗證、仿真、性能評估和對離散時間動態(tài)系統(tǒng)的控制有著強有力的作用，因而Petri網(wǎng)已成為當前最具前景的建模工具。
　　作為一種建模工具，Petri網(wǎng)不可避免地面臨著狀態(tài)空間爆炸的問題。在對大型系統(tǒng)進行建模分析時，會產(chǎn)生大量的狀態(tài)空間，從而對我們的分析和研究造成巨大的阻礙。因此，本文致力于利用T-不變量對Petr

2、i網(wǎng)的狀態(tài)空間進行壓縮，從而緩解Petri網(wǎng)在建模過程中所面臨的狀態(tài)空間爆炸的問題。
　　由于在Petri網(wǎng)的狀態(tài)可達圖中，每一個強連通分支中的狀態(tài)標識都互相可以到達，因此本文將每一個強連通分支看作一個等價類，其中的標識相互等價，因此對于每一個強連通分支只存儲一個狀態(tài)標識，而其他未知的標識通過強連通分支中的路徑搜索得到。在Petri網(wǎng)的狀態(tài)可達圖中強連通分支的搜索過程中，本文主要利用T-不變量與借矩陣進行結合，改進了Tarjan算

3、法，啟發(fā)式地引導尋求狀態(tài)可達圖中的強連通分支，極大優(yōu)化了強連通分支的搜索速度。此外本文通過拓撲排序極大簡化了未知標識探索的過程。
　　最后，本文設計了一組對照實驗，選取了狀態(tài)可達圖中強連通分支只包含一個環(huán)和多個環(huán)的兩種Petri網(wǎng)，分別將Karsten Schmidt所提出的壓縮算法與本文所提出的壓縮算法應用于兩種Petri網(wǎng)的狀態(tài)空間壓縮進行比較分析，得出了本算法在壓縮率上具有優(yōu)越性而在預處理過程處于劣勢的結論，因此分析出在不同