Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ | Прикладная дискретная математика. 2013. № 2(20).

Для известного алгоритма точного решения задачи коммивояжёра методом ветвей и границ (алгоритма Литтла) предлагается следующая модификация. На каждой промежуточной стадии выполнения алгоритма вычисляется более точная оценка снизу для всех альтернативных маршрутов, которые можно построить на основе текущего частичного решения. Благодаря этому, отсечение бесперспективных вариантов выполняется, как правило, намного эффективнее, особенно для случайной несимметричной матрицы расстояний. Рассмотрены реализации модифицированного алгоритма с поиском вглубь и вширь, а также с поиском вглубь, когда ищется приближенный маршрут с произвольно задаваемой погрешностью. Для функции трудоёмкости U (n) = a · c n, измеряющей количество обрабатываемых матриц расстояний (узлов дерева решений) в графе с n вершинами, с помощью вычислительного эксперимента получены оценки констант a и c для различных реализаций алгоритма. При этом время обработки каждого узла увеличивается в 1,5-2 раза при существенном уменьшении общего времени выполнения алгоритма.
  • Title Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ
  • Headline Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(20)
  • Date:
  • DOI
Ключевые слова
computing experiment, travelling salesman problem, branch-and-bound method, вычислительный эксперимент, метод ветвей и границ, задача коммивояжёра
Авторы
Ссылки
Костюк Ю. Л. Модифицированный алгоритм решения задачи коммивояжёра методом ветвей и границ. Программа и модуль с описанием класса: язык Паскаль в системе Delphi // Электронный ресурс: www.inf.tsu.ru/Decanat/Staff.nsf/people/KostjukJuL, 2013.
Хелд М., Карп Р. М. Применения динамического программирования к задачам упорядочивания // Кибернетический сборник. Вып. 9, старая серия. М.: Мир, 1964. С. 202-218.
Данциг Дж. Линейное программирование, его применения и обобщения: пер. с англ. М.: Прогресс, 1966.
Меламед И.И., Сергеев С. И., Сигал И. Х. Задача коммивояжёра. Точные алгоритмы // Автоматика и телемеханика. 1989. №10. С. 3-29.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. М.: Мир, 1980. 478 с.
Little J. D. C., Murty K. G., Sweeney D. W., and Karel C. An algorithm for the Traveling Salesman Problem // Operations Research. 1963. No. 11. P. 972-989.
 Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ | Прикладная дискретная математика. 2013. № 2(20).
Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ | Прикладная дискретная математика. 2013. № 2(20).