|
Алгоритм соединения циклов для метрической задачи коммивояжера на максимум
А. В. Панюков, Ю. Ф. Леонова Южно-Уральский государственный университет (454080 Челябинск, пр. им. В.И. Ленина, д. 76)
Аннотация:
Задача коммивояжера на максимум имеет ряд практических приложений, например, при сжатии произвольных данных и анализе последовательностей ДНК. При том, что задача коммивояжера на максимум является менее разработанной, чем задача коммивояжера на минимум, для ее решения существуют эффективные приближенные алгоритмы. В статье приведены оценки точности лучших на сегодняшний день алгоритмов для приближенного решения метрической задачи коммивояжера на максимум, и предлагается еще один алгоритм приближенного решения задачи коммивояжера на максимум, состоящий из поиска 2-фактора максимального веса в заданном графе, а затем применения операции оптимального соединения циклов в один гамильтонов цикл. Приведено доказательство, что для метрической задачи коммивояжера на максимум отношение длины найденного алгоритмом гамильтонова цикла к максимально возможной длине гамильтонова цикла не менее 5/6. Вычислительная сложность алгоритма не превышает $O$(|$V$|$^{3}$). Проведено тестирование качества алгоритма на случайно сгенерированных матрицах стоимостей с евклидовой метрикой. Аналитическое и численное исследование алгоритма объединения циклов позволило выдвинуть гипотезу об асимптотической точности алгоритма на классе метрических задач коммивояжера на максимум.
Ключевые слова:
алгоритм, асимптотическая точность, вычислительная сложность, вычислительный эксперимент, задача коммивояжера.
Поступила в редакцию: 22.03.2021
Образец цитирования:
А. В. Панюков, Ю. Ф. Леонова, “Алгоритм соединения циклов для метрической задачи коммивояжера на максимум”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 10:4 (2021), 26–36
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyurv267 https://www.mathnet.ru/rus/vyurv/v10/i4/p26
|
Статистика просмотров: |
Страница аннотации: | 63 | PDF полного текста: | 24 |
|