?
Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма
Предложен новый «антижадный» алгоритм для решения задачи коммивояжера, имеющий меньшую погрешность, чем известные приближенные полиномиальные алгоритмы. Идея «антижадного» алгоритма заключается в том, что из графа последовательно удаляются ребра наибольшей длины при одновременном соблюдении для оставшегося графа двух правил. Во-первых, из каждой его вершины должно выходить, как минимум, два ребра. Во-вторых, в нем не должно возникать циклов, состоящих менее, чем из n ребер, где n – количество вершин в исходном графе. Проведено исследование работы трех алгоритмов: «антижадный», «жадный» и алгоритм Кристофидеса, – для евклидовых и неевклидовых графов. Получены статистические данные о погрешности и времени работы алгоритмов, которые демонстрируют значительное превосходство «антижадного» алгоритма в точности, в особенности для неевклидовых графов.