Структурный синтез с ограничениями на основе N-дольных графов

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

N-дольным называется граф вида G=(X, R), где множество вершин X разбито на совокупность непересекающихся подмножеств X1ИX2И…ИXN, а из существования ребра r=(z, y) следует, что инцидентные ребру вершины принадлежат разным подмножествам, т.е. zОZ, yОZ, Z, Y НX и Z№Y. Подмножества вида Xi принято называть долями графа. Из определения следует, что все доли являются независимыми множествами вершин.

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

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

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

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

Обоснуем достаточность. Предположим, что существует N-вершинный полный подграф, который не является корректным решением задачи структурного синтеза. Это возможно только в случае, когда существуют по крайней мере две вершины, принадлежащие одной доли графа. Это предположение противоречит полноте решающего подграфа, поскольку по определению N-дольного графа его доли являются независимыми подмножествами.

Проиллюстририруем предложенный формализм примером небольшого фрагмента очень простого класса технических устройств «Портативные электрические фонарики». Функциональная структура этого класса показана на рис. 6.

рис. 6. Функциональная структура класса «Портативный электрический фонарик»

На рис. 7 представлен многодольный граф, построенный по заданной функциональной структуре. Легко проверить, что любой полный трехвершинный подграф этого графа представляет собой возможную компоновку электрического фонарика. Все немногочисленные запреты связаны с элементом под номером 10, который не может сочетаться в одном решении с некоторыми типами конструктивного исполнения и источниками света.

рис. 7. Представление обобщенной структуры в виде многодольного графа

В приведенном формализме требование разложимости графа на несколько долей не ограничивает общность постановки задачи. Анализ показывает, что любой граф можно разложить на совокупность долей, вершины которых не связаны друг с другом. Такое представление возможно даже для самых плотных типов графов — полных графов с произвольным числом вершин. На рис. 8 такое разложение показано на примере полного четырехвершинного графа.

рис. 8. Представление полного четырехвершинного графа в многодольном виде

Это значит, что для поиска структурных решений по многодольным графам не требуется изобретать никаких специализированных алгоритмов. Для этих целей можно воспользоваться стандартными схемами, которые предложены для графов общего вида. В работах по теории графов показывается, что задача поиска полного подграфа с фиксированным числом вершин может быть решена несколькими разными способами: как напрямую, так и при помощи сведения к графовым конфигурациям другого вида. Так, хорошо изучен метод, когда исходная задача сводится к поиску независимого множества в дополнительном графе, который, в свою очередь, формулируется как задача покрытия транспонированной матрицы инцидентности [5]. В [1] рассматривается еще одна возможная схема решения данной проблемы, которая формулируется как задача об изоморфном вложении графов.

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

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

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

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

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

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

Более формально, дополнением графа G=G(X, R) называется граф L(G)=L(X, D), причем ребро r=(x, y) существует в G тогда и только тогда, когда аналогичные вершины не связаны ребром d=(x, y) в графе L. Очевидно, что объединение любого графа и его дополнения дает в итоге полный граф на том же множестве вершин, который содержит n*(n-1)/2 ребер.

Поскольку сумма ребер основного графа и его дополнения — есть величина постоянная, то большое число ребер в одном образовании означает их дефицит в его дополнении. Так, для многодольного графа, приведенного на рис. 7, его дополнение (рис. 9) представляет собой намного более компактную формацию.

рис. 9. Представление дополнительного графа

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

рис. 10. Редуцированное представление многодольного графа

Приведем некоторые выводы, следующие из изложенного:

· Задача структурного синтеза — это одна из важнейших задач в проектировании технических систем и процессов. Она решается для всех типов и видов объектов, независимо от их отраслевой принадлежности и выполняемых функций. К этому классу принадлежат и простейший выбор изделия из каталога стандартных решений, и сложнейшие методики синтеза, требующие усилий коллективов высококвалифицированных разработчиков. Во многих проектных ситуациях решение задачи структурного синтеза исчерпывает объем проектных работ.

· Формализации задачи структурного синтеза — это важнейшее условие создания полнофункциональных систем автоматизированного проектирования и технологической подготовки производства. Можно утверждать, что эта проблема является центральной и для теории проектирования и теории технических систем.

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

· Аппарат многодольных графов позволяет описать бинарные запреты на сочетания элементов очень компактным и естественным способом. Для поиска корректных структурных решений можно применить хорошо разработанные схемы генерации полных подграфов с фиксированным числом вершин.

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

Список литературы

1. Алгоритмы и программы решения задач на графах и сетях/ под редакцией Нечепуренко М.И. — Новосибирск: Наука, Сибирское отделение, 1990

2. Белоусов А.И., Ткачев С.Б. Дискретная математика М.: МГТУ, 2001

3. Глазунов В.Н. Поиск принципов действия технических систем М.: 1990

4. Голдовский, Б.И., Вайнерман М.И. Рациональное творчество М, Речной транспорт, 1990

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи М.: Мир, 1982

6. Дубов Ю.А. и др. Многокритериальные модели формирования и выбора вариантов систем М.: Наука, 1986

7. Евгенев Г.Б. Системология инженерных знаний. М.: МГТУ 2001.

8. Закревский А.Д. Алгоритмы синтеза дискретных автоматов М.: Наука, 1971

9. Исследования по теории структур. Сборник статей. Новосибирск.: Наука, 1986

10. Кандырин Ю.В., Шкурина Г.Л. Процедуры генерации и выбора при проектировании технических объектов Волгоград, 1999

11. Капустян В.М., Махотенко Ю.А. Конструктору о конструировании атомной техники М, Атомиздат, 1981

12. Кристофидес Н. Теория графов. Алгоритмический подход М: Мир, 1978

13. Кругликов Г.И. и др. Основы технического творчества М, Народное образование, 1995

14. Лабковский Б.А. Наука изобретать Санкт-Петербург: Нордмет, 2000

15. Мюллер И. Эвристические методы в инженерных разработках М, Радио и связь, 1984.

16. Норенков И.П. Основы автоматизированного проектирования. М.: МГТУ, 2000.

17. Одрин В.М. Картавов С.С. Морфологический анализ систем. Киев: Нукова Думка, 1977.

18. Половинкин А.И. Основы инженерного творчества М, Машиностроение, 1988