|
|
| (127 intermediate revisions by 3 users not shown) |
| Line 1: |
Line 1: |
| '''Мрежите на Петри''' ({{lang-en|Petri net}}) задават един от няколкото езика за математическо моделиране за описание на дискретни разпределени системи. Мрежата на Петри е ориентиран двуделен граф, чиито възми представляват:
| |
| * ''преходи'' (''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>.
| |
|
| |
| The ''preset'' of a transition ''t'' is the set of its ''input places'': <math>{}^{\bullet}s = \{ s \in S \mid W(s,t) > 0 \}</math>;
| |
| its ''postset'' is the set of its ''output places'': <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>
| |