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

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

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

Вершины с  конфликтами  в  сценарии  системы проектирования обрабатываются одинаково.  Для вершин второго типа по построению

. Поэтому  число  конфликтов                      , т.е.

равно числу выходных вершин.

Алгоритм начинается   с  определения  начальной  маркировки корнем графа,  то есть граничной  вершиной.  До  тех  пор,  пока имеются граничные вершины, они обрабатываются алгоритмом.

Пусть х - граничная вершина, которую необходимо обработать.

1. Если  для  маркировки  M[x]  не  один  из  переходов  не разрешен ( то есть                     не  определено  для  всех

), то х - терминальная вершина.

2. Если х - граничная вершина  без  конфликта,  то  создать новую  вершину  z  сокращенного  графа  достижимости.  Вершина z

связывается  с   вершиной   х   ребром,   которое   взвешивается идентификаторами переходов, разрешенными в маркировке M[x].

Маркировка M[z],  связанная с этой  вершиной,  определяется для каждой      позиции      pi      следующим     образом     :

, если  переход             разрешен  в

M[x];  M[z]i=(M[x],tj)i,  если  переход            не разрешен в

M[x].

Если в сокращенном графе достижимости  существует вершина  с маркировкой M[z],  то  вершина  z  не  вводится,  а  используется вершина с маркировкой M[z].

Вершина х переопределяется как внутренняя вершина.

3. Если  х  - граничная вершина с конфликтом,  то создать k

новых граничных        вершин        z1,z2,...,zk,        причем

,  где  m  - число конфликтных вершин в сети

Петри с маркировкой M[x];  lji- число конфликтов  в  позиции  i.

Маркировка  M[zim],  связанная  с  вершиной z,  определяется для каждой позиции следующим образом:                         , если переход                    разрешен в M[x] при данном конфликте;

M[zim]=(M[x],tj)im, если переход            не разрешен  в  M[x]

при данном конфликте.

Вершина zim  связывается  с  вершиной  х  ребром,   которое взвешивается    идентификаторами   переходов,   разрешенными   в маркировке M[x] при данном конфликте.  Если в сокращенном  графе достижимости существует вершина с маркировкой M[zim], то вершина

zim не вводится, а используется вершина с маркировкой M[z].

Вершина х  переопределяется  как внутренняя вершина.  Когда все вершины  дерева  -  терминальные  или  внутренние,  алгоритм останавливается (рис.2.6, 2.7).

Рассмотрим класс начальных маркировок Mn={Mn1,Mn2,...,Mnk}, определяемый множеством всех проектов, которые можно выполнить в системе автоматизированного проектирования. Допустим, для каждой начальной   маркировки   Mni  и  заданной   сети  Петри  системы

С=<P,T,I,O> построен сокращенный граф достижимости Gi.

Определим операцию  объединения  GiUGj  сокращенных  графов достижимости Gi и Gj,  построенных по сети Петри  С=<P,T,I,O>  с начальными маркировками Mni и Mnj соответственно.

Определение 6. Пусть Gi=<Vi,Ui>,  где

Vi={v1i(w1i),v2i(w2i),...,vni(wni)};

Ui={u1i(w1i),u2i(w2i),...,uki(wki)};

Gj=<Vj,Uj>;

Vj={v1j(w1j),v2j(w2j),...,vlj(wlj)};

Uj={u1j(w1j),u2j(w2j),...,vmj(wmj)}.

Причем каждый вес вершины w определяется множеством позиций

w={pi1,pi2,...,pik}, а каждый вес дуги w определяется множеством переходов w={tj1,tj2,...,tjn}.