Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера

  • Максим Сергеевич Баркетов Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

Аннотация

Рассматривается асимметричная задача коммивояжера, в которой надо найти гамильтонов цикл с минимальной суммарной стоимостью дуг в полном ориентированном графе. Для решения данной задачи на основе алгоритма, построенного автором в статье «Полиномиальный рандомизированный алгоритм для задачи “Асимметричный коммивояжер”» (Доклады Национальной академии наук Беларуси. 2022. Т. 66, № 5. С. 489 – 494), разработан новый параметризованный полиномиальный рандомизированный алгоритм. Его отличие состоит в другой параметризации. Однако основным результатом является препроцессинговый полиномиальный алгоритм линейного программирования для определения оптимальных параметров.

Биография автора

Максим Сергеевич Баркетов, Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

кандидат физико-математических наук, доцент; старший научный сотрудник лаборатории математической кибернетики

Литература

  1. Barketau MS. Polynomial randomised algorithm for the asymmetric travelling salesman problem. Doklady of the National Academy of Sciences of Belarus. 2022;66(5):489–494. Russian. DOI: 10.29235/1561-8323-2022-66-5-489-494.
  2. Arora S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of 37th Annual symposium on foundations of computer science; 1996 October 14–16; Burlington, USA. Los Alamitos: IEEE Computer Society Press; 1996. p. 2–11. DOI: 10.1109/sfcs.1996.548458.
  3. Svensson O. Approximating ATSP by relaxing connectivity. In: Proceedings of 2015 IEEE 56th Annual symposium on foundations of computer science (FOCS-2015); 2015 October 17–20; Berkeley, USA. Los Alamitos: Conference Publishing Services of the IEEE Computer Society; 2015. p. 1–19. DOI: 10.1109/focs.2015.10.
  4. Burke EK, Cowling PI, Keuthen R. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Boers EJW, Cagnoni S, Gottlieb J, Hart E, Lanzi PL, Raidl GR, et al., editors. Applications of evolutionary computing. EvoWorkshops-2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM; 2001 April 18–20; Como, Italy. Berlin: Springer; 2001. p. 203–212 (Goos G, Hartmanis J, van Leeuwen J, editors. Lecture notes in computer science; volume 2037). DOI: 10.1007/3-540-45365-2_21.
  5. Fischetti M, Lodi A, Toth P. Exact methods for the asymmetric traveling salesman problem. In: Gutin G, Punnen AP, editors. The traveling salesman problem and its variations. New York: Springer; 2007. p. 169–205 (Du D-Z, Pardalos PM, editors. Combinatorial optimization; volume 12). DOI: 10.1007/0-306-48213-4_4.
  6. Grötschel M, Lovász L, Schrijver A. Geometric algorithms and combinatorial optimization. 2nd edition. Berlin: Springer-Verlag; 2012. XII, 362 p. (Graham RL, Korte B, Lovász L, editors. Algorithms and combinatorics; volume 2).
Опубликован
2024-07-23
Ключевые слова: комбинаторная оптимизация, теория вероятностей, рандомизированный алгоритм, приближенный алгоритм, задача коммивояжера
Поддерживающие организации Работа выполнена при частичной финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проекты Ф21-010 и Ф23РНФ-017).
Как цитировать
Баркетов, М. С. (2024). Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера. Журнал Белорусского государственного университета. Математика. Информатика, 2, 113-118. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/6327
Выпуск
№ 2 (2024): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Краткие сообщения

Copyright (c) 2024 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).