|
Algorithms
Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа
А. Н. Максименко Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14, Ярославль, 150003, Россия
Аннотация:
В настоящей работе рассматривается понятие линейного разделяющего алгоритма прямого типа, введенное В. А. Бондаренко в 1983 г. Понятие алгоритма прямого типа определяется с помощью графа решений задачи комбинаторной оптимизации. Вершинами этого графа служат все допустимые решения задачи. Два решения называются смежными, если существуют входные данные, для которых эти решения и только они являются оптимальными. Ключевой особенностью алгоритмов прямого типа является то, что их трудоемкость оценивается снизу кликовым числом графа решений. В 2015-2018 гг. было опубликовано пять работ, основными результатами которых являются оценки кликовых чисел графов многогранников, ассоциированных с различными задачами комбинаторной оптимизации. В качестве основной мотивации в этих работах приводится тезис о том, что класс алгоритмов прямого типа является широким и включает в себя многие классические комбинаторные алгоритмы, в том числе алгоритм ветвей и границ для задачи коммивояжера, предложенный J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel в 1963 г. Мы покажем, что этот алгоритм не является алгоритмом прямого типа. Ранее, в 2014 г., автором настоящей работы было показано, что венгерский алгоритм для задачи о назначениях не является алгоритмом прямого типа. Таким образом, класс алгоритмов прямого типа не является настолько широким, как предполагалось ранее.
Ключевые слова:
метод ветвей и границ, задача коммивояжера, линейное разделяющее дерево, кликовое число, алгоритм прямого типа.
Поступила в редакцию: 03.12.2019 Исправленный вариант: 05.01.2020 Принята в печать: 28.02.2020
Образец цитирования:
А. Н. Максименко, “Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа”, Модел. и анализ информ. систем, 27:1 (2020), 72–85
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais704 https://www.mathnet.ru/rus/mais/v27/i1/p72
|
|