Асимптотически точный алгоритм для задачи MAX m-Cycles Cover на максимум

Аннотация

В данной работе рассмотрена постановка задачи коммивояжера на максимум (MAX TSP), приведены известные результаты прошлых лет, а также рассмотрена симптотически точный алгоритм Гимади-Сердюкова с временной сложностью O(n3)для решения задачи MAX TSP в евклидовой постановке. Пошагово приведено переработанное доказательство асимптотической точности алгоритма.Проведен эксперимент, целью которого было проверить свойства асимптотически точного алгоритма. Для задачи коммивояжера на максимум существует множество обобщений, одним из которых является задача о цикловом покрытии графана максимум (MAX m-Cycles Cover). Продемонстрирован TSP-подход к её решению, а также рассмотрен соответствующий асимптотически точный алгоритмобладающий аналогичной трудоемкостью - O(n3). Приведено переработанное доказательство асимптотической точности данного алгоритма, проведено его тестирование