Loading AI tools
来自维基百科,自由的百科全书
佩特里網(英語:Petri net),又譯為裴氏網、派翠網路,是對離散並列系統的數學表示。佩特里網屬於離散事件動態系統,是1960年代由卡爾·亞當·佩特里發明的[1],適合於描述非同步的、並行的電腦系統模型。佩特里網既有嚴格的數學表述方式,也有直觀的圖形表達方式。
由於佩特里網能表達並行的事件,被認為是自動化理論的一種。研究領域趨向認為佩特里網是所有流程定義語言之母。
卡爾·亞當·佩特里是一名物理學家,他發明佩特里網主要是從物理的角度去描述並發現象的。據佩特里本人所述,他認為60年代電腦科學的概念構架由於缺乏並行不適合於描述物理系統。其中一個重要的概念,就是佩特里網裡面不存在所謂的「全域時間」的概念,因為這跟狹義相對論是衝突的。相反,佩特里網可以描述每一個節點的時序。
從狹義相對論的觀點出發,兩個時空點之間如果沒有因果關係把它們連接起來(或者說「類空」的),它們就是獨立的,不能說其中一個發生在前另一個在後或者相反。因此,佩特里網裡面的兩種變遷(見下文)如果都有發生的條件,則不能認為其執行順序有任何關係。然而,佩特里網旨在描述變遷之間的因果關係,並由此構造時序。
經典的佩特里網是簡單的過程模型,由兩種節點:庫所和變遷,有向弧,以及權杖等元素組成的。
佩特里網的元素:
佩特里網的規則是:
如果一個變遷的每個輸入庫所(input place)都擁有數量足夠的權杖時,該變遷即為被允許(enable)。一個變遷被允許時,變遷將發生(fire),輸入庫所(input place)的權杖被消耗,同時為輸出庫所(output place)產生權杖。
注意:
兩個變遷爭奪一個權杖的情形被稱之為衝突。當發生衝突的時候,由於佩特里網的時序是不確定的,因此具體哪個變遷得以發生也是不確定的。實際應用中,往往需要避免這種情形。用於描述現象的佩特里網也可能自然出現衝突,這表明我們對於變遷發生的條件沒有完全了解。
多個弧連接兩個節點的情況。在輸入庫所和變遷之間的弧的個數決定了該變遷變為被允許需要的權杖的個數。弧的個數決定了消耗/產生的權杖的個數。
一個經典的佩特里網由四元組(庫所,變遷,輸入函式,輸出函式)組成。任何圖都可以對映到這樣一個四元組上,反之亦然。
被允許的形式化 變遷發生的形式化佩特里網 到變遷系統的對映 可達性圖
佩特里網是一個三元組(P,T,F)
F(P X T)U(T X P)是弧的集合
一個流程的狀態是由在場所中的權杖建模的,狀態的變遷是由變遷建模的。權杖表示事物(人,貨物,機器),資訊,條件,或對象的狀態;庫所代表庫所,通道或地理位置;變遷代表事件,轉化或運輸
一個流程(Flow)有當前狀態,可達狀態,不可達狀態。
為了壓縮經典佩特里網中的重複結構,提高佩特里網的建模能力,進階佩特里網應運而生。進階佩特里網包括有色佩特里網和謂詞/變遷系統。這類網系統的特點是通過摺疊來減少網的網元,壓縮網的規模。
一個有色的權杖(托肯)通常代表具有一個可以標識的對象,從而避免相同網路結構的重複建模,如一個權杖可以取值「權杖A」,另一個權杖取值「權杖B」。當有色權杖的識別碼取值(顏色)可以使用複雜的複合類型時,因此權杖擁有取值(顏色)代表由權杖建模的對象的具體特徵,如一個權杖代表一個工人(張三,28歲,經驗3級)。
為了擴充佩特里網的建模能力,很多研究學者在多個方面對Petri網進行了擴充:
為了進行分析,我們需要建模期間,延遲等,因此可以為每一個權杖附加一個時間戳,由變遷決定生產出的權杖的延遲。常用的時間佩特里網可分為Timed Petri Net 和 Time Petri Net。
增加時序邏輯的定義,更好的描述行為過程。
構造一個複雜性與資料流圖相當的佩特里網的機制。層次佩特里網是由庫所,變遷和子網路構成的網路。佩特里網的層次化具有多種實現形式,例如高層次佩特里網中的一個變遷可以代表一個子佩特里網。