Анализ точности и времени решения задачи коммивояжера с помощью "антижадного" алгоритма
Автор: Чусовлянкин А.А., Морозенко В.В.
Журнал: Вестник Пермского университета. Серия: Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Информатика. Информационные системы
Статья в выпуске: 4 (35), 2016 года.
Бесплатный доступ
Предложен новый "антижадный" алгоритм для решения задачи коммивояжера, имеющий меньшую погрешность, чем известные приближенные полиномиальные алгоритмы. Идея "антижадного" алгоритма заключается в том, что из графа последовательно удаляются ребра наибольшей длины при одновременном соблюдении для оставшегося графа двух правил. Во-первых, из каждой его вершины должно выходить, как минимум, два ребра. Во-вторых, в нем не должно возникать циклов, состоящих менее чем из n ребер, где n -количество вершин в исходном графе. Проведено исследование работы трех алгоритмов: "антижадный", "жадный" и алгоритм Кристофидеса, - для евклидовых и неевклидовых графов. Получены статистические данные о погрешности и времени работы алгоритмов, которые демонстрируют значительное превосходство "антижадного" алгоритма в точности, в особенности для неевклидовых графов.
Задача коммивояжера, "антижадный " алгоритм, "жадный " алгоритм, алгоритм кристофидеса, евклидовы графы, неевклидовы графы, погрешность
Короткий адрес: https://sciup.org/14730084
IDR: 14730084 | DOI: 10.17072/1993-0550-2016-4-68-75
Список литературы Анализ точности и времени решения задачи коммивояжера с помощью "антижадного" алгоритма
- Дулькейт В.И., Файзуллин Р.Т. Приближенное решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой//Вычислительные методы в дискретной математике./Омск: Изд-во Омского гос. тех. ун-та, 2009. № 1 (3). С.72-78.
- Задача коммивояжера//Институт математики им. С.Л. Соболева СО РАН. URL: http://math.nsc.ru/LBRT/k5/ORMMF/TSPr.pf свободный (дата обращения: 19.10.2016).
- Оре О. Графы и их применение/пер. с англ., под ред. И.М. Яглома. М.: Мир, 1965.174 с.
- Кузюрин Н.Н. Фомин С.А. Сложность вычислений и анализ алгоритмов//DISCO-PAL. М.: МФТИ, 2007. 312 с. URL: http://discopal. ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf, свободный. (дата обращения: 19.10.2016).
- Чусовлянкин А.А. "Антижадный" алгоритм для решения задачи коммивояжера М.: МИЭМ НИУ ВШЭ, 2016. С. 10-11.
- Gutin G., Punnen A. P. The Traveling Salesman Problem and Its Variations Springer//Combinatorial Optimization. Vol. 12. Boston: Kluwer Academic Publishers, 2002. P. 84-85.
- Stencek J. Traveling salesman problem. JAMK University of Applied sciences: Bachelor's Thesis, 2013. P. 25, 31.
- Чусовлянкин А.А., Морозенко В.В. О погрешности алгоритма Кристофидеса для случайных неевклидовых графов//Пермь: ПГНИУ, 2015. С. 338-342.
