Разработка инструментальных средств создания интеллектуального проектировщика САПР на основе сетей Петри (Диссертация на соискание ученой степени кандидата технических наук), страница 27

Петри системы, а Mо - начальная маркировка:

, i=1,2,...,k.

Каждое решение   может   содержать   в   себе  подмножество переходов, срабатывание которых не является необходимым условием для    получения    конечной    маркировки    Мt.    Это   можно проиллюстрировать следующим образом.  Пусть  задана  сеть  Петри

C=<P,T,I,O> (см.рис. 3.2 а).

P= {p1,p2,p3,p4};  Т= {t1,t2,t3}

I(t1) = {p1};           O(t1) = {2p2}

I(t2) = {p2};           O(t2) = {p3}

I(t3) = {p3};           O(t3) = {p4}

Сокращенный граф   достижимости   для  множества  начальных маркировок Мн = {Mн1}, где Мн1 = (1,0,0,0) имеет вид, показанный на рис 3.2 б.

Пусть множество входных позиций определяется как Мо = {p1}, а   множество   выходных   Mt   =  {p3}.  Тогда  решение  задачи планирования  имеет  вид:   vo,u1,v1,u2,v2.   Но  вес  дуги   u2

w(u2)={t2,t3}  содержит  переход  t3,  который  для получения Мt

запускать не требуется.

Для исключения  подобного  рода  ситуаций использован метод

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

Алгоритм    метода  "обратной волны".

Исходные данные: начальная маркировка Мо, конечная маркировка  Мt, сеть Петри системы C = <P,T,I,O>

решение задачи планирования:

vs,u1,v1,u2,...,um,vt

Шаг 1. В весе вершины w'(vt) оставляем только позиции

Mt : т.к. MtCw(vt), то w'(vt) = Mt w(vt) = Mt ,

i = m,  vm = vt,  Mm = Mt

Шаг 2. Пусть дуга ui имеет вес w(ui) = {t1,t2,...,tli}

Найдем множество             для всех tk  w(ui)

в весе  w'(ui)  оставим  только  те  переходы,   для которых O(tk)CGi. При этом O'(tk) = O(tk) Gi.

Шаг 3.  Вес вершины w(vi-1) содержит,  по  построению,  все входные   позиции   переходов,  взвешивающих  ui,  а следовательно, (т.к. w'(ui)  w(ui)) и всех переходов включенных  в  вес w'(ui).  Вес вершины примет новое значение                     для  всех k: O(tk)C Gi.

Шаг 4. Если            ,  и, одновременно,             , то присвоить i = i-1 и перейти к шагу 2. Иначе: получен путь  в  сокращенном  графе  достижимости сети Петри системы.  Измененные веса вершин показывают  ресурсы памяти,  требуемые  на  каждом  этапе,  а веса дуг определяют порядок и  последовательность  выполнения модулей, которое необходимо использовать для решения проектной задачи,  описываемой начальной и  конечной маркировками: Мо,Мt.

Если в  сокращенном  графе  достижимости  найдено несколько маршрутов  между  вершинами  (т.е.  l>1),  то  из  полученных  l

маршрутов  следует  выбрать  оптимальный  по  заданному критерию маршрут.

3.3.   Выбор оптимального пути в сокращенном графе достижимости.

3.3.1. Постановка задачи оптимизации.

Решение задачи планирования процесса проектирования  в САПР

в общем  случае является неоднозначным.  Для выбора оптимального пути следует  выбрать  критерии,  поставить  и   решить   задачу оптимизации.

Выбор оптимального пути связан с  решением  оптимизационной задачи  на сокращенном графе достижимости.  Условия задачи могут быть поставены двумя способами.

Первый способ. В результате работы алгоритма планирования и алгоритма метода "обратной волны" получено l решений задачи:

;

;

........................

.

Требуется выбрать оптимальный путь из l-имеющихся.

Второй способ.  Алгоритм  планирования представляет решение задачи в виде подграфа GD(V,U) сокращенного  графа достижимости.

Предполагается,  что применение метода "обратной волны" к путям, входящим в GD существенных изменений в весах  дуг  и  вершин  не вносит. Требуется выбрать оптимальный путь между вершинами графа

vs  и  vt (либо  парами  вершин    и   , i,j=1,2,...,l, возможно и          для       ).

3.3.2. Критерии оптимизации.

Основными критериями, по которым может быть найден оптимум, являются  критерии,  накладываемые  вычислительными   ресурсами:

быстродействие и память.