УДК 681.3 ПОДХОД К КОМБИНИРОВАНИЮ НЕЗАВЕРШЕННОГО МЕТОДА ВЕТВЕЙ И ГРАНИЦ И АЛГОРИТМА ИМИТАЦИОННОЙ НОРМАЛИЗАЦИИ Б. Ф. <...> Мельников, С. Н. Эйрих Тольяттинский государственный университет Поступила в редакцию 01.04.2010 г. Аннотация. <...> В настоящей статье рассматривается гибрид незавершенного метода ветвей и границ и алгоритма имитационной нормализации для решения задач дискретной оптимизации. <...> Основное внимание уделяется исследованию комбинирования алгоритмов, возможностям распараллеливания и возможностям применения алгоритма для всего класса задач. <...> Ключевые слова: Незавершённый метод ветвей и границ, имитационная нормализация, задачи дискретной оптимизации. <...> In this paper, a combination of the truncated branch-and-bound method and simulated annealing for solving discrete optimization problem is considered. <...> Key words: Truncated branch-and-bound method, simulated annealing algorithm, discrete optimization problems. <...> ВВЕДЕНИЕ Для задач дискретной оптимизации характерны такие отличительные признаки как факториальный рост вычислительной сложности и допустимость приближенного решения. <...> Представителями указанного класса задач являются NP-полные задачи оптимизации [1]. <...> В настоящей работе рассматривается гибрид незавершённого метода ветвей и границ и параллельного варианта алгоритма имитационной нормализации для решения NP-полных задач оптимизации. <...> Обоснованием выбора имитационной нормализации для комбинирования служили следующие соображения: — алгоритм основан на простой и ясной идее — и легко реализуем; — алгоритм может применяться почти для всех задач оптимизации; — благодаря стохастическому критерию принятия решений и ненулевой вероятности принятия ухудшенных решений алгоритм не попадает в локальные оптимумы. <...> МЕТОДИКА ЭКСПЕРИМЕНТА ОПИСАНИЕ ЗАДАЧИ Алгоритм, который будет описан в данной работе, применим для решения многих задач © Мельников Б. Ф., Эйрих С. Н., 2010 дискретной оптимизации. <...> В их числе задача коммивояжера (ЗКВ), минимизация недетерминированных конечных автоматов, минимизация дизъюнктивных нормальных <...>