|
|
| (126 intermediate revisions by 3 users not shown) |
| Line 1: |
Line 1: |
| '''Мрежите на Петри''' ({{lang-en|Petri net}}), още наричани '''позиционно-преходни мрежи''' (''place-transition nets'', ''P/T nets'') задават един от няколкото езика за математическо моделиране за описание на дискретни разпределени системи. Мрежата на Петри е ориентиран двуделен граф, чиито възми представляват:
| |
| * ''преходи'' (''transitions''), т.е. дискретни събития, които могат да се случат,
| |
| * ''позиции'' (''places''), т.е. условия, и
| |
| * ''насочени дъги'', които описват кои позиции за кои преходи са пред- и/или пост-условия.
| |
|
| |
|
| Мрежите на Петри са измислени през август 1939 година от [[Карл Адам Петри]], тогава на 13 години, за нуждите на описанието на химични процеси.
| |
|
| |
| Подобно на индустриални стандарти като [[UML]]-диаграмите, [[Business Process Modeling Notation]] и [[Event-driven process chain]], мрежите на Петри предлагат графична нотация на постъпкови процеси, съдържащи избор, итерация и паралелно изпълнение. За разлика от тези стандарти, мрежите на Петри имат точна математическа дефиниция на семантиката на изпълнението си, с добре разработена математическа теория за анализ на процесите.
| |
|
| |
| == Неформално описание ==
| |
| Една мрежа на Петри се състои от позиции, преходи и насочени дъги. Една дъга свързва една позиция и един преход, но не и двойка позиции или двойка дъги. Позиция, от която започва дъга, се нарича входна позиция за прехода; а такава, в която влиза започнала от преход дъга, се нарича изходна позиция.
| |
|
| |
| Позициите могат да съдържат произволен неотрицателен брой ''ядра'' (''tokens''). Непразните позиции се наричат ''маркирани''. Разпределението на ядрата из позициите на мрежата се нарича ''маркировка'' (''marking''). Маркировката отразява състоянието на системата в един момент от време, и в следващия момент може да се промени при активиране на преход. Промяната на маркировката още се нарича "игра на ядрата". Един преход в мрежата на Петри се активира, когато се появи ядро в края на някоя от входните му дъги; когато преход се активира, той поглъща входните ядра и поставя нови ядра на края на всичките си изходни дъги, с други думи ядрата преминават от входните позиции на прехода към изходните му позиции. Активирането е атомарно събитие, т.е. извършва се на една неделима стъпка.
| |
|
| |
| Изпълнението на мрежите на Петри е недерминирано: когато множество преходи са в готовност по едно и също време, може да се активира всеки от тях. Освен това, по едно време множество ядра могат да се намират на различни места из мрежата, включително и в една и съща позиция. Всички тези характеристики правят мрежите на Петри подходящ инструмент за моделиране на паралелни процеси и конкурентното поведение на разпределени системи.
| |
|
| |
| == Формално определение ==
| |
|
| |
| === Синтаксис ===
| |
|
| |
| '''[[Граф (математика)|Граф]] на мрежата на Петри''' е тройката <math>(S,T,W)\!</math>, при която
| |
| * <math>S</math> е крайно непразно [[множество]] от позиции,
| |
| * <math>T</math> е крайно непразно множество от преходи,
| |
| * сечението на множествата <math>S</math> и <math>T</math> е [[празно множество|празното множество]], т.е. никой от обектите в графа не може да е едновременно и позиция, и преход.
| |
| * <math>W: (S \times T) \cup (T \times S) \to \mathbb{N}</math> е [[мултимножество]] от насочени дъги, т.е. дефинира дъгите и им присвоява по едно неотрицателно [[цяло число]] <!-- arc multiplicity -->.
| |
|
| |
| The ''flow relation'' е множество от дъги: <math> F = \{ (x,y) \mid W(x,y) > 0 \}</math>. In many textbooks, arcs can only have multiplicity 1, and they often define Petri nets using <math>F</math> instead of <math>W</math>.
| |
|
| |
| Графът на мрежата на Петри е [[двуделен граф|двуделен]] [[мултиграф]] <math>(S \cup T, F)</math> с възли <math>S</math> и <math>T</math>.
| |
|
| |
| Множеството от входните позиции на преход е <math>{}^{\bullet}s = \{ s \in S \mid W(s,t) > 0 \}</math>; множеството от изходните позиции на преход е: <math>s^{\bullet} = \{ s \in S \mid W(t,s) > 0 \}</math>
| |
|
| |
| ''Маркировка'' на графа на мрежата на Петри е мултимножество от своите позиции, т.е. изображение от вида <math>M: S \to \mathbb{N}</math>. Казваме, че маркировката присвоява на всяка позиция определен брой ядра.
| |
|
| |
| '''Мрежа на Петри''' е четворката <math>(S,T,W,M_0)\!</math>, при която
| |
| * <math>(S,T,W)</math> е графът на мрежата на Петри;
| |
| * <math>M_0</math> е началната маркировка на графа.
| |
|
| |
| === Семантика на изпълнението ===
| |
|
| |
| Поведението на една мрежа на Петри се дефинира като релация на нейните маркировки, по следния начин:
| |
|
| |
| Маркировки могат да се добавят като към всяко мултимножество: <math>M + M' \ \stackrel{D}{=}\ \{ s \to M(s) + M'(s) \mid s \in S \}</math>
| |
|
| |
| Изпълнението на графа на мрежата на Петри <math>G = (S,T,W)\!</math> може да се определи като ''релацията преход'' <math>\to_{G}</math> между нейните маркировки по следния начин:
| |
| * за всяко <math>t</math> от <math>T</math>: <math> M \to_{G,t} M' \ \stackrel{D}{\Leftrightarrow}\ \exists M'': S \to \mathbb{N}:
| |
| M = M'' + \textstyle\sum_{s \in S} W(s,t) \ \wedge\
| |
| M' = M'' + \textstyle\sum_{s \in S} W(t,s)</math>
| |
| * <math> M \to_{G} M' \ \stackrel{D}{\Leftrightarrow}\ \exists t \in T: M \to_{G,t} M'</math>
| |
|
| |
| С други думи,
| |
| * активирането на преход <math>t</math> в една маркировка <math>M</math> поглъща <math>W(s,t)</math> ядра от всеки от неговите входни позиции <math>s</math>, и генерира <math>W(t,s)</math> ядра във всяка от изходните му позиции <math>s</math>
| |
| * преходът е ''в готовност'' (още се казва, че е ''достъпен'', т.е. може да бъде ''активиран'') в <math>M</math>, ако всичките му входни позиции съдържат ядра, т.е. само тогава когато <math>\forall s: M(s) \geq W(s,t)</math>, и всичките му изходни позиции са празни.
| |
|
| |
| Интересуваме се най-вече какво може да се случи когато преходите могат продължително време да се активират в произволен ред.
| |
|
| |
| Казваме, че една маркировка <math>M'</math> ''е достижима'' от маркировката <math>M</math> ''на един такт'' ако <math>M \to_G M'</math>; казваче, че е ''достижима от '' <math>M</math> ако <math>M {\to_G}^* M'</math>, където <math>{\to_G}^*</math> е [[транзитивно затваряне]] на <math>\to_G</math>; т.е. ако е достижима за 0 или повече такта (стъпки).
| |
|
| |
| За една (маркирана) мрежа на Петри <math>(S,T,W,M_0)\!</math>, се интересуваме от активациите, които могат да настъпят при дадена начална маркировка <math>M_0</math>. Множеството от ''достижимите маркировки'' е множеството <math>R(N) \ \stackrel{D}{=}\ \{ M' \mid M_0 {\to_{(S,T,W)}}^* M' \} </math>
| |
|
| |
| ''Графът на достижимостта'' на <math>N</math> е релацията на прехода <math>\to_G</math>, ограничена върху своите достижими маркировки <math>R(N)</math>. <!-- It is the [[state space]] of the net. -->
| |
|
| |
| ''Последователността от активациите'' за една мрежа на Петри с граф <math>G</math> и начална маркировка <math>M_0</math> е последователността от преходи <math>\vec \sigma = \langle t_{i_1} \ldots t_{i_n} \rangle</math>, за която <math>M_0 \to_{G,t_{i_1}} M_1 \wedge \ldots \wedge M_{n-1} \to_{G,t_{i_n}} M_n</math>. Множеството от последователности на активациите се означава с <math>L(N)</math>.
| |
|
| |
| === Формулировка чрез вектори и матрици ===
| |
| Маркировките на една мрежа на Петри <math>(S,T,W,M_0)\!</math> могат да бъдат разгледани като [[вектор]]и от неотрицателни цели числа с дължина <math>|S|</math>.
| |
|
| |
| Релацията на прехода на мрежата може да се опише като двойка [[матрица|матрици]] с размери <math>|S|</math> на <math>|T|</math>:
| |
| * <math>W^-</math>, определена с <math>\forall s,t: W^-[s,t] = W(s,t)</math>
| |
| * <math>W^+</math>, определена с <math>\forall s,t: W^+[s,t] = W(t,s).</math>
| |
| Тогава, тяхната разлика
| |
| * <math> W^T = W^+ - W^-</math>
| |
| може да се използва за описание на достижимите маркировки в термините на умножението на матрици.
| |
| За всяка последователност от преходи <math>w</math>, с <math>o(w)</math> се означава векторът, който прави съответствието между всеки преход и броя на срещанията му в <math>w</math>. Тогава,
| |
| * <math>R(N) = \{ M \mid \exists w: M = M_0 + W^T \cdot o(w) \wedge w \!</math> е последователността от активации на <math>N \}\!</math>.
| |
|
| |
| За отбелязване е изискването, че <math>w</math> е определена последователност от активации, понеже разрешаването на произволни последонателности от преходи ще генерира по-голямо множество.
| |
|
| |
| [[Image:detailed petri net.png|frame|(b) Petri net Example]] <math>W^{+}=\begin{bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end{bmatrix} </math>
| |
|
| |
| <math> W^{-}=\begin{bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end{bmatrix} </math>
| |
|
| |
| <math>W^T=\begin{bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end{bmatrix}</math>
| |
|
| |
| <math>M_{0}=\begin{bmatrix} 1 & 0 & 2 & 1 \end{bmatrix}</math>
| |