Альтернативные графы

Любую морфологическую таблицу можно представить в виде дерева (рис. 1). На рисунке функции представлены вершинами И (темные кружки), значения функций — вершинами ИЛИ (светлые кружки). Очевидно, что таблица представляет множество однотипных объектов, поскольку все они характеризуются одним и тем же множеством функций.

Рис. 1. Дерево, соответствующее морфологической таблтце

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

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

Рис. 2. И-ИЛИ-граф

Если допустить некоторую избыточность при изображении И-ИЛИ-графа, то его можно превратить в И-ИЛИ-дерево, что ведет к определенным удобствам.

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

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

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

(1)

где , если в оцениваемый вариант вошел элемент , иначе . Условие (1) означает, что в допустимую структуру не могут входить одновременно элементы и . Совокупность ограничений типа (1) можно представить как систему логических уравнений с неизвестными . Тогда задачу синтеза можно решать эволюционными методами, если предварительно или одновременно с ней решать систему логических уравнений (задачу о выполнимости).