• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма

Чусовлянкин А. А., Морозенко В. В.

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