Существует ли алгоритм для нахождения оптимального значения k-tsp (коммивояжера) за полиномиальное время?

Question

Я прочитал эту статью, в которой предлагается (последний абзац страницы 1025), что существует алгоритм полиномиального времени для нахождения оптимума задачи k-tsp с использованием бинарного поиска. Использование бинарного поиска предполагает, что существует алгоритм проверки, существует ли решение с cost<X, и этот алгоритм используется для бинарного поиска. Я «гуглил» вокруг этого, и единственный алгоритм, который я смог найти, был недетерминированным (что довольно тривиально), но, очевидно, я ищу детерминированный.

Меня интересует это в учебных целях,

Любая помощь / ссылки будут оценены.

EDIT

Я имею в виду нахождение значения оптимального решения, а не нахождение самого решения.

Answer 1

Поскольку TSP является частным случаем k-TSP, где k = количество узлов в графе.Если бы у вас было решение для «какой самый дешевый маршрут k-TSP» в полиноме относительно размера графа, то у вас было бы полиномиальное решение для версии задачи решения TSP, которая подразумевала бы, что P = NP.

Так что ответ - нет.Детерминированный полиномиальный алгоритм для решения проблемы и версии оптимизации (они по сути одинаковы) k-TSP не существует (пока).

Answer 2

В упомянутой вами статье предлагается алгоритм полиномиального времени приближения для направленной задачи k-TSP.

Алгоритмы аппроксимации - это те алгоритмы, которые гарантированно дают решения с ограниченным отклонением отоптимальное значение решения.Существуют примеры алгоритмов аппроксимации за полиномиальное время для задач NP-Hard: алгоритм Christofides дает за время O (n³) решения метрической задачи TSP, значения которой не более чем на 3/2 от значенияоптимальное решение.