-
Пройти Антиплагиат ©


Главная » Теория вычислительных процессов » 11.1 Решение задачи покрываемости и достижимости сетей Петри на основе дерева достижимости.



Решение задачи покрываемости и достижимости сетей Петри на основе дерева достижимости.

Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная. Уникализировать текст 



 
Проблемы, возникающие в случае наличия неограниченной позиции. Пример.
В задаче покрываемости мы хотим для данной маркировки μ' определить, достижима ли маркировка μ''
μ'. Строим для начальной маркировки усеченное ДД. Затем ищем любую вершину х с μ[x
μ'. Если такой вершины не существует, маркировка μ' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую маркировку, покрывающую μ'.
Задача достижимости маркировки μ'' из начальной маркировки μ' решается поиском вершины усеченного ДД с маркировкой μ''
Усеченное ДД не всегда можно использовать для решения задач покрываемости и достижимости. Ранее уже обсуждалось, что решение указанных задач затруднено в случае, когда ДД содержит символ
ω
. Если дерево не содержит символ
ω
, то эти за
дачи успешно решаются. Пример: рисунок

 
 
 
Если проанализировать функционирование СП, то можно увидеть, что для получения маркировки (0, 14, 1, 7), необходимо выполнить следующую последовательность запусков:
σ
=(t1t1…t1) t2 (t3t3…t3).
21 раз 7 раз
Таким образом
μ
=(0, 14, 1, 7) достижима из начальной маркировки, однако она не покрывается, так как после получения
μ
переход t1 запустить уже нельзя и фишки после дальнейшего запуска t3 лишь перераспределяются между p2 и p4.
Обе задачи решить по усеченному ДД затруднительно, так как оно не дает информации о соотношении фишек в p2 и p4.
   

Анализ свойств сетей на основе использования матричного подхода: матрицы D-, D+, пример построения матриц для сети Петри.
Один из подходов к анализу свойств СП основан на матричном представлении сетей, в соответствии с которым сеть представляется четверкой:
 
С=(P, T, D–,D+),
где Р – множество позиций , |P| = п;
T – множество переходов, |T|=т;
D–– матрица, описывающая входную функцию, D–[j,i]=#(pi, I(tj));
D+– матрица, описывающая выходную функцию, D+[j,i]=#(pi, O(tj)).
     
D–: Первая строка отвечает за переход t1. Первые три элемента в строке равны 1, так как из позиций p1, p2, p3 идут дуги к переходу t1.
 
 
Составная матрица изменений (матрица инцидентности). Пример. Замечания по применению матричного подхода.
Рассмотрим m-мерный булев вектор е[j].Например, для перехода t2, если m=5, то e[j]=(0, 1, 0, 0, 0).
Переход tj в маркировке μ разрешен, если μ е[j]D–.
Результат запуска tj в μ: δ(μ, tj)= μ'=μ-е[j]D–+е[j]D+.
Вынесем е[j] за скобку: δ(μ, tj)=μ'=μ+е[j]D, где D=-D–+D+
Замечания по применению матричного подхода
1) Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц D- и D+, но затем взаимно уничтожаются в матрице D=D+-D-.
2) При вычислении матрицы D, если СП содержит петли, теряется информация о кратности дуг.
   



Лекция, реферат. Решение задачи покрываемости и достижимости сетей Петри на основе дерева достижимости. - понятие и виды. Классификация, сущность и особенности. 2021.

Оглавление книги открыть закрыть




« назад Оглавление вперед »
11. Структура сетей Петри. Граф сети Петри. « | » 11.2 Решение задачи достижимости с помощью матричного подхода.






 

Похожие работы:

Воспользоваться поиском

 

Учебники по данной дисциплине

Шпоры по математике
Общая статистика. Конспект лекций
Статистика коммерческой деятельности