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

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

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

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