4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 10:53, 25 мая 2018
, 25 мая 2018→Основные результаты
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Из теоремы 1 следует, что с точки зрения параметризованной сложности [2, 3, 16] эти алгоритмы представляют собой ''алгоритмы с фиксированными параметрами'', принимая за параметр число внутренних точек k – и, следовательно, задача принадлежит к классу разрешимых с фиксированным параметром. (Время выполнения алгоритма с фиксированным параметром составляет O(f(k)poly(n)), где 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). | Из теоремы 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). | ||