Применение дополнений паросочетаниями для решения задачи MAX TSP

Бесплатный доступ

Изложен подход к приближенному решению задачи коммивояжера на максимум (MAX TSP), основанный на дополнении частичного тура просочетаниями подграфа открытых вершин. Проведено аналитическое исследование, показавшее, что алгоритм, основанный на непосредственном применении данного подхода, во-первых, имеет вычислительную сложность не более O(n3), n - число городов, во-вторых, не улучшает гарантированные оценки точности известных алгоритмов. Предложена модификация алгоритма Сердюкова, имеющая оценку вычислительной сложности O(n3) и наилучшую гарантированную оценку точности. Представлены результаты вычислительного эксперимента, позволяющие выдвинуть гипотезу об асимптотической точности алгоритма для достаточно широкого класса задач.

Еще

Гамильтонов цикл, задача коммивояжера, приближенный алгоритм, паросочетание, оценки точности, вычислительная сложность, вычислительный эксперимент

Короткий адрес: https://sciup.org/147159039

IDR: 147159039

Список литературы Применение дополнений паросочетаниями для решения задачи MAX TSP

  • Гимади Э.Х. О некоторых результатах для задачи коммивояжера на максимум/Э.Х. Гимади, А.И. Сердюков//Дискретный анализ и исследование операций. 2001. № 1. С. 22-39.
  • Панюков А.В. Исследование реализаций алгоритма Сердюкова для задачи MAX TSP/А.В. Панюков, С.А. Тычинин//Российская конференция «Дискретная оптимизация и исследование операций»: материалы конф. (Владивосток, 7-14 сентября 2007). Новосибирск, 2007. С. 132.
  • Тычинин С.А. Алгоритм дополнения подграфами для решения задачи MAX TSP/С.А. Тычинин//Информационный бюллетень ассоциации математического программирования № 11: Конференция «Математическое программирование и приложения (тезисы докладов)». Екатеринбург, 2007. С. 217-218.
  • The maximum traveling salesman problem under polyhedral norms/А.I. Barvinok, D.S. Johnson, G. Woeginger, R. Woodroofe//Integer Programming and Combinatorial Optimization. Berlin, 1999. P. 195-201.
  • Chen Zh. Improved Deterministic Approximation Algorithms for Max TSP/Zh. Chen, Y. Okamoto, L. Wang//Inform. Process. Lett. 2005. N 95. P. 333-342.
  • Gabow H. An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs/H. Gabow//J. of the ACM. 1976. N 4. P. 221-234.
  • Hartvigsen D. Extensions of matching theory: PhD Thesis/D. Hartvigsen -Pittsburg, PA: Carnegie Mellon Univ, 1984. 148 p.
  • Hassin R.A 7/8 -approximation algorithm for metric Max TSP/R. Hassin, S. Rubinstein//Inform. Process. Lett. 2002. N 81. P. 247-251.
  • Hassin R. Better approximations for Max TSP/R. Hassin, S. Rubinstein//Inform. Process. Lett. 2000. N 75. P. 181-186.
Еще
Статья научная