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

Abstract

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

Keywords

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