Полиномиальный рандомизированный алгоритм для задачи «Асимметричный коммивояжер»
https://doi.org/10.29235/1561-8323-2022-66-5-489-494
Анатацыя
Рассматривается задача «Асимметричный коммивояжер», в которой нужно найти обход вершин с минимальной суммарной стоимостью дуг в полном ориентированном графе. На задачу не накладывается неравенство треугольника. Для решения данной задачи построен рандомизированный алгоритм, у которого есть определенная гарантированная степень приближения. Вычислительная сложность алгоритма позволяет использовать данный алгоритм для компьютерных программ.
Аб аўтары
М. Баркетов
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
Беларусь
Спіс літаратуры
1. Arora, S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems / S. Arora // Proceedings of 37th Conference on Foundations of Computer Science. – 1996. – P. 2–11. https://doi.org/10.1109/sfcs.1996.548458
2. Svensson, O. Approximating ATSP by relaxing connectivity / O. Svensson // IEEE 56th Annual Symposium on Foundations of Computer Science. – 2015. – P. 1–19. https://doi.org/10.1109/focs.2015.10
3. Burke, E. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem / E. Burke, P. Cowling, R. Keuthen // Workshops on Applications of Evolutionary Computation. – Berlin, Heidelberg: Springer, 2001. – P. 203–212. https://doi.org/10.1007/3-540-45365-2_21
4. Fischetti, M. Exact methods for the asymmetric traveling salesman problem / M. Fischetti, A. Lodi, P. Toth // The traveling salesman problem and its variations. – Boston, MA: Springer, 2007. – P. 169–205. https://doi.org/10.1007/0-306-48213-4_4
##reviewer.review.form##
Праглядаў: 180
Паслаць артыкул па эл. пошце 