Структурный синтез по альтернативным деревьям

Язык A-деревьев обладает большими выразительными возможностями по сравнению с рассмотренными средствами представления обобщенных структур [4, 7, 18].

Альтернативным деревом (A-деревом) называется вектор (G, S, γ), в котором: G=G(X, D) — корневое ориентированное дерево со множеством вершин X={xi} и множеством дуг D={dj}; S={Sk}—множество названий (номеров) связок; отображение γ: S→ 2D ставит в соответствие каждому имени связки s, принадлежащей S, подмножество дуг γ (s) из множества D, причем все дуги одной связки имеют общую начальную вершину.

Объекты этого типа нашли широкое применение в программировании и в исследованиях по искусственному интеллекту. В этих отраслях знаний их принято называть И—ИЛИ-деревьями.

Рассмотрим правила соответствия между элементами деревьев и обобщенными структурами.

· Корень дерева соответствует основной технической функции класса объектов.

· Висячие вершины (листья) представляют технические реализации.

· Связки дерева описывают способы разбиения технических функций на подфункции.

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

рис. 5. Представление обобщенной структуры в виде А-дерева

Альтернативное дерево составляется для конкретного класса систем, изделий, процессов и описывает обобщенную структуру этого класса. Вершинам дерева могут соответствовать функции, системы, подсистемы, элементы, которые реализуют эти функции, а также признаки функций и систем. Если у вершины альтернативного дерева есть потомки, это означает, что объект, который вершина описывает, имеет структуру. Например, функция сводится к набору подфункций, система—к совокупности подсистем и элементов, признак является агрегированным и выражается через композицию более простых признаков. Концевые вершины (листья) альтернативного дерева соответствуют элементарным, бесструктурным в данном классе объектам: функциям, элементам, признакам.

Для того чтобы получить по A-дереву решение задачи синтеза, нужно выполнить следующую последовательность шагов.

· Выбрать одну из связок, исходящих из корневой вершины.

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

· Продолжать этот процесс до тех пор, пока каждая из полученных вершин-потомков не станет концевой вершиной в альтернативном дереве.

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

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

· Если х—элемент Xn, то Gr состоит из единственной вершины х.

· Если x не принадлежит Xn, и если из х исходит связка K, направленная на вершины {x1, x2, …, xk}, причем существует граф решения, соединяющий вершины из Xn с каждой вершиной хi, i=l, k, то Gr состоит из вершины x, связки К, вершин {x1, x2, …, xk} и графов решения, идущих в Хn из каждой вершины множества {x1, x2, …, xk}.

· Если не выполнены условия 1 и 2, то графа решения, который бы связывал х с Xn, не существует.

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