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

Question

Я прочитал статью this, она предлагает (стр. 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 Algorithm дает во времени O (n³) решения проблемы метрического TSP, значения которых не превосходят 3/2 значение оптимального решения.