Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи достижимости и покрываемости
Задача достижимости. Для данной сети Петри С с маркировкой m и маркировки m ' определить: ? Маркировка m " покрывает маркировку m ', если m " m ', т.е. . Задача покрываемости. Для данной сети Петри С с начальной маркировкой m и маркировки m ' определить, существует ли такая достижимая маркировка , такая что m " m '.
Методы анализа сетей Петри.
Дерево достижимости.
Рис 4.4: Маркированная сеть Петри, для которой строится дерево достижимости.
Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 4.4. Её начальная маркировка – (1, 0, 0). Это – корневая вершина дерева достижимости. Непосредственно достижимые из неё маркировки – это вершины второго уровня и т.д.
Рис 4.5: Первые три шага построения дерева достижимости для сети Петри на рис 4.4. Получившееся дерево достижимости может оказаться бесконечным. Будет порождена каждая маркировка из множества достижимости, поэтому для любой сети Петри с бесконечным множеством достижимости соответствующее дерево также должно быть бесконечным. Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево. Пассивные маркировки – маркировки, в которых нет разрешенных переходов. Они называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Они называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис.4.5 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности , не будет порождать какие-либо новые вершины, поскольку она ранее встречалась в дереве в результате выполнения перехода из начальной маркировки. Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке m и кончающуюся в маркировке m ' > m,. Маркировка m ' совпадает с маркировкой m, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная в m ' и приходя к маркировке m ". В общем случае можно запустить последовательность σ n раз, получив в результате маркировку . Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 4.4, например, можно запустить переход столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р 2. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа ω, который обозначает «бесконечность». Для любого постоянного а определим
. (4.5)
Рис 4.6: Дерево достижимости для сети Петри изображённой на рис 4.4. Можно показать, что алгоритм построения дерева достижимости заканчивает работу.
Лекция 5. Анализ сетей Петри (продолжение).
Безопасность и ограниченность. Сеть Петри ограниченна тогда и только тогда, когда символ отсутствует в ее дереве достижимости. Если сеть Петри ограниченна дерево достижимости будет содержать вершину, соответствующую всякой достижимой маркировке. Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых маркировок. Например, чтобы определить границу для заданной позиции, нужно построить дерево достижимости и найти наибольшее значение компоненты маркировки, соответствующей этой позиции. Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций равна 1, сеть безопасна. Сохранение. Если маркировка имеет в качестве маркировки некоторой позиции тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Если сеть сохраняющая, существуют взвешенная сумма, обозначим её s, и вектор весов w = (w 1, w 2,.., wn). Для каждой маркировки дерева достижимости имеем
. (5.1)
Если система (5.1) имеет решение, то сеть сохраняющая с весом. Покрываемость. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки дерево достижимости. Затем ищем любую вершину с m " m '. Если такой вершины не существует, маркировка m ' не покрывается никакой достижимой маркировкой; если она найдена, то это и есть искомая маркировка. Путь от корня к покрывающей маркировке определяет последовательность переходов, которые приводят из начальной маркировки к покрывающей маркировке. Символ вновь должен рассматриваться как обозначение бесконечного множества значений. Если компонента покрывающей маркировки — , то в пути от корня к покрывающей маркировке имеется цикл. Для увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточное число раз повторить этот цикл.
|
||||||
Последнее изменение этой страницы: 2016-08-14; просмотров: 334; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.92.1.156 (0.009 с.) |