Внимание!!!
В выложенном на сайте тексте могут быть ошибки,
СКАЧАЙТЕ
оригинальную версию методички одним файлом в формате .doc (MS Word)
6.6. Дерево достижимости сетей Пэтри.
Алгоритм построения дерева
Для анализа свойств сетей Петри наиболее удобно использовать граф представления множества достижимости сетей Петри /ДДСП/. В этом дереве представлены все достижимые состояния сетей Петри.
Для стохастических сетей Петри ДДСП несколько сокращается, т.к. в них отражаются только реальные состояния.
Мгновенное состояние сети Петри в таком дереве не представлено.
Общий путь построения ДДСП R /СП, M0/ заключается в определении всех разрешенных переходов в соответствующей маркировке с последующим анализом соответствующего очередного состояния /маркировки/, достигающихся при независимых автоматических последовательностей запусков всех разрешенных переходов предыдущей маркировки.
Для нашего примера ДДСП имеет вид:
Начальная маркировка - корневая точка ДДСП.
дублирующая вершина дерева, после нее ДДСП строить необязательно.
В MV нет разрешения переходов и она называется терминальной или конечной.
Аналогично MIX завершает победу 1-го процесса.
Продолжение построения ДДСП с повторением маркировки M0 не имеет смысла, т.к. ДДСП будет иметь бесконечное множество одинаковых фрагментов.
ДДСП всегда представляется конечным графом. Ограничение ДДСП достигается за счет:
1. появления пассивных маркировок /терминальных вершин/ завершающих соответствующие ветви ДДСП;
2. появление маркировок тождественных некоторым ранее полученным маркировкам ДДСП /дублирующие вершины/ и дальше ДДСП не строится, т.к. ветви будут повторятся бесконечное число раз;
3. появление маркировок МZ, которые находятся в отношениях покрываемости с некоторыми уже имеющимися маркировками ДДСП /MZ > MY/. Это значит, что в одной или нескольких розициях Рі имеет место увеличение числа фишек. Такое увеличение можно считать неограниченным. В этом случае для позиции Рі вводится специальный символ , отражающий свойство накопления фишек в данной позиции. К фишки не прибавляются, следовательно появляются дублирующие вершины.
Постоение ДДСП для простых сетей Петри может быть выполнено вручную, а для более сложных - машинным способом.
В имитационных моделях выделяют специальный режим для построения ДДСП.
Для работы модели формируется несколько списков /очередей/, например очередь граничных вершин Qx .
Все остальные вершины дерева должны быть преобразованы алгоритмом из граничных вершин в следующие три типа вершин: