Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью

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