Жадный алгоритм Радо–Эдмондса, не учитывающий пересечений,
находит решение за линейное время. Методы динамического програм-
мирования и локальных улучшений работают за полиномиальное вре-
мя, однако не гарантируют нахождения точного решения. Методы пол-
ного перебора ветвей и границ обеспечат точное решение, но время
работы оценивается как степенная зависимость. На приведенном гра-
фике метод ветвей и границ показывает достаточно хорошие резуль-
таты (близкие к методу локальных улучшений), однако с ростом
n
значение функции резко возрастает.
Выводы.
Рассмотрена комбинаторно-оптимизационная задача вы-
бора оптимального набора исходных кодов для переноса функциональ-
ных возможностей с учетом общих исходных кодов и без. Получены
две постановки задачи, относящиеся к классам сложности NP и P
соответственно.
Задачу класса сложности NP предложено решать как задачу струк-
турного синтеза. Рассмотрена возможность применения пяти различ-
ных методов нахождения результирующего множества функций, про-
ведены оценки сложности вычислений. Полученные результаты гово-
рят о целесообразности использования методов динамического про-
граммирования и локальных улучшений.
СПИСОК ЛИТЕРАТУРЫ
1. Б о ж к о А. Н., Т о л п а р о в А. Ч. Структурный синтез на элементах с огра-
ниченной сочетаемостью // Наука в образовании: электронное научное издание.
– № 5. – 2004.
2. Т о м а с Х. К о р м е н. Алгоритмы: построение и анализ. – М.: Вильямс, 2006.
3. Г э р и М., Д ж о н с о н Д. Вычислительные машины и труднорешаемые зада-
чи. – М.: Мир, 1982.
4. О в ч и н н и к о в В. А. Алгоритмизация комбинаторно-оптимизационных за-
дач при проектировании ЭВМ и систем. – М.: Изд-во МГТУ им. Н.Э. Баумана,
2001.
Статья поступила в редакцию 16.09.2008
Татьяна Николаевна Романова окончила МГУ им. М.В. Ломоносова. в 1980 г. Канд.
физ.-мат. наук, доцент кафедры “Программное обеспечение ЭВМ и информационные
технологии” МГТУ им. Н.Э. Баумана. Автор 8 научных работ в области программи-
рования и аэрогидродинамики.
T.N. Romanova graduated from the Lomonosov Moscow State University in 1980. Ph.
D. (Phys.-Math.), assoc. professor of “Computer Software and Information Technologies”
department of the Bauman Moscow State Technical University. Author of 8 publications
in the field of programming and aero-hydrodynamics.
Алексей Викторович Анисимов родился в 1982 г., окончил МИФИ в 2005 г. Аспирант
кафедры “Программное обеспечение ЭВМ и информационные технологии” МГТУ
им. Н.Э. Баумана. Автор 5 научных работ в области конфигурационного управления
и управления изменениями в исходных кодах.
A.V. Anisimov (b. 1982) graduated from the Moscow Engineering and Physics Institute
in 2005. Post-graduate of “Computer Software and Information Technologies” department
of the Bauman Moscow State Technical University. Author of 5 publications in the field
of configuration management and control of variation in source codes.
32 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3
