Рис. 6. Функции, реализующие требования
Рис. 7. Наличие общих исходных кодов
задачи, в которой учитывается пересечение подмножеств исходных
кодов, относится к классу NP-трудных задач [3].
Методы решения NP-трудных задач.
Для решения задач такого
класса не найдено точных алгоритмов, работающих за полиномиаль-
ное время (хотя и не доказано, что их не существует). Это фактически
означает что, решая NP-трудную задачу, не имеет смысла искать точ-
ный алгоритм, а следует воспользоваться одним из распространенных
приближенных методов. К таким методам относятся метод случайного
поиска (последовательность случайных выборов вариантов решения);
псевдополиномиальные алгоритмы (подкласс динамического програм-
мирования); метод локальных улучшений (поиск лучшего решения в
некоторой окрестности допустимого); генетические алгоритмы.
Применительно к поставленной задаче были рассмотрены все пе-
речисленные методы, а также методы полного перебора и ветвей,
и границ (идея отсечений заведомо неоптимальных решений целы-
ми классами в соответствии с некоторой оценкой). Для всех них
(за исключением генетических алгоритмов, которые нецелесообразно
использовать для данной задачи) были построены оценки вычисли-
тельной сложности, они приведены далее. Жадный алгоритм Радо–
Эдмондса, используемый для поиска начального решения, также рас-
сматривается в качестве вспомогательного метода.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3 27
