Точное и приближенное решения задачи коммивояжера большого размера
DOI:
https://doi.org/10.26089/NumMet.v25r436Ключевые слова:
задача коммивояжера, точный алгоритм, эвристический алгоритм, параллельный алгоритм, метод ветвей и границАннотация
В работе рассматривается быстрый эвристический алгоритм для задачи коммивояжера на основе метода ветвей и границ с оценкой качества получаемого решения, т.е. с параметром k, который гарантирует, что получаемое решение хуже оптимального не более чем в 1/k раз. Алгоритм предназначен для вычислительных систем с общей памятью.
Библиографические ссылки
J. R. Miller, S. Koren, and G. Sutton, “Assembly Algorithms for Next-Generation Sequencing Data,” Genomics 95 (6), 315-327 (2010).
doi 10.1016/j.ygeno.2010.03.001
E. Balas and N. Christofides, “A Restricted Lagrangean Approach to the Traveling Salesman Problem,” Math. Program. 21 (1), 19-46 (1981).
doi 10.1007/BF01584228
Concorde TSP Solver.
http://www.math.uwaterloo.ca/tsp/concorde.html.(Cited November 25, 2024).
V. V. Burkhovetskiy, “Optimization and Parallelization of the Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem,” Program Systems: Theory and Applications 11 (4), 3-16 (2020).
doi 10.25209/2079-3316-2020-11-4-3-16
http://psta.psiras.ru/read/psta2020_4_3-16.pdf. (Cited November 25, 2024).
M. A. Posypkin and I. Kh. Sigal, “A Combined Parallel Algorithm for Solving the Knapsack Problem,” Izv. Akad. Nauk, Teor. Sist. Upravl., No. 4, 50-58 (2008) [J. Comput. Syst. Sci. Int. 47 (4), 543-551 (2008)].
doi 10.1134/S1064230708040072
P. Feautrier, “A Parallelization Framework for Recursive Tree Programs,” in Lecture Notes in Computer Science (Springer, Heidelberg, 1998), Vol. 1470, pp. 470-479.
doi 10.1007/BFb0057890
D. I. Lichmanov, I. V. Afanasyev, and Vad. V. Voevodin, “Performance Study of the Architecture-Independent VGL Framework for Efficient Implementation of Graph Algorithms,” Numerical Methods and Programming 24 (4), 485-499 (2023).
https://doi.org/10.26089/NumMet.v24r433. (Cited November 25, 2024).
N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,” Oper. Res. Forum 3, Article Number 20 (2022).
doi 10.1007/s43069-021-00101-z
K. A. Barkalov, V. V. Ryabov, and S. V. Sidorov, “Some Local and Global Search Balancing Methods in Parallel Global Optimization Algorithms,” Numerical Methods and Programming 11 (4), 382-387 (2010).
http://mi.mathnet.ru/vmp333.(Cited November 25, 2024).
V. Burkhovetskiy and B. Steinberg, “An Exact Parallel Algorithm for Traveling Salesman Problem,”
https://dl.acm.org/doi/10.1145/3166094.3166108.(Cited November 25, 2024).
V. V. Burkhovetskiy, “Implementation of the Exact Algorithm for the Traveling Salesman Problem Based on Modified Balas and Christofides Algorithm,”
https://ops.rsu.ru/download/progs/BalasChristofides_v1_0.zip. (Cited November 29, 2024).
N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, Cambridge, 1975; Mir, Moscow, 1978).
V. V. Burkhovetskiy, Optimization and Parallelization of the Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem (Inst. Matem. Mekh. Komp’yut. Nauk, Rostov-on-Don, 2018).
http://2018.nscf.ru/TesisAll/4Students/237_BurkhovetskiyVV.pdf. (Cited November 25, 2024) [in Russian].
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2024 В. В. Бурховецкий, Б. Я. Штейнберг
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
