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

Тогда G=GiUGj есть граф,  определяемый  следующим  образом:

G=<V,U>, причем считается,  что вершины             и идентичны,  если  w(vi)Сw(vj)  или  w(vj)Сw(vi),  результирующая вершина имеет вес w(vj)  или  w(vi)  соответственно  ;  U=UiUUj, причем считается, что дуги            и          идентичны, если

w(ui)=w(uj).  Если w(vi)Сw (vj),  то всем вершинам графа Gi,  из которых  достижима вершина vi,  дописываем вес - w(vj)\w(vi),  а также вершинам,  которые достижимы из vi.  При таком объединении вершин следует учитывать их смежность.  Пусть в графе Gi вершины

vi1 и vi2 инцидентны дуге ui, а в графе Gj вершины vj1  и  vj2 дуге  uj  и  при  этом попарно выполняются условия включения для весов w(vi1) и w(vj1),  w(vi2) и w(vj2).  Мы объединяем  вершины

vi1 и vj1.  При этом вершины vi2 и vj2 объединяются только в том случае, если w(vi1)Cw(vj1) и w(vj1)\w(vi1)=w(vj2)\w(vi2).

Определение 7. Сокращенным  графом  достижимости  системы с сетью Петри  С=<P,T,I,O>  и  множеством   начальных   маркировок

Mn={Mn1,Mn2,...,Mnk} назовем граф                (рис.2.8).

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

Задачи планирования.  Для того,  чтобы по множеству входных моделей  {pi1,pi2,...,pin}  и выходных моделей {pj1,pj2,...,pjm}

определить  возможность   реализации   проекта,   необходимо   в сокращенном  графе достижимости системы найти две вершины:  v1 с весом M1 и v2 с весом M2, для которых существует путь от вершины

v1 к  вершине  v2  и  M1\(M2^M1)С{pi1,pi1,...,pin};{pj1,pj2,...,

pjm}СM2 (1).

Если множество  входных  моделей  задано не полностью,  то, чтобы определить  множество  входных  моделей,  необходимых  для получения  заданных  выходных моделей,  надо найти в сокращенном графе достижимости системы вершину v2  с  весом  M2  такую,  что функционал J2=J(M2',{pj1,pj2,...,pjm}) минимален,  и вершину v1, причем   существует   путь   от    вершины    v1    к    v2    и

J1=J(M1',{pi1,pi2,...,pin}) минимальна и не содержит конфликтных вершин   второго  типа,  то  есть  позиций  типа  p,   так   как фактически  они  не  соответствуют  никакой  входной  модели,  а являются лишь фиктивной входной (выходной) моделью и  служат для отражения  различных  ситуаций  формирования  выходных моделей в зависимости  от  работы  модуля.   Здесь   M1'и   M2'-множества, соответствующие комплектам   M1   и  M2.  Здесь  J(x)  некоторый функционал,  характеризующий  трудоемкость   получения   моделей множества   x.   Вид   функционала   определяется  экспертом.  В

простейшем  случае он  может  вычисляться как мощность множества

!w(v)\x!:

J1=!  1!=!M1'\{pi1,pi2,...,pin}!

J2=!  2!=!M2'\{pj1,pj2,...,pjm}!

Решение этой  задачи  осуществляется  известным  алгоритмом

Дейкстры [32, 37], приведенном в Гл.3 настоящей работы.

Тогда множество входных моделей,  необходимых для получения заданных выходных моделей, будет определяться следующим образом:

{pi1,pi2,...,pin}UM1\(M2^M1).

Для определения  последовательности  и  порядка  выполнения модулей,  необходимых  для  реализации  данного  проекта,   надо выписать  последовательно  веса  всех  дуг  пути,  полученного в предыдущем  случае.   Причем   если   переходы   tj1,tj2,...,tjn

взвешивают  одну  дугу,  то  модули,  соответствующие  переходам

tj1,tj2,...,tjn, можно выполнять параллельно.

Множество данных,  которые  необходимо  хранить  на  каждом этапе    проектирования,    определяется   следующим    образом:

MiU(M1\(M2^M1)), где Mi - вес вершины vi полученного пути.

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

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

{vj(wj) / wj(vj)СMo} и  найти  все  вершины  сокращенного  графа достижимости, в которые существует путь из выделенного множества вершин.  Множество,  являющееся объединением  множеств,  которые соответствуют комплектам весов найденных вершин,  будет являться подмножеством Mt;