DOI: https://doi.org/10.26089/NumMet.v25r436
Точное и приближенное решения задачи коммивояжера большого размера
Авторы
-
В. В. Бурховецкий
-
Б. Я. Штейнберг
Ключевые слова:
задача коммивояжера
точный алгоритм
эвристический алгоритм
параллельный алгоритм
метод ветвей и границ
Аннотация
В работе рассматривается быстрый эвристический алгоритм для задачи коммивояжера на основе метода ветвей и границ с оценкой качества получаемого решения, т.е. с параметром k, который гарантирует, что получаемое решение хуже оптимального не более чем в 1/k раз. Алгоритм предназначен для вычислительных систем с общей памятью.
Загрузки
Опубликован
2024-12-11
Выпуск
Раздел
Параллельные программные средства и технологии
Библиографические ссылки
- 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 Всемирная.
