Некоторые проблемы, которые являются NP-hard, также fixed-parameterableable или FPT. Википедия описывает проблему с фиксированным параметром, если есть алгоритм, который решает его во времени f (k) и middot; | Х |. О (1)
Что это значит? Почему эта концепция полезна?
Начнем с того, что P & ne; NP, для любой NP-жесткой задачи нет полиномиально-временных точных алгоритмов. Хотя мы не знаем, P = NP или P & ne; NP, у нас нет алгоритмов с полиномиальным временем для любых NP-трудных задач.
Идея уступчивости с фиксированными параметрами состоит в том, чтобы взять NP-трудную задачу, которую мы не знаем ни одного алгоритма полиномиального времени для, и попытаться выделить сложность на две части - часть, которая зависит исключительно от размер ввода и часть, которая зависит от некоторого "параметра" к проблеме.
В качестве примера рассмотрим проблему 0/1 рюкзак. В этой задаче вам предоставляется список из n объектов, у которых есть связанные веса и значения, а также некоторый максимальный вес W, который вам разрешено переносить. Вопрос заключается в определении максимальной стоимости, которую вы можете носить. Эта проблема NP-hard, что означает, что нет алгоритма полиномиального времени, который ее решает. Метод грубой силы займет время вокруг O (2 n), рассмотрев все возможные подмножества элементов, что чрезвычайно велико для больших n. Однако эту задачу можно решить во времени O (nW), где n - количество элементов, а W - количество веса, которое вы можете переносить. Если вы посмотрите на рабочую среду O (nW), вы заметите, что она разбита на две части: компонент, линейный по количеству элементов (n-часть) и компонент, линейный по весу (часть W). Если W - любая фиксированная константа, то время выполнения этого алгоритма будет O (n), которое является линейным временем, хотя проблема вообще NP-жесткая. Это означает, что если рассматривать W как какой-то настраиваемый "параметр" задачи, то для любого фиксированного значения этого параметра проблема заканчивается в полиномиальное время (которое является "приемлемым" в смысле теории сложности).
В качестве другого примера рассмотрим проблему поиска длинных простых путей в графе. Эта проблема также NP-жесткая, а наивный алгоритм нахождения простых путей длины k в графе занимает время O (n!/(N - k)!), Которое при больших k оказывается суперэкспоненциальным. Однако, используя технику color-coding, можно решить эту проблему за время O ((2e) k n 3 log n), где k - длина пути для поиска, а n - количество узлов в входном графе. Обратите внимание, что эта среда выполнения также имеет два компонента: один компонент, который является полиномом числа узлов входного графика (n 3 log n part) и одной компоненты, экспоненциальной по k (( 2e) k). Это означает, что при любом фиксированном значении k существует алгоритм полиномиального времени для нахождения путей длины-k в графе; время выполнения будет O (n 3 log n).
В обоих случаях мы можем взять проблему, для которой у нас есть экспоненциально-временное решение (или, что еще хуже), и найти новое решение, время выполнения которого является некоторым полиномом в n раз некоторой безумной функцией некоторого дополнительного параметра ". В случае проблемы с рюкзаком этот параметр является максимальным весом, который мы можем переносить; в случае нахождения длинных путей параметр - это длина пути для поиска. Вообще говоря, проблема называется фиксированным параметром трактуемой, если существует некоторый алгоритм решения задачи, заданный в терминах двух величин: n, размер ввода и k, некоторый "параметр", где время выполнения
O (p (n) & middot; f (k))
Где p (n) - некоторая полиномиальная функция, а f (k) - произвольная функция из k. Интуитивно это означает, что сложность задачи масштабируется полиномиально с n (что означает, что по мере увеличения только размера проблемы время выполнения будет хорошо масштабироваться), но может масштабироваться произвольно плохо с параметром k. Это отделяет "присущую жесткость" проблемы, так что "жесткая часть" проблемы обвиняется в параметре k, а "легкая часть" проблемы заряжается до размера ввода.
Когда у вас есть среда выполнения, которая выглядит как O (p (n) и middot; f (k)), мы сразу получаем алгоритмы полиномиального времени для решения задачи для любого фиксированного k. В частности, если k фиксировано, то f (k) является некоторой константой, поэтому O (p (n) & middot; f (k)) является просто O (p (n)). Это алгоритм полиномиального времени. Поэтому, если мы "фиксируем" параметр, мы возвращаем некоторый "сговорный" алгоритм для решения проблемы. Это источник термина фиксированного параметра.
(Примечание: определение пригодности фиксированных параметров в Википедии говорит о том, что алгоритм должен иметь время выполнения f (k) и middot; | x | O (1). Здесь | x | относится к размер ввода, который я назвал n здесь. Это означает, что определение Википедии совпадает с тем, что время выполнения: f (k) и middot; n O (1). href= "/info/293887/why-does-no1-mean-polynomial-time" > в этом более раннем ответе, n O (1) означает "некоторый многочлен от n", и поэтому это определение оказывается эквивалентным тому, здесь).
Уступчивость с фиксированными параметрами имеет огромное практическое значение для проблемы. Это часто встречается с проблемами NP-hard. Если вы обнаружите проблему с фиксированным параметром, и параметр низкий, может быть значительно эффективнее использовать алгоритм с фиксированным параметром, чем использовать обычный алгоритм грубой силы. Например, пример цветового кодирования для поиска длинных путей на графике был использован для большого успеха в вычислительной биологии, чтобы найти пути последовательности в дрожжевых клетках, а рюкзак 0/1 используется часто, потому что общие значения W являются достаточно низкими для практического применения.
Надеюсь, это поможет!