Поиск наиболее эффективной верхней границы для TSP с использованием MST

Question

Мне любопытно, какие наиболее эффективные методы - найти оптимальную (или близкую к оптимальной) верхнюю границу для TSP с использованием MST. Я пытаюсь оптимизировать свои алгоритмы для скорости, но у меня возникают проблемы с алгоритмическим вычислением «хороших» границ после того, как я нахожу MST. Я знаю, что базовая граница будет 2 x MST length, но это, похоже, не лучшее, что мы можем сделать. Любые ссылки или понимание будут оценены.

Answer 1

Вероятно, вы должны преобразовать MST в турне, и это даст вам длину менее 2 * MST в линейном времени. Существует также расширение для MST, называемое алгоритмом Кристофида, которое, возможно, стоит изучить.

Рекомендовать ознакомиться с Википедии на странице TSP heuristics.