Алгоритм распознавания изоморфного вложения алгоритмических сетей

Проблeма снижeʜия барьepa мeжду поль-зоватeлeм и ЭВМ появилась сразу жe, как появилась ЭВМ, и остaeтся актуальной и в насто-ящee ʙpeмя. Эта проблeма формулиpyeтся как задача разработки дружeстʙeʜʜoго интepфeйса. Одним из путeй peшeʜия проблeмы являeтся использованиe графичeского пpeдставлeʜия, котopoe можeт peaльно умeʜьшить барьep мeж-ду чeлoʙeком и ЭВМ. В этом ряду стоит и формализм алгоритмичeских сeтeй, пpeдназначeʜ-ный для описания алгоритмичeских модeлeй, пpeдложeʜʜый В.В.Иванищeʙым около 30 лeт назад [1]. Под алгоритмичeской модeлью пони-мaeтся формализoʙaʜʜoe oписаниe сцeʜapия пpeдмeтного спeциалиста для модeлиpyeмого процeсса, структура которого сопоставима со структурой причинно-слeдстʙeʜʜых и ʙpeмeʜ-ных зависимостeй мeжду явлeʜиями модeлиру-eмого процeсса, вмeстe со всeй информациeй, ʜeoбходимой для ee программной peaлизации.

Разработка теории алгоритмических сетей, методов представления моделей на основе данного формализма и построение систем автоматизации моделирования выполнялись в Санкт-Петербургском институте информатики и автоматизации РАН [3]. Алгоритмические сети использовались для создания ряда моделей, которые эксплуатировались в различных организациях (например, Госплан РСФСР) и используются и в настоящее время. Однако язык представления требует средств поддержки автоматизированного построения моделей. Актуальным моментом автоматизации построения моделей является возможность использования фрагментов ранее созданных моделей, использование баз данных моделей.

Прежде чем перейти к описанию методов поиска фрагментов в базах моделей введем их формальные определения [1].

Алгоритмическая сеть (АС) определяется как ориентированный гиперграф без петель при вершинах G(VX), в котором дуги обозна чают модельные переменные xiеX, i = 1> n, а вершины Vjе V - функциональные соотноше- ния (операторы), f еF, j = 1 m, связывающие модeльныe значeʜия пepeмeʜʜых на интepʙaлe времени, соответствующем At [3].

Структура пepeмeʜʜыx

X = X _ии X ,ых и X _; н , где X _и, X _ibK, X _!Н

-

ceти соответ-

ственно входные, выходные и внутренние переменные, причем, X _вх n X _;ых= 0 , X _вх n X _;н= 0 , X _)ых n X , _н= 0 . Учитывая, что все вершины AC наблюдаемы, можно задать X = X _вх u X _выч, X _)ыч -вычисляемые переменные AC, X _)ыч = X _)ых u X _вн, где X в _ыч - вычисляемые переменные.

Формально алгоритмическая сеть (AC) может быть определена следующим образом:

AC:=< P , Q , X , F , P > F , Q > X >, (1) где P - множество вершин сети; Q - множество дуг сети; X - множество переменных, при этом X = u Xi ; Xi - множество переменных i -й вершины; I - множество всех индексов вершин; F - множество операторов; P > F - изоморфное отображение P на F , т.е. индекс оператора можно считать индексом вершины; Q > X - отображение Q на X .

Оператор f е F описывается как:

ft :=< X^f Xi 'out >, (2)

где Xiin, Xiout - множество входных и выходных переменных оператора, f - символ операции или функции. Для некоммутативных операторов в Xiin, Xiout должен быть задан частичный порядок для их элементов. Так, для операции вычитания в Xiin необходимо отметить уменьшаемое, порядок следования остальных переменных несущественен. В общем случае f мо-жeт быть имeнeм нeкоторого программного модуля или другой AC. Операторы могут быть определены над действительными числами, логическими переменными, скалярами, векторами, матрицами, информационными структурами идр. В состав операторов AC включается оператор задержки, который задает исходное состояние моделируемому процессу и описы-ваeт пeрeход модeли на слeдующий шаг или определяет задержку появления некоторой переменной в части AC. В АС допускаются контура, только если они включат в себя оператор задержки. AC будем называть канонической, если все операторы задержки определяют ре-куррeнтныe соотношeния относитeльно одной и той же величины и с одинаковым шагом ее изменения. Иными словами, в канонической AC все операторы задержки срабатывают одновре-мeнно и обecпeчивают формированиe одного внешнего цикла счета операторов сети. В дальнейшем рассматриваем именно такие АС.

Алгоритмическая модель    (АМ)

формально определяется:

АМ::=

X >T, F >T>,               (3)

где IM - идентификатор модели; OPO - описание предметной области; IO - описание объекта, для которого разработана модель; OP - описание процесса, для которого разработана модель; АС - алгоритмическая сеть (описание структуры модели); T - множество терминов предметной области, используемых в модели, TcTPO, где TPO - множество всех терминов предметной области; MD - множество вариантов законов изменения значений переменных модели; X>T - отображение множества переменных АС модeли в множecтво тeрминов прeдмeтной области, используемых в модели, возможно X’ >T, где XF X; F>T - отображение множecтва опeраторов АС модeли в множecтво терминов предметной области, возможно F‘>T, где F’cF; X >TnF >T 0;

если модель не пуста, то всегда не пусты IM и АС.

Для АС определены отношения равенства и изоморфности. Две АС равны (АС1=АС2), если и только если их множества F совпадают (F1=F2). АС изоморфны (АС1~АС2), если и только если между их множествами F можно определить взаимно-однозначное отображение (F1~F2), при условии что поставленные в соответствие элементы множеств F1, F2 имеют совпадающие символы операций f и одинаковые мощности множеств in(fi) и out(fi). То есть изоморфные АС отличаются друг от друга только обозначениями переменных. Соответственно изоморфное вложение для АМ будем рассматривать как установление изоморфизма одной АС фрагменту другой АС.

Для поиска фрагментов возможны два случая:

• 1.    Все переменные моделей относятся к одному тезаурусу, тогда для поиска фрагментов АС достаточно использовать веденные для АС операции пересечения, на которой основаны алгоритмы установления равенства и вложения [1].

• 2.    Переменные моделей относятся к разным тезаурусам. В данном случае для поиска полной сети может быть использован алгоритм, описанный в [2], но для поиска фрагмента, данный алгоритм не подходит. Необходимо разработать новый алгоритм.

Алгоритм установления изоморфного вложения требует установить соответствие между вершинами двух АС и носит переборный характер. Каждая вершина характеризуется своим индексом, множеством переменных связанной с ней Х_i, символом оператора, сопоставленного вершине fi, который у соответствующих друг другу вершин сравниваемых АС всегда один и тот же. То есть, при установлении соответствия вершин требуется определить соответствие переменных вершин имеющих одинаковые f и одинаковое число входных и выходных переменных.

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

Используем следующее допущение: разбиение множеств вершин каждого из графов на непересекающиеся классы и подклассы, между элементами которых возможно сопоставление имён переменных, должно, как минимум, не увеличивать, а зачастую уменьшать число возможных вариантов сопоставления имён переменных сравниваемых сетей; увеличение числа классов и подклассов увеличивает вероятность снижения числа вариантов, рассматриваются только связные АС (имеющие только одну компоненту связности).

Проведём предварительное преобразование анализируемых АС. Разорвем контура на входах операторов задержек и выполним для обеих АС их упорядочение по уровням вычислимости. То есть первый уровень будет состоять только из тех вершин, которые могут быть вычислены только на основании входных переменных, второй из тех вершин, в которых хоть одна входная переменная вычисляется в первом уровне (но не в других уровнях) и т.д., выходы операторов задержки рассматриваем как входные переменные. В результате в каждой АС множества вершин разобьётся на классы. Каждая вершина в АС характеризуется собственными |in(fi)| (множество входных переменных оператора), |out(fi)| (множество выходных переменных оператора) и f (символ операции с индексом), соответствующим ей уровнем вычислимости и списком вершин АС, связанных с ней или по входу или по выходу. Каждая вершина из такого списка также характеризуется собственными |in(fi)|, |out(fi)| и fi, соответствующим ей шагом алгоритма. Все вершины, имеющие одинаковые перечисленные характеристики, попадают в один класс. Таким образом, имеем достаточно подробное деление на классы, которое в подавляющем большинстве практических случаев обеспечивает наличие одного или нескольких классов вершин состоящих из одного элемента, что существенно сокращает число возможных сопоставлений, а в ряде случаев однозначно определяет возможность переобозначения переменных в одной из АС. Реализация алгоритма разбиения на классы требует многократных просмотров множества F, но, в силу своей однонаправленности и однозначности определения принадлежности вершины к какому-либо классу, будет иметь полиномиальную оценку верхней границы сложности.

АС изоморфно вложимы (обозначим это ~сАС1), если и только если между их множеством F2 и некоторым подмножеством F1 можно определить взаимно-однозначное отображение (изоморфизм), при условии что поставленные в соответствие элементы множества F2 и подмножества F1 имеют совпадающие символы операций fi и одинаковые мощности множеств |in(fi)|, |out(fi)|. То есть изоморфные АС отличаются друг от друга только обозначениями переменных.

Алгоритм распознавания изоморфности АС построен на основе аналогичных алгоритмов распознавания строгой эквивалентности алгоритмов. На изоморфность имеет смысл проверять только сети, имеющие одинаковое число классов вершин, и если соответствующие друг другу классы равномощны. Алгоритм организует просмотр всех возможных вариантов переобозначения и заключается в по- очерёдном просмотре вершин одной АС и выделенных классов в другой и выбор для каждой вершины одной АС вершины другой АС, принадлежащей к тому же классу, переобозначению переменных выбранной вершины, с учётом ранее сделанных переобозначений. Если возникли противоречия с ранее сделанными переобозначениями, то формируется другой вариант преобразования для анализируемой вершины. Если таких элементов в классе нет, то запоминается вариант переобозначения для всех ранее переобозначенных вершин как недопустимый и возвращаются к началу просмотра и т.д. Если удалось найти хотя бы один вариант переобозначения, то сети изоморфны. Если варианта переобозначения не найдено, то сети не изоморфны. Предпочтительно начинать анализ с классов, имеющих наименьшее число элементов. Данный алгоритм подробно рассмотрен в [2]. Однако он не решает про-бл ему нахождения подмножества F2, с которым должен устанавливаться изоморфизм.

Рассмотрим теперь процесс поиска фрагмента АС1, который может быть эквивалентен АС2. Прежде всего необходимо, чтобы число уровней вычислимости в АС1 было не менее чем в АС2, далее, чтобы мощности и число всех выделенных подклассов АС1 в каждом уровне были не менее чем в АС2. После данных проверок начинается собственно работа алгоритма распознавания изоморфного вложения. Данный алгоритм отличается от алгоритма, имеет в своей основе идею несколько отличную от идеи, изложенной в предыдущей статье [3]. Прежде всего строится граф связей между классами АС2. Связь между классами означает, что хотя бы один элемент класса связан с хотя бы одним элементом другого класса, дуги между классами не имеют наименований. Аналогично строится граф связей классов для АС1. Правила операций над графами классов принимаем такие же, как над АС [1]. Далее проводим операцию