danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2022-66-5-489-494dan-1087Research ArticleИНФОРМАТИКАINFORMATICSПолиномиальный рандомизированный алгоритм для задачи «Асимметричный коммивояжер»Polynomial randomized algorithm for the asymmetric travelling salesman problemБаркетовМ. С.BarketauM. S.

Баркетов Максим Сергеевич – канд. физ.-мат. наук,доцент, ст. науч. сотрудник

ул. Сурганова, 6, 220012, Минск  

Barketau Maksim S. – Ph. D. (Physics and Mathematics),Associate Professor, Senior Researcher

6, Surganov Str., 220012, Minsk

barketau@mail.ruОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of the National Academy of Sciences of Belarus202202112022665489494Copyright © Баркетов М.С., 20222022Баркетов М.С.Barketau M.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/1087

Рассматривается задача «Асимметричный коммивояжер», в которой нужно найти обход вершин с минимальной суммарной стоимостью дуг в полном ориентированном графе. На задачу не накладывается неравенство треугольника. Для решения данной задачи построен рандомизированный алгоритм, у которого есть определенная гарантированная степень приближения. Вычислительная сложность алгоритма позволяет использовать данный алгоритм для компьютерных программ.

The asymmetric travelling salesman problem without metric restrictions is considered. The randomized algorithm is proposed. It has a certain approximation guarantee and possesses a certain property regarding the probabilities of the tours built. The computational complexity of the algorithm is polynomial and affordable. 

комбинаторная оптимизациятеория вероятностейрандомизированный алгоритмприближенный алгоритмзадача коммивояжераcombinatorial optimizationprobability theoryrandomized algorithmapproximation algorithmasymmetric travelling salesman problemReferencesArora, 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.548458Arora S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 2–11. https://doi.org/10.1109/sfcs.1996.548458Svensson, 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.10Svensson O. Approximating ATSP by relaxing connectivity. IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 1–19. https://doi.org/10.1109/focs.2015.10Burke, 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_21Burke E., Cowling P., Keuthen R. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. Workshops on Applications of Evolutionary Computation. Berlin, Heidelberg, 2001, pp. 203– 212. https://doi.org/10.1007/3-540-45365-2_21Fischetti, 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_4Fischetti M., Lodi A., Toth P. Exact methods for the asymmetric traveling salesman problem. The traveling salesman problem and its variations. Boston, MA, 2007, pp. 169–205. https://doi.org/10.1007/0-306-48213-4_4

The authors declare that there are no conflicts of interest present.