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

Из теоремы 1 следует, что с точки зрения параметризованной сложности [2, 3, 16] эти алгоритмы представляют собой ''алгоритмы с фиксированными параметрами'', принимая за параметр число внутренних точек k – и, следовательно, задача принадлежит к классу разрешимых с фиксированным параметром. (Время выполнения алгоритма с фиксированным параметром составляет <math>O(f(k) poly(n)) \;</math>, где n – размер входных данных, k – параметр, а <math>f: \mathbb{N} \to \mathbb{N}</math> – произвольная вычислимая функция. Например, алгоритм с временем выполнения <math>O(5^k n) \;</math> является алгоритмом с фиксированным параметром, тогда как алгоритм с временем выполнения <math>O(n^k) \;</math> не является таковым). Заметим, что второй алгоритм дает точное решение с полиномиальным временем выполнения при k = O(log n).

Грантсон и Левкопулос [9] предложили алгоритм с временем выполнения <math>O(k^{6k - 5} 2^{16k} n) \;</math>. Позднее Спиллнер [19] улучшил эту временную сложность до <math>O(2^k k^3 n^3) \;</math>.

Грантсон [5] предложил алгоритм с временем выполнения <math>O(k^{6k - 5} 2^{16k} n) \;</math>. Позднее Спиллнер [19] улучшил эту временную сложность до <math>O(2^k k^3 n^3) \;</math>. ()

Пусть дан геометрический граф с n вершинами (т. е. граф на евклидовой плоскости, каждое ребро которого является отрезком прямой, соединяющим две точки). Необходимо определить, имеется ли у него [[остовное дерево]], ребра которого не пересекаются. Дженсен и Вегингер [11] доказали, что эта задача является NP-полной.

 

Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет <math>2^{O(\sqrt{k} \; log \; k)} poly(n).</math>

На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения <math>2^{O(\sqrt{k})} poly(n)</math>?

* [[Евклидова задача коммивояжера]]

* [[Гамильтоновы циклы в случайных графах пересечений]]

* [[Конкурс по реализации эвристик для задачи коммивояжера]]

* [[Метрическая задача коммивояжера]]

 

* [[Нахождение ближайшей подстроки]]

* [[Параметризованная задача выполнимости КНФ]]

* [[Кернелизация вершинного покрытия]]

* [[Вершинное покрытие и деревья поиска]]

 

* [[Триангуляция с минимальным весом]]