Рис. 3. Пересекающиеся подмножества исходных кодов
условию задачи для каждого требования может быть более одной ре-
ализующей его функции, то их следует выбирать так, чтобы число
общих исходных кодов для них было максимальным, но при этом
сопоставленное каждой функции число исходных кодов было мини-
мальным. Для такой комбинаторно-оптимизационной задачи следует
использовать автоматизированный поиск решения.
Постановка задачи.
Итак, задача ставится следующим образом:
среди сопоставленных функциям подмножеств исходных кодов, соот-
ветствующих всем возможным вариантам реализации выставленных
требований, выбрать подмножества, объединение которых будет со-
держать минимальное число исходных кодов.
На рис. 4 приведены четыре примера выбора оптимального под-
множества функций. В каждом из четырех примеров представлены
два требования и по две функции к каждому требованию. Требуется
выбрать по одной функции для каждого требования так, чтобы мощ-
ность объединения выбранных функций была наименьшей из всех
возможных. Жирным выделены выбранные функции. Объединение их
исходных кодов является минимальным в каждом примере, реализу-
ющим все выставленные требования. Для нахождения подмножества
функций с минимальным числом исходных кодов следует осуществить
поиск среди групп из
n
функций, где
n
равно числу выставленных
требований, т.е. каждому требованию соответствует одна функция.
Данную задачу целесообразно решать как прикладную задачу струк-
турного синтеза [1] с оптимизацией на графах.
Построим модель объекта проектирования. На рис. 3 представлена
предметная область в виде гиперграфа, но для данного метода такое
представление должно быть видоизменено. Для приведенного гипер-
графа построим соответствующий ему обыкновенный неориентиро-
ванный граф, руководствуясь следующими правилами. Каждому ребру
гиперграфа поставим во взаимно-однозначное соответствие вершину
нового графа. В новом графе вершины будут обозначать функции, ре-
бра — наличие общих исходных кодов у двух функций. Вершины и
24 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3
