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

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

Возьмем и    вершину   графа    обозначим   vo(wo);   дуги, инцидентные этой   вершине   -                     ;    вершины, инцидентные этим дугам  v1(w1), v1'(w1'),... и т.д., далее  дуги

u1(w ), u1'(w '),... и т.д. Теперь сформулируем свойства:

1. wo(vo) \ w1(v1)СMo  1)

1) - штрихи опущены у обозначений вершины wi(vi)

2.

* - расширенная функция следующего состояния, получаемая в результате одновременного запуска переходов  w(vi):

w1(v1)  = w1(v1)^wo(vo)UM1

3.                             i = 2, 3,... n, где n-длина пути в подграфе wi(vi) = wi(vi)^wi-1(vi-1)UMi.

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

(wo(vo)^w1(v1)) \ Mo.

Предложенные формальные   соотношения  обозначают  то,  что модели,  взвешивающие вершины  сокращенного  графа  достижимости

wi(vi)  и  не  входящие  в множество моделей Mo,  не участвуют в дальнейших преобразованиях.   То   есть,   фишки   в   позициях, соответствующих указанным моделям, не перемещаются по сети Петри системы по мере  запуска  переходов  wj(vj),  взвешивающих  дуги выделенных подграфов сокращенного графа достижимости.

Задача диагностики.  Для  определения   множества   входных моделей Min, с помощью которых можно получить заданное множество выходных Мо, используя систему проектирования, следует:

выделить множество  вершин  сокращенного графа достижимости

{vj(wj) / MoСwj(vj) };

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

1. Выделить вершины            такие,  что существует дуга, инцидентная   vj(wj)   и                 и    направленная    от к           , и веса вершин удовлетворяют условию:

1.

2.

В множество вершин  включается  вершина             ,  а  в множество   маркировок,   из   которого  может  быть  достигнута маркировка Мо, маркировка                          .

2. На  k-м  шаге выделить вершины                такие, что существует дуга,  инцидентная               и                  и направленная от                к               , и  веса  вершин удовлетворяют условию:

1.

2.

В множество  вершин  включается вершина              ,  а в множество маркировок маркировка                           .

Выполнять эту   процедуру   до   тех  пор,  пока  не  будут выполняться указанные условия.

Задачи прогнозирования  и  диагностики могут быть сведены к решению задачи планирования. Если решается задача планирования и множество  входных моделей равно пустому множеству,  то мы имеем задачу  диагностики.  Если  решается   задача   планирования   и множество  выходных  моделей  равно  пустому  множеству,  то это задача прогнозирования.  При этом  для  решения  рассматриваемых задач  в полном объеме критерии минимальности     и      следует исключить.

Эти задачи могут быть также решены путем моделирования сети

Петри.  Для решения задачи прогнозирования используется исходная сеть Петри с Мо в качестве начальной маркировки.

Для решения задачи диагностики используется сеть  Петри,  в которой  входные и выходные функции меняются местами.  Начальная маркировка остается той же самой. Отличие задачи прогнозирования от  задачи  диагностики  состоит  в  том,  что  решением  первой является множество позиций,  которые могут быть промаркированы в процессе  проектирования;  решением  второй  является  множество маркировок, из которых может быть достигнута маркировка Мо (либо для  обратной  сети это просто множество достижимости R(C',Mo)).

Множество маркировок является множеством множеств позиций.