Методы структурного синтеза

Синтез ВС и вычислительных процессов (ВП) включает три этапа:

· выбор типовых элементов структуры (синтез базиса);

· построение структуры (структурный синтез);

· параметризация элементов структуры (параметрический синтез).

Выбор типовых элементов структуры выполняется эмпирически. Для формализации используют матрицу «элементы — свойства» (или, что то же самое, матрицу «средства — цели»). Строкам этой матрицы соответствуют различные альтернативные элементы, выполняющие одни и те же функции, а столбцам — свойства этих элементов, важные для проектируемой ВС (ВП). В каждой клетке матрицы по балльной системе проставляется экспертная оценка i-го свойства у j-го элемента. Анализ этой матрицы проектировщиком позволит составить наглядное и достаточно полное представление о приемлемости того или иного элемента.

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

1) Выбор из готовых структур-прототипов. Этот прием предполагает наличие библиотеки готовых структур. Основной недостаток — необходимость прямого перебора всех структур. Если подобрать полностью подходящую структуру не удается, выбирают наиболее близкую и модифицируют ее под заданные требования путем удаления или добавления новых элементов, введения дополнительных или исключения ненужных связей и т. д.

2) Построение частной структуры из общей. В этом случае сначала создают структуру с максимальной избыточностью, являющуюся обобщением всех известных структур объекта данного типа. Нужная структура синтезируется путем удаления лишних элементов и связей обобщенной структуры. Этот прием традиционно используется при синтезе вычислительных процессов, когда обобщенный процесс представляет собой цепочку всех вычислительных операций, применяемых для изготовления объекта данного класса, а синтез состоит в выборе из этой цепочки только тех операций, которые нужны в каждом конкретном случае. Так как выбор выполняется самим разработчиком на основе своего опыта, этот прием, как и предыдущий, относится к методам эмпирического синтеза.

3) Направленный поиск по И—ИЛИ «дереву». Этот прием можно рассматривать как специальный случай построения частной структуры из общей. В качестве общей структуры выступает заранее составленное И—ИЛИ «дерево», в котором каждая группа путей от корневой вершины через вершины И, ИЛИ до терминальных вершин соответствует одной частной структуре
(рис. 3.5). Синтез по И—ИЛИ «дереву» удобно применить в тех случаях, когда объект легко декомпозируется на составляющие его части, которые декомпозируются на еще более мелкие и т. д., каждая декомпозиция порождает вершину типа И, а каждый уровень декомпозиции — ярус «дерева» из вершин И. Альтернативные варианты реализации каждой части объекта порождают вершину типа ИЛИ. Ветви «дерева», выходящие из вершин ИЛИ — имена способов реализации этих частей или их свойств, играющих определенную роль при синтезе. В качестве примера на рис. 3.5 приведено «дерево» И—ИЛИ для некоторого абстрактного объекта, который декомпозируется на части а, b, затем каждая из них соответственно на части c, d и e, f, g, h.

Рис. 3.5 – Структура И-ИЛИ дерева, где
1, 4, 5, 6 – вершины И; 2, 3, 8, 9 – вершины ИЛИ;
10, 11, 12, 13, 14, 15, 16 – терминальные вершины

Части a, c, h могут быть реализованы соответственно способами a₁, a₂, c_1, c₂, h₁, h₂. При этом способ декомпозиции части а на с и d не зависит от способа реализации части а (a₁ или a₂), тогда как способ декомпозиции части b — зависит (при реализации b₁, то b делится на е и f, а при реализации b₂ или b₃ — на g и h). Очевидно, если «дерево» состоит только из вершин И, то оно описывает одну структуру объекта. Альтернативный выбор структуры определяется вершинами ИЛИ. Обход «дерева» из вершин ИЛИ возможен либо в глубину, либо в ширину. При этом с каждой альтернативной реализацией (a₁ или a₂; c₁, c₂ или c₃ и т. д.) связывается оператор перехода, разрешающий переход в следующую вершину И только при выполнении определенных ограничений в вершине ИЛИ. Ограничения могут быть глобальными, относящиеся ко всему объекту (общая масса или общая стоимость ВС, общее время вычислительного процесса и т. д.), и локальными, относящимися к данной реализуемой части объекта (условия стыковки с другими ЭВМ, ВС; ограничения на параметры части ВС).

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

Направленный поиск по «дереву» состояний и свойств. Структурно-параметрический синтез можно выполнить не только на основе И—ИЛИ «дерева», но и с помощью «дерева» состояний и свойств (рис. 3.6).

Рис. 3.6 – Дерево состояний и свойств

Каждая вершина в этом «дереве» трактуется как задача, возможное решение которой обладает свойствами , а каждый оператор перехода имеет смысл: «Если решение задачи -1 должно обладать свойством а, то перейти к решению задачи ». Таким образом, чтобы решение задачи обладало свойством , нужно решить задачу , а чтобы решение задачи обладало нужным свойством , нужно решить задачу . Корневое состояние имеет смысл исходной задачи, промежуточные состояния , — смысл промежуточных задач, на которые разбивается исходная задача синтеза, а , , , , — смысл базовых, терминальных, неделимых далее подзадач. Рассмотрим методику синтеза. Пусть известно, что решение должно одновременно удовлетворять свойствам (а, b, h, с). Нужно найти терминальную вершину, имеющую указанные свойства.

Решение заключается в поиске пути от к той терминальной вершине, которая обладает указанными свойствами a, b, . В этом случае имеем ( ), ( ), (b), ( ), ( , решение должно привести в . Приведенный пример позволяет иллюстрировать некоторые характерные особенности обработки знаний в ИИ при использовании «дерева» состояний.

1) Наследование свойств. Из рис. 3.6 видно, что состояние (c, d) на самом деле кроме свойств с, d должно также обладать и свойством а предыдущей вершины состояние (e, f) — свойством b, а состояние (d, h, c) — свойством . Вследствие этого более точным было бы обозначение этих состояний в виде (c, d, a), (e, f, b), (d, h, c, ). Аналогично можно было бы уточнить запись операторов в виде ; в виде и т. д. Обеспечиваемое последовательным прохождением вершин при поиске по «дереву» передача свойств отцовской вершины к дочерним называется в ИИ «наследованием свойству). Механизм автоматического наследования свойств позволяет упростить запись и реализацию операторов перехода, не учитывая в них свойств предыдущих состояний. Он «по умолчанию» обеспечивает присутствие в последующих состояниях свойств предыдущих. Заметим, однако, что «наследование свойств» в «дереве» поиска необязательно и его можно отменить, если условиться, что «отцовское» и «дочернее» состояние по своим свойствам друг с другом не связаны, например, относятся к понятиям с разной семантикой ( — рабочий, — станок). Если же состояния в «дереве» относятся к одному классу, то механизм наследования свойств позволяет «наращивать» свойства состояний в процессе последовательного раскрытия вершин «дерева». Это особенно важно при решении задач классификации и диагностики.

2) Наследование условий перехода. По аналогии с наследованием свойств состояний можно говорить о наследовании условий перехода в операторах перехода On. Это позволяет объяснить результат поиска. Например, приход к состоянию вызван наличием свойства в и одновременно свойства в , что легко установить, анализируя условия перехода в и . Обычно процесс последовательного применения операторов перехода к раскрытию вершин «дерева» состояний запоминается в программе поиска и может быть легко воспроизведен в виде «трассы поиска», вследствие чего процедуру объяснения результатов часто называют «трассировкой поиска».

3) Поиск правил по образцу. Этот часто используемый в работах по ИИ термин означает, что левая часть правила «если -1 обладает свойством а, то переход к » «сравнивается с образцами», т. е. с перечнем фактически имеющихся имен состояний и их свойств. Совпадение левой части правила с каким-либо образцом вызывает активизацию правила, т. е. срабатывание его правой части. Кроме описанных существует большое число других методов синтеза — метод морфологического ящика, весьма близкий к поиску по «дереву» состояний и «И—ИЛИ-дереву», методы «мозгового штурма» и контрольных вопросов, относящиеся к методам решения изобретательских задач, однако в САПР они не получили распространения из-за сложности их формализации.