Полиномиальный рандомизированный алгоритм для задачи «Асимметричный коммивояжер»
https://doi.org/10.29235/1561-8323-2022-66-5-489-494
Аннотация
Рассматривается задача «Асимметричный коммивояжер», в которой нужно найти обход вершин с минимальной суммарной стоимостью дуг в полном ориентированном графе. На задачу не накладывается неравенство треугольника. Для решения данной задачи построен рандомизированный алгоритм, у которого есть определенная гарантированная степень приближения. Вычислительная сложность алгоритма позволяет использовать данный алгоритм для компьютерных программ.
Об авторе
М. С. Баркетов
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
Беларусь
Баркетов Максим Сергеевич – канд. физ.-мат. наук,
доцент, ст. науч. сотрудник
ул. Сурганова, 6, 220012, Минск
Список литературы
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
Рецензия
Просмотров: 230
Послать статью по эл. почте 