TVPS_posobie_13_06_2013

Рис. 50. Сеть Петри после удаления пассивного перехода t5

Так как после удаления данного перехода появилась висячая вершина – позиция p6, то удаляем ее (Рис. 51).

Рис. 51. Сеть Петри после удаления пассивной позиции p6

Шаг. 3. Строим список пассивных позиций – он пустой.

Работа алгоритма завершена. В результате получена сеть Петри, не имеющая пассивных переходов и позиций, множество последовательностей запусков которой совпадает с множеством последовательностей запусков исходной сети (Рис. 51).

Далее будет рассмотрен алгоритм построения дерева достижимости сети Петри, который, в частности, позволяет установить наличие пассивных переходов и позиций в сети.

81

2.13.Методы анализа сетей Петри: дерево достижимости

Наибольший интерес представляют методы, которые легко реализовать на ЭВМ, что важно для автоматического анализа свойств моделируемой дискретной системы.

Основные методы анализа сетей Петри основаны на использовании дерева достижимости (ДД) и матричных уравнений.

Смену маркировок, возникающих в результате запуска переходов, удобно представлять в виде графа маркировок, называемого деревом достижимости.

Дерево достижимости – это ориентированное корневое дерево, вершинам которого соответствуют возможные маркировки, а дугам – разрешенные переходы.

Корневой вершине соответствует начальная маркировка. Из каждой вершины исходят дуги, соответствующие разрешенным в этой маркировке переходам.

Построение дерева осуществляется последовательно, начиная с корневой вершины; на каждом шаге строится очередной ярус дерева.

Пример 34. На Рис. 52 изображена сеть Петри и дерево достижимости для нее.

p1

t2

p2

		(10)
		t1
		(01)
	t1	t2
		(10)
		t1
		(01)
		…

Рис. 52. Сеть Петри и дерево достижимости для нее

Нетрудно видеть, что даже в случае сетей, имеющих конечное множество достижимости, дерево достижимости получается бесконечным. Естественно, в случае бесконечного множества достижимости дерево достижимости бесконечное.

82

Вывод: для превращения ДД в полезный инструмент анализа необходимо принять определенные соглашения, ограничивающие ДД до конечных размеров. Такие соглашения приведут к потери некоторой части информации о СП и ее поведении, однако, эта мера вынужденная. Введем некоторые понятия, необходимые для описания алгоритма построения ДД.

Граничная вершина (и соответствующая ей маркировка) – это вершина, полученная на очередном шаге построения ДД, которая в настоящий момент обрабатывается.

Терминальная вершина соответствует маркировке, в которой не разрешен ни один переход (тупиковой маркировке).

Дублирующая вершина соответствует маркировке, уже полученной в построенной части ДД.

Внутренняя вершина – вершина ДД, не являющаяся ни граничной, ни дублирующей, ни терминальной.

Алгоритм построения усеченного дерева достижимости

На практике при использовании ДД для анализа сети Петри, естественно, ограничивают его до конечных размеров. Назовем такое ДД усеченным. Далее рассматриваются средства ограничения ДД до конечных размеров.

Для этого, в первую очередь, введем символ , который будет обозначать неограниченное число фишек в позиции. Пусть а – целое

неотрицательное число. Будем	считать, что символ	обладает
следующими арифметическими свойствами:
+а= ,	-a= , а< ,

где а – целое неотрицательное число.

Пусть имеется маркированная сеть Петри (P, T, I, O, 0), х – вершина дерева достижимости, [х] – маркировка, соответствующая вершине х ДД. Обозначим через [х]i число фишек в позиции pi P для маркировки [х]. Тогда

83

где m – целое неотрицательное число.

Если в некоторой маркировке вершины усеченного ДД встретится символ , то во всех дочерних вершинах соответствующая позиция также будет маркирована с помощью символа , так как a= .

Множество натуральных чисел с добавленным символом будем называть расширенным множеством натуральных чисел.

Во вторую очередь, естественно не строить исходящих дуг для терминальных и дублирующих вершин.

Рассмотрим алгоритм построения усеченного ДД. Пусть х – граничная вершина. Сначала это х0, соответствующая 0. Строить дерево будем в ширину, вершины одного уровня будем обрабатывать слева направо. Алгоритм работает до тех пор, пока имеются граничные вершины.

1.Если для маркировки [x] ни один из переходов не разрешен

(т. е. ( [x], tj) не определена для всех tj Т), то х – терминальная вершина.

2.Если в построенной части дерева имеется вершина у x, для

которой [x]= [y], то вершина х – дублирующая.

3. Если х – нетерминальная и недублирующая, то для х существуют переходы tj Т:

( [x], tj) определена.

Поэтому существует дуга из вершины х, помеченная tj и ведущая в вершину z.

Маркировка [z], связанная с этой вершиной, определяется для каждой позиции рi следующим образом:

а) если [х]i= , то [z]i= .

б) если на пути от корневой вершины к х существует вершина y: [y]< ( [x], tj) и [y]i< ( [x], tj)i, то [z]i= .

84

Отметим, что в данном случае используется принцип монотонности, с помощью символа мы говорим, что все переходы, разрешенные в вершине y, разрешены и в вершине z. Это позволяет усечь (ограничить) ДД, правда, часть информации теряется – мы можем сказать, что количество фишек в позиции может быть потенциально сколь угодно большим, но не можем сказать, какие точные значения оно может принимать.

в) Во всех остальных случаях [z]i= ( [x],tj)i.

После обработки вершина х становится внутренней, а z – граничной. Когда все вершины становятся дублирующими либо терминальными либо внутренними, работа алгоритма завершается.

Пример 35. Рассмотрим по шагам процесс построения усеченного ДД согласно алгоритму для сети Петри (Рис. 53).

Рис. 53. Пример построения дерева достижимости для сети Петри

Шаг 1. Корнем дерева является вершина x, соответствующая начальной маркировке (1, 0, 0). Она же является текущей граничной вершиной (выделена жирным начертанием). Обработаем ее. В результате получим две новые вершины (Рис. 54).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1	(1, 1, 0)	(0, 1, 1)

Рис. 54. ДД, полученное на шаге 1

85

Шаг 2. Строить дерево будем в ширину, вершины одного уровня будем обрабатывать слева направо. Тогда подлежат обработке вершины уровня 1, граничная вершина имеет маркировку (1, 1, 0). Обработаем ее. В результате получим две новые вершины на уровне 2 (Рис. 55). Обратите внимание, что в одной из новых вершин появился символ , так для позиции p2 выполнилось условие б третьего пункта алгоритма построения ограниченного ДД.

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
				(1, 1, 0)						(0, 1, 1)
		t1					t2
Уровень 2
	(1, , 0)					(0, 2, 1)

Рис. 55. ДД, полученное на шаге 2

Шаг 3. Возвращаемся на один уровень вверх, чтобы обработать вершину с маркировкой (0, 1, 1). В результате получим только одну новую вершину (Рис. 56).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
				(1, 1, 0)					(0, 1, 1)
												t3
		t1					t2
Уровень 2											(0, 0, 1)
	(1, , 0)					(0, 2, 1)
	Рис. 56.			ДД, полученное на шаге 3

86

Шаг 4. На текущем уровне дерева (на уровне 1) все вершины обработаны, поэтому переходим на уровень 2. Граничная вершина (1, , 0). Обработаем ее, в результате получим две новые вершины

(Рис. 57).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
							(1, 1, 0)							(0, 1, 1)
																	t3
					t1							t2
Уровень 2																(0, 0, 1)
			(1,	, 0)						(0, 2, 1)
		t1						t2
		(1,	, 0)		(0,		, 1)
Уровень 3

Рис. 57. ДД, полученное на шаге 4

Шаг 5. Граничная вершина находится на уровне 2 и имеет маркировку (0, 2, 1). Обработаем ее, в результате получим одну новую вершину (Рис. 58).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																								t3
							t1								t2
Уровень 2																							(0, 0, 1)
					(1,	, 0)						(0, 2, 1)
			t1							t2							t3
		(1,			, 0)		(0,		, 1)					(0, 1, 1)
Уровень 3
					Рис. 58. ДД, полученное на шаге 5

87

Шаг 6. Граничная вершина находится на уровне 2, она имеет маркировку (0, 0, 1). Обработаем ее. В данной маркировке не разрешен ни один переход, поэтому вершина является терминальной, исходящие дуги построит нельзя (Рис. 59).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																								t3
							t1								t2
Уровень 2																							(0, 0, 1)
					(1,	, 0)						(0, 2, 1)
			t1							t2							t3
		(1,			, 0)		(0,		, 1)					(0, 1, 1)
Уровень 3

Рис. 59. ДД, полученное на шаге 6

Шаг 7. Все вершины на уровне 2 обработаны, переходим на уровень 3. Граничная вершина имеет маркировку (1, , 0). Обработаем ее. Вершина является дублирующей, исходящие дуги не строятся (Рис. 60).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																								t3
							t1								t2
Уровень 2																							(0, 0, 1)
				(1,		, 0)						(0, 2, 1)
			t1							t2							t3
		(1, , 0)					(0,		, 1)					(0, 1, 1)
Уровень 3

Рис. 60. ДД, полученное на шаге 7

88

Шаг 8. Граничная вершина имеет маркировку (0, , 1). Обработаем ее, в результате получим одну новую вершину (Рис. 61).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																						t3
							t1									t2
Уровень 2																					(0, 0, 1)
				(1,		, 0)						(0, 2, 1)
			t1							t2							t3
															(0, 1, 1)
		(1, , 0)					(0,		, 1)
Уровень 3
							t3
Уровень 4
						(0,			, 1)

Рис. 61. ДД, полученное на шаге 8

Шаг 9. Возвращаемся на один уровень вверх, граничная вершина имеет маркировку (0, 1, 1). Обработаем ее. Вершина является дублирующей, исходящие дуги не строятся (Рис. 62).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																						t3
							t1									t2
Уровень 2																					(0, 0, 1)
					(1,	, 0)						(0, 2, 1)
			t1							t2							t3
		(1,			, 0)		(0,		, 1)						(0, 1, 1)
Уровень 3
							t3
Уровень 4
						(0,			, 1)

Рис. 62. ДД, полученное на шаге 9

89

Шаг 10. На уровне 3 все вершины обработаны, переходим на уровень 4. Граничная вершина имеет маркировку (0, , 1). Обработаем ее. Вершина является дублирующей, исходящие дуги не строятся (Рис. 63).

Уровень 0
				(1, 0, 0)
		t1
						t2

Уровень 1
									(1, 1, 0)									(0, 1, 1)
																						t3
							t1									t2
Уровень 2																					(0, 0, 1)
					(1,	, 0)						(0, 2, 1)
			t1							t2							t3
															(0, 1, 1)
		(1,			, 0)		(0,		, 1)
Уровень 3
							t3
Уровень 4
						(0,			, 1)

Рис. 63. ДД, полученное на шаге 10

Так как в дереве больше нет граничных вершин, то работа алгоритма завершается.

90