Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 17
Текст из файла (страница 17)
6(ц(х1, Гг) определено), создать новую вершину з дерева достижнмости. Маркировка рЫ, связанная с этой вершиной, определяется для каждой позиции р~ следующим образом: а) Если )г(х1, = ьт, то рЫ~ — — гь. б) Если на пути от корневой вершины к х существует вершина у с р(у) ( 6 (1«(х), гг) и п(у1; ( 6 (1«(х), гг) ь то 1«Ы, = е. в) В противном случае рЫ, = Ь(1«(х1, Гг)ь Дуга, помеченная Гт, направлена от вершины х к вершине х.
Вершина х переопределяется как внутренняя, вершина г становится граничной. Когда все вершины дерева — терминальные, дублирующие илн внутренние, алгоритм останавливается. На рис. 4.14 представлено дерево достижимости для сети Петри на рнс. 4.9. Дерево достнжимости сети Петри с рис. 4 15 изображено на рис. 4.16. Аиояив сетей ПетРи (0.1,И (1,о,о) (1дье) тв (Оеь)) Рве. 4.14. Лерево достикииости сети Петри, првведевиоа вв рис. 4.9.
Рве. 4.15. Сеть Петри, двя котороа строится дерево достижвиости. Очень важным свойством алгоритма построения дерева достнжимостн является то, что ои заканчивает работу. Для доказательства этого мы должны показать, что алгоритм не может создавать новые граничные вершины бесконечно. Доказательство основано на трех леммах, Лемма 4.!.
В любом бесконечном направленном дереве, в котором , всякая вершина имеет только конечное число непосредственно Гдова 4 П,ОД,О1 т1 тр б (1,ьз,0,11 11, . о.о1 11,ю,1,01 Рис. 4.16. Дерево достижимости сети Петри, изображеииой иа рис. 4.15. последующих вершин, существует бесконечный путь, исходящий из корня. Доказагпелвспмо. Начнем с корня в вершине ха. Поскольку имеется только конечное число непосредственно следующих за х вершин, но общее число вершин в дереве бесконечно, по крайней мере одна из непосредственно следующих за х, вершин должна быть корнем бесконечного поддерева. (Если бы все поддеревья с корнями, не. посредственно следующими за х, были конечнымн, то и дерево с корнем х было бы конечным.) Выберем вершину хь непосредственно следующую за х и являющуюся корнем бесконечного поддерева.
Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве таком вершины х . Продолжая таким же образом, получим бесконечный путь в дереве х„хь х„.... Д Лемма 4.2. Всякая бесконечная последовательность неотрицательных целых содержит бесконечную неубывающую подпоследовательность. Дохаительалао. Возможны два случаи: Е Если какой-либо элемент последовательности встречается бесконечно часто, то пусть хо является таким элементом. Бесконечная подпоследовательность хв, ха, х„ ...
является бесконечной неубывающей подпоследовательностью. Анализ сетей Петри 2. Если никакой элемент не встречается бесконечно часто, тогда всякий элемент встречается только конечное число раз. Пусть х — произвольный элемент последовательности. Существует самое большее хе целых, неотрицательных и меньших, чем хе (О,..., хе — 1), причем каждый из них присутствует в последовательности толька конечное число раз. Следовательно, продвигаясь достаточно долго по последовательности, мы должны встретить элемент ха х,;~ хе. Аналогично должен существовать в последователь- насти хе, хе ~ хь и т. д. Это определяет бесконечную неубывающую подпоследовательиасть х„х„х,...
В обоих случаях бесконечная неубывающая последовательность существует. Г] Ь Лемма 4.3. Всякая бесконечная последовательность и-векторов иад расширенными неотрицательными целыми (неотрицательные целые плюс символ ее) содержит бесконечную неубывающую подпоследовательность. Доказательство. Доказываем икдукцней по и, где и — размерность векторного пространства. 1. Базовый случай (и =- Ц. Если в последовательности имеется бесконечное число векторов (еа), то они образуют бесконечную неубывающую последовательность.
В противном случае бесконеч, ная последовательность, образованная удалением конечного числа векторов (та), имеет по лемме 4.2 бесконечную неубывающую под- 1, последовательность. , 2. Индуктивное предположение. (Допустим, что лемма верна для и, докажем ее справедливость для и+ 1.) Рассмотрим первую ,'координату.
Если существует бесконечно много векторов, имею- щих в качестве первой координаты ее, тогда выберем эту бесконеч- 'ную подпоследовательиасть, которая не убывает (постоянна) по ', первой координате. Если только конечное число векторов имеют еь в качестве первой координаты, то рассмотрим бесконечную последовательность целых, являкхцихся значениями первых коарди- 1, нат.
По лемме 4.2 эта последовательность имеет бесконечную не, убывающую подпоследовательность. Оиа определяет бесконечную й подпаследовательность векторов, которые ие убывают по своей первой координате. В любам случае мы имеем последовательность векторов, не.убывающих по первой координате. Применим индуктивное пред, положение к последовательности п-векторов, которая получается в результате отбрасывания первой компоненты п+ 1-векторов.
Полученная таким образом бесконечная подпоследовательность является неубывающей по каждой координате. Е] Докажем следующую теорему. ° еарема 4.1. дерево достижимости сети Петри конечно. цоказательстео. Доказательство проводим от противного. Допустим, что существует бесконечное дерево достижимости. Тогда 4 ба2 па лемме 4.1 в нем имеется бесконечный путь х, хп хз, ..., исходящий из корня х;,. (Число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов т.) Тогда р[хв], р[х ], р[хз],...— бесконечная последовательность и-векторов над Н Ь [ш], а по лемме 4.3 ана имеет бесконечную неубывающую подпаследовательность р[хь] < р[хп] < р[хи].... Но по построению мы не можем иметь р[х,] = р[х~], поскольку тогда одна из вершин была бы дублирующей й не имела следукхцих за собой вершин.
Следовательно, мы имеем бесконечную строго убывающую последовательность р[х4]< р,[хп]< .... Но по построению, так как р[х;]< р[хД, нам следовало бы заменить по крайней мере одну компоненту р[х ], не являющуюся гв, на гв в р[х 1]. Таким образом, р[х,,~ имеет по кРайней меРе однУ компонентУ, ЯвлЯющУюсЯ в, Р[хь1 имеет по крайней мере две е-компоненты, а р[хг ] имеет по крайней мере и а-компонент.
Поскольку маркировки о-мерные, р[х; ] имеет во всех компонентах а. Но тогда р[хг ] не может быть больше р[х; ]. Пришли к противоречию, что доказывает, что наше допул щение относительно существования бесконечного дерева достижимасти неверно. Г1 Построение дерева дастижнмости было впервые описано Карпом и Миллерам [148]. Используемый здесь вариант алгоритма бьш предложен Келлером [1Щ. Доказательство конечности, данное здесь, взято у Хэна [11Ц, который принял за основу доказательство Карпа и Миллера [!48]. Дерево достижимости — очень полезный инструмент анализа сетей Петри. В последующих разделах мы покажем, как его можно использовать для решения некоторых задач, представленных в равд. 4.1. 4.1лЛ.
ввзоаасность и ограияченнчсп Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое к, что число фишек в любой позиции не может превысить й. Оба этих свойства можно проверить с помощью дерева достижимости. Сеть Петри ограниченна тогда и толька тогда, когда символ гв отсутствует в ее дереве дастижимости. Присутствие символа е в дереве дастижимасти означает„что число фишек потенциально не ограничено; существует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая количество фишек до произвольно большого числа. Таким образом, если имеется символ г», сеть неограниченна.
Кроме того, положение символа гв показывает, какие позиции неограниченны. Обратное утверждение также является верным, если сеть Петри неограниченна, та число достижимых маркировок бесконечно. По- Анализ сетей Петри <о. «. ,о< з <о,о.<.о1 <о,о,хо> <о,о,о, и !" «,о.о,о> Рнс. 4А7. Опрелеленне ограннченностн длн сети Петри с помощью Лорена достнжнмостн. скольку дерево достижимости конечно, бесконечное число достижимых маркировок отражает присутствие символа-ю. Если сеть Петри ограниченна н символ ю отсутствует в дереве достижимости, то сеть Петри представляет систему конечных состояний. Дерево достижимости, по существу, является графом состояний и будет содержать вершину, соответствукнцую всякой достижимой маркировке. Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых мар.
кировок. Например, чтобы определить границу для заданной позиции, нужно построить дерево достижимости и найти наибольшее ,аначение компоненты маркировки, соответствующей атой позиции. 4* !00 Найденное значение является границей числа фишек для заданной позиции.
Если граница для всех позиций равна 1'>, сеть безопасна. На рис. 4.17 демонстрируется использование дерева достижнмости для определения ограниченности. Отметим, что по дереву достижимости даже для сетей Петри, не являющихся ограниченными (вследствие неограниченности некоторой позиции), мсзкно определить границы для тех позиций, которые являются ограниченными.
Таким образом, дерево достижимости позволяет эффективно решить задачи анализа сетей Петри по определению ограниченности и безопасности для отдельных позиций и целых сетей. З.Х1.2. Санраааана Сеть Петри является сохраняющей, если она не теряет и не порождает фишки, а просто передвигает нх. Поскольку две фишки можно закодировать как одну фишку, которая позже вызовет запуск перехода, создакхцего две фишки, значение фишки в каждой позиции определяет вектор взвешивания, веса неотрицательны. Сеть Петри является сохраняющей по отношению к вектору взвешивания, если взвешенная сумма фишек постоянна для всех достижимых маркировок.
Свойство сохранения эффективно проверяется с помощью дерева достижимости. Так как дерево достижимости конечно, для каждой маркировки можно вычислить взвешенную сумму. Если сумма одинакова для каждой достижимой маркировки, сеть— сохраняющая по отношению к данному весу. Если суммы не равны„ сеть — несокраняющая. При оценке сохранения необходимо быть внимательным с символом ы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
