Достижимость и покрываемость сетей Петри

Достижимость и покрываемость  сетей Петри. Пример.

Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок. Задача достижимости являет­ся, по-видимому, наиболее простой (для формулировки).

Определение 4.5. Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ’ определить: μ'  R(C, μ)?

Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости. Например, для сети Петри с рис. 4.6 тупик может возникнуть, если достижимым является со­стояние (0, 1, 0, 0, 0, 0, 1, 0).

На рис. 4.8 показана сеть Петри, цель которой заключается в решении задачи о взаимном исключении, — предполагается, что позиции p₄ и р₉ будут взаимно исключающими. Мы хотим знать, является ли какое-либо состояние с μ(р₄)  1 и μ(p₉)  1 достижи­мым. Эта задача аналогична достижимости, но несколько отлича­ется; она называется задачей покрываемости. Маркировка

μ "пок­рывает маркировку μ,, если μ" μ'.

Определение  Задача покрываемости. Для данной сети Петри С с начальной маркировкой μ и маркировки μ.' определить, сущест­вует ли такая достижимая маркировка μ"  R(C, μ), что μ"  μ'.

Рекомендуемые материалы

В других возможных задачах типа достижимости могло бы игно­рироваться содержимое некоторых позиций и приниматься во вни­мание сравнение или покрытие содержимого нескольких важных позиций. Например, в сети Петри на рис. 4.8 наш интерес огра­ничен позициями р₄ и р₉ — маркировка остальных позиций не важна. Таким образом, мы можем рассматривать достижимость и покрываемость «по модулю» множества позиций. Эти задачи назы­ваются задачами достижимости подмаркировки и покрываемости подмаркировки.

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

Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемос­ти мы хотим для данной маркировки μ' определить, достижима ли маркировка μ"  μ'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево дости­жимости. Затем ищем любую вершину х с μ[х] μ'. Если такой вершины не существует, маркировка р' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую Маркировку, покрывающую μ'.

Если Вам понравилась эта лекция, то понравится и эта - Вторая часть.

Путь от корня к покрывающей маркировке определяет последо­вательность переходов, которые приводят из начальной маркиров­ки к покрывающей маркировке, а маркировка, связанная с этой вершиной, определяет покрывающую маркировку. Символ (о вновь должен рассматриваться как обозначение бесконечного множества значений. Если компонента покрывающей маркировки — μ , то в пути от корня к покрывающей маркировке имеется «цикл». Для увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточное число раз повторить этот цикл.

Заметим, что, если несколько компонент покрывающей марки­ровки равны w, между изменениями маркировки, получающимися в результате прохождения циклов, возможна взаимосвязь. Рассмот­рим сеть Петри на рис. 4.18 и ее дерево достижимости, показанное на рис. 4.19. Согласно проведенному анализу, маркировка (0, 14, 1, 7) покрывается в множестве достижимости. Путь, порождающий покрывающую маркировку, состоит из некоторого числа переходов t₁, за которыми следует переход t₂, после которого уже следует некото­рое число переходов t₃. Задача заключается в определении того, сколько раз нужно запустить переходы t₁ и t₃. Так как мы хотим иметь в позиции р₁ 14 фишек, a t₁ помещает в р₂ одну фишку, попытаемся

выполнить 14 t₁. Однако нам необходимо выполнить 7t₃, а каждый за­пуск t₃ удаляет из р₂ фишку, поэтому в действительности необходимо выполнить не менее 21 t₁ затем t₂ и после этого не менее 7t₃ (выпол­нить t₃ такое число раз, чтобы в позиции р₂ осталось не менее 14 фишек). Карп и Миллер  предложили алгоритм, определяю­щий минимальное число запусков переходов, необходимых для покрытия дайной маркировки.