Оптимизация и распараллеливание упрощенного алгоритма Балаша-Кристофидеса для задачи коммивояжера
Автор: Бурховецкий Виктор Витальевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (47) т.11, 2020 года.
Бесплатный доступ
В работе описывается точный параллельный алгоритм для задачи коммивояжера, основанный на упрощенном алгоритме Балаша/Кристофидеса, его оптимизация и увеличение эффективности распараллеливания. За счет нового метода передачи заданий между параллельными потоками алгоритм способен решать задачи с 3000 вершинами (со случайными весами дуг), в среднем, за минуту, а задачи с 10000 вершинами - за 50 минут. Возможность решать задачи с более чем 3000 вершинами появилась благодаря проведенной автором оптимизации расхода памяти.
Метод ветвей и границ, параллельные вычисления, задача коммивояжера, обход дерева, оптимизация расхода памяти
Короткий адрес: https://sciup.org/143175969
IDR: 143175969 | DOI: 10.25209/2079-3316-2020-11-4-3-16
Список литературы Оптимизация и распараллеливание упрощенного алгоритма Балаша-Кристофидеса для задачи коммивояжера
- M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979, ISBN 0716710447. t3
- И. И. Меламед, С. И. Сергеев, И. Х. Сигал. «Задача коммивояжера. Вопросы теории», Автоматика и телемеханика, 1989, №9, с. 3-33.
- И. И. Меламед, С. И. Сергеев, И. Х. Сигал. «Задача коммивояжера. Точные методы», Автоматика и телемеханика, 1989, №10, с. 3-29.
- И. И. Меламед, С. И. Сергеев, И. Х. Сигал. «Задача коммивояжера. Приближенные алгоритмы», Автоматика и телемеханика, 1989, №11, с. 3-26. 0 t3
- E. Balas, N. Christofides. "A restricted Lagrangean approach to the traveling salesman problem", Mathematical Programming, 21:1 (1981), pp. 19-46.
- G. B. Dantzig. "Optimal assignment and other distribution problems", Linear Programming and Extensions, Princeton University Press, Princeton, NJ, USA, 1998, ISBN 0691059136, pp. 316-334. 3 6
- Ю. Л. Костюк. «Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ», Прикладная дискретная математика, 20:2 (2013), с. 78-90. 3
- National Research Council. Getting Up to Speed: The Future of Supercomputing, eds. S. L. Graham, M. Snir, C. A. Patterson, The National Academies Press, Washington, DC, 2005, ISBN 978-0-309-09502-0, 289 pp. 4
- V. Levchenko, A. Perepelkina, A. Zakirov. "DiamondTorre algorithm for high-performance wave modeling", Computation, 4:3 (2016), pp. 29. I ' 4
- S. G. Ammaev, L. R. Gervich, B. Y. Steinberg. "Combining parallelization with overlaps and optimization of cache memory usage", Parallel Computing Technologies, PaCT 2017, Lecture Notes in Computer Science, vol. 10421, ed. V. Malyshkin, Springer International Publishing, 2017, pp. 257-264.
- S. El-Metwally, O. M. Ouda, M. Helmy, Next Generation Sequencing Technologies and Challenges in Sequence Assembly, SpringerBriefs in Systems Biology, vol. 7, Springer, 2014, ISBN 978-1-4939-0715-1, pp. 17-19, 84-85.
- R. Jonker, T. Volgenant. "Transforming asymmetric into symmetric traveling salesman problems", Operations Research Letters, 2:4 (1983), pp. 161-163.
- V. Burkhovetskiy, B. Steinberg. "An exact parallel algorithm for traveling salesman problem", Proceedings of the 13th Central & Eastern European Software Engineering Conference in Russia, CEE-SECR'17, ACM, New York, NY, USA, 2017 (in Russian), 5 pp. t4 r 8 9
- M. Bellmore, G. L. Nemhauser. "The traveling salesman problem: a survey", Operations Research, 16:3 (1968), pp. 538-558. t5
- Y. Kaempfer, L. Wolf. Learning the multiple Traveling Salesmen Problem with permutation invariant pooling networks, 2018. arXivjQj 1803.09621 12
- A. Fischer, F. Fischer, G. Jäger, J. Keilwagen, P. Molitor, I. Grosse. "Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics", Discrete Applied Mathematics, 166 (2014), pp. 97-114. d ti2
- T. Fischer, T. Stätzle, H. Hoos, P. Merz. "An analysis of the hardness of TSP instances for two high performance algorithms", MIC2005: The Sixth Metaheuristics International Conference (Vienna, Austria, August 22-26, 2005), 2005, pp. 361-367. ® ti2
