Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/12

Для решения задачи коммивояжёра с матрицей расстояний порядка n предлагается приближённый алгоритм на основе метода ветвей и границ. Для отсечения используется увеличенная оценка снизу текущего частичного решения, гарантирующая заранее заданную величину ε погрешности всего решения. Проведён вычислительный эксперимент для матриц расстояний четырёх видов распределений, среди них для равномерного случайного (несимметричного) распределения, а также для матриц евклидовых расстояний между случайными точками (симметричного распределения). В последнем случае дополнительно применён локальный поиск. Получены оценки степени p для функции полиномиальной трудоёмкости O(n^p ) для разных видов распределений и различных величин погрешности ε. Для равномерного случайного распределения полученная оценка степени p оказалась близка к 2,8 в диапазоне n до 1000 и средней погрешности около 1 %.