Задача коммивояжера с несколькими внутренними точками: различия между версиями

Теорема 1. Специальный случай евклидовой задачи коммивояжера с несколькими внутренними точками может быть решен со следующими затратами времени и памяти. Обозначим за n общее число городов, а за k – число городов во внутренней области выпуклой оболочки. 1. За время O(k!kn) с затратами O(k) памяти. 2. За время O(2kk2n) с затратами O(2kkn) [1] памяти.

Из теоремы 1 следует, что с точки зрения параметризованной сложности [2, 3, 16] эти алгоритмы представляют собой алгоритмы с фиксированными параметрами, принимая за параметр число внутренних точек k – и, следовательно, задача принадлежит к классу разрешимых с фиксированным параметром. (Время выполнения алгоритма с фиксированным параметром составляет O(f(k)poly(n)), где n – размер входных данных, k – параметр, а f: N ! N – произвольная вычислимая функция. Например, алгоритм с временем выполнения O(5kn) является алгоритмом с фиксированным параметром, тогда как алгоритм с временем выполнения O(nk) не является таковым). Заметим, что второй алгоритм дает точное решение с полиномиальным временем выполнения при k = O(log n).

Этот метод может быть расширен на определенные обобщенные версии задачи коммивояжера (TSP). В частности, Дейнеко и др. [ ] заявили, что задача коммивояжера со сбором наград и частичная задача коммивояжера могут быть решены аналогичным образом.