Есть много реальных проблем, которые оказываются NP -hard. Если предположить, что P & ne; NP, для этих задач не существует алгоритмов с полиномиальным временем.
Если вам нужно решить одну из этих проблем, есть ли надежда, что вы сможете сделать это эффективно? Или вам просто не повезло?
Если проблема NP -харда, в предположении, что P & ne; NP нет алгоритма
Если вам абсолютно нужны все перечисленные гарантии, тогда вам не повезло. Однако, если вы согласитесь решить проблему, которая смягчает некоторые из этих ограничений, тогда еще очень может быть надежда! Вот несколько вариантов для рассмотрения.
Если проблема NP -хард и P & ne; NP, это означает, что нет алгоритма, который всегда будет эффективно воспроизводить точно правильный ответ на всех входах. Но что, если вам не нужен точный ответ? Что делать, если вам просто нужны ответы, близкие к правилу? В некоторых случаях вы можете бороться с NP -жесткой, используя алгоритм аппроксимации.
Например, канонический пример проблемы NP - проблема коммивояжера. В этой задаче вам предоставляется как ввод полного графика, представляющего транспортную сеть. Каждое ребро в графе имеет связанный вес. Цель состоит в том, чтобы найти цикл, который проходит через каждый node в графе ровно один раз и который имеет минимальный общий вес. В случае, когда веса ребер удовлетворяют неравенству треугольника (то есть лучший маршрут от точки A до точки B всегда должен следовать прямым ссылку от A до B), то вы можете вернуть цикл, стоимость которого не превышает оптимального 3/2, используя алгоритм Christofides.
В качестве другого примера проблема 0/1 рюкзака известна как NP -hard. В этой задаче вам дается сумка и коллекция объектов с различными весами и значениями. Цель состоит в том, чтобы упаковать максимальное количество предметов в сумку, не превышая лимит веса мешка. Даже если вычисление точного ответа требует экспоненциального времени в худшем случае, можно аппроксимировать правильный ответ на произвольную степень точности в полиномиальное время. (Алгоритм, который делает это, называется полностью полиномиально-временной схемой приближения или FPTAS).
К сожалению, у нас есть некоторые теоретические ограничения на аппроксимируемость некоторых NP -арда. Алгоритм Кристофида, упомянутый ранее, дает приближение 3/2 к TSP, где ребра подчиняются неравенству треугольника, но достаточно интересно показать, что если P & ne; NP, не существует алгоритма аппроксимации полиномиального времени для TSP, который может попасть в любой постоянный коэффициент оптимальности. Обычно вам нужно провести некоторое исследование, чтобы узнать больше о том, какие проблемы могут быть хорошо аппроксимированы, а какие не могут, поскольку многие проблемы NP могут быть хорошо аппроксимированы, а многие не могут. Кажется, что нет единой темы.
Во многих проблемах с NP стандартные подходы, такие как жадные алгоритмы, не всегда дают правильный ответ, но часто достаточно хорошо подходят для "разумных" входов. Во многих случаях разумно атаковать NP - тяжелые проблемы с эвристикой. Точное определение эвристики варьируется от контекста к контексту, но, как правило, эвристика - это либо подход к проблеме, которая "часто" дает хорошие ответы за счет того, что иногда дает неверные ответы, или это полезное эмпирическое правило, которое помогает ускорить поиск, даже если это может не всегда правильно вести поиск.
В качестве примера первого типа эвристики рассмотрим проблему раскраски графа. Этот NP-hard проблема, заданная графиком, найти минимальное количество цветов, необходимых для рисования узлов в графе, так что конечные точки края не будут одного цвета. Это оказывается особенно сложной задачей для решения многих других подходов (наиболее известные алгоритмы аппроксимации имеют ужасные оценки и не предполагают, что они имеют параметризованный эффективный алгоритм). Тем не менее, существует много эвристик для графовой раскраски, которые довольно хорошо на практике. Существует много жадных раскрасок эвристики для назначения цветов узлам в разумном порядке, и эти эвристики часто на практике довольно хороши. К сожалению, иногда эти эвристики дают ужасные ответы, но при условии, что график не является патологически сконструированным, эвристика часто работает очень хорошо.
В качестве примера второго типа эвристики полезно посмотреть на решатели SAT. SAT, проблема булевской выполнимости, была первой проблемой, которая оказалась NP -hard. Задача задается с учетом пропозициональной формулы (часто написанной в конъюнктивной нормальной форме), чтобы определить, есть ли способ присвоить значения переменным так что общая формула имеет значение true. Современные SAT-решатели во многих случаях хорошо справляются с решением SAT, используя эвристику, чтобы вести поиск по возможным назначениям переменных. Один известный алгоритм SAT-решения, DPLL, по существу пытается выполнить все возможные назначения, чтобы убедиться, что эта формула выполнима, используя эвристику для ускорения поиск. Например, если он обнаруживает, что переменная всегда или всегда неверна, DPLL попытается присвоить этой переменной ее принудительное значение перед тем, как попробовать другие переменные. DPLL также находит единицы предложения (предложения только с одним литералом) и устанавливает значения этих переменных перед тем, как попробовать другие переменные. Чистый эффект этих эвристик заключается в том, что DPLL на практике становится очень быстрым, хотя известно, что он имеет экспоненциальное худшее поведение.
Если P & ne; NP, тогда проблема NP не может быть решена в полиномиальное время. Однако в некоторых случаях определение "полиномиального времени" не обязательно соответствует стандартной интуиции полиномиального времени. Формально говоря, полиномиальное время означает многочлен от числа бит, необходимых для указания входа, который не всегда синхронизируется с тем, что мы считаем входным.
В качестве примера рассмотрим задание проблемы раздела. В этой задаче вам задан набор чисел и нужно определить, есть ли способ разбить набор на два меньших набора, каждый из которых имеет одинаковую сумму. Наивное решение этой проблемы выполняется во времени O (2 n) и работает только с грубой силой, проверяя все подмножества. Тем не менее, при динамическом программировании можно решить эту проблему во времени O (nN), где n - количество элементов в наборе, а N - максимальное значение в наборе. Технически говоря, время выполнения O (nN) не является полиномиальным, поскольку числовое значение N записывается только в битах log 2 n, но при условии, что числовое значение N не слишком велико, это является вполне разумным временем выполнения.
Этот алгоритм называется псевдополиномиально-временным алгоритмом, поскольку время выполнения O (nN) "выглядит" как многочлен, но технически говоря экспоненциальный по размеру ввода. Многие проблемы NP, особенно связанные с числовыми значениями, допускают алгоритмы псевдополиномиального времени и поэтому легко разрешаются, предполагая, что числовые значения не слишком велики.
Для получения дополнительной информации о псевдополиномиальном времени просмотрите этот ранее вопрос о переполнении стека о псевдополиномиальном времени.
Если проблема NP -хард и P & ne; NP, тогда нет детерминированного алгоритма, который мог бы решить эту проблему в худшем случае полиномиального времени. Но что произойдет, если мы допустим алгоритмы, которые вводят случайность? Если мы готовы согласиться на алгоритм, который дает хороший ответ на ожидание, то мы часто можем получить относительно хорошие ответы на NP- тяжелые проблемы в недолгое время.
В качестве примера рассмотрим проблему максимального разрешения. В этой задаче вам предоставляется неориентированный граф и вы хотите найти способ разбить узлы в графе на две непустые группы A и B с максимальным количеством ребер, проходящих между группами. У этого есть некоторые интересные приложения в вычислительной физике (к сожалению, я их вообще не понимаю, но вы можете просмотреть эту статью для получения некоторых подробностей о это). Известно, что эта проблема является NP -hard, но для нее существует простой алгоритм рандомизированного аппроксимации. Если вы просто бросаете каждую из node в одну из двух групп полностью наугад, вы получаете разрез, который в ожидании находится в пределах 50% от оптимального решения.
Возвращаясь к SAT, многие современные SAT-решатели используют некоторую степень случайности, чтобы вести поиск удовлетворительного задания. алгоритмы WalkSAT и GSAT, например, работают, выбирая случайное предложение, которое в настоящее время не выполняется и пытается удовлетворить его, перевернув некоторую переменную значение истинности. Это часто направляет поиск к удовлетворительному назначению, заставляя эти алгоритмы работать на практике.
Получается много открытых теоретических проблем о способности решать проблемы NP с использованием рандомизированных алгоритмов. Если вам интересно, посмотрите класс сложности BPP и открытая проблема его отношения к NP.
Некоторые NP - жесткие проблемы принимают несколько разных входов. Например, проблема длинного пути проблема суммирования подмножества принимает в качестве входного набора чисел и целевого номера k, а затем спрашивает, есть ли подмножество чисел, точно к.
Интересно, что в случае проблемы с длинным путем существует алгоритм (алгоритм цветового кодирования), время выполнения которого равно O (( n 3 log n) & middot; b k), где n - количество узлов, k - длина запрошенного пути, b - некоторая константа. Эта среда выполнения является экспоненциальной по k, но является только полиномом по n, числу узлов. Это означает, что если k фиксировано и известно заранее, время выполнения алгоритма в зависимости от количества узлов является только O (n 3 log n), что является довольно хорошим полиномом. Аналогично, в случае проблемы суммы подмножества существует алгоритм динамического программирования, время выполнения которого равно O (nW), где n - количество элементов набора, а W - максимальный вес этих элементов. Если W фиксируется заранее как некоторая константа, то этот алгоритм будет выполняться во времени O (n), что означает, что можно будет точно решить сумму подмножества в линейном времени.
Оба этих алгоритма являются примерами параметризованных алгоритмов, алгоритмов решения NP - сложных проблем, которые разделяют твердость проблемы на две части - "жесткий" кусок, который зависит от некоторого входного параметра к проблеме, и "легкая" штука, которая грациозно масштабируется с размером ввода. Эти алгоритмы могут быть полезны для нахождения точных решений проблем NP, когда этот параметр мал. Например, упомянутый выше алгоритм цветового кодирования оказался весьма полезным на практике в вычислительной биологии.
Однако некоторые проблемы предполагают, что у них нет хороших параметризованных алгоритмов. Например, при раскраске графа не существует эффективных алгоритмов с параметрами. В тех случаях, когда существуют параметризованные алгоритмы, они часто довольно эффективны, но вы не можете полагаться на них для всех проблем.
Для получения дополнительной информации о параметризованных алгоритмах, проверьте этот ранее вопрос о переполнении стека.
Алгоритмы экспоненциального времени не очень хорошо масштабируются - их время работы приближается к времени жизни юниверса для входов размером не более 100 или 200 элементов.
Что делать, если вам нужно решить NPно вы знаете, что вход достаточно мал - скажем, возможно, его размер составляет от 50 до 70. Стандартные алгоритмы экспоненциального времени, вероятно, не будут достаточно быстрыми, чтобы решить эти проблемы. Что делать, если вам действительно нужно точное решение проблемы, а другие подходы здесь не сократят?
В некоторых случаях существуют "оптимизированные" алгоритмы экспоненциального времени для проблем с NP. Это алгоритмы, время выполнения которых экспоненциально, но не так плохо экспоненциальное, как наивное решение. Например, простой алгоритм экспоненциального времени для 3-цветной задачи (учитывая график, определите, можете ли вы покрасить узлы по одному из трех цветов для каждого из них, чтобы конечные точки конца не были одинакового цвета) могли бы работать, проверяя каждый возможный способ раскраски узлы в графе, проверяя, есть ли какая-либо из них 3-окраска. Существует 3 способа n поэтому в худшем случае время выполнения этого алгоритма будет O (3 n & middot; poly (n)) для некоторого небольшого полином poly (n). Однако, используя более умные трюки и методы, можно разработать алгоритм 3-красочности, который выполняется во времени O (1.3289 n). Это все еще алгоритм экспоненциального времени, но это гораздо более быстрый алгоритм экспоненциального времени. Например, 3 19 составляет около 10 12 поэтому, если компьютер может выполнять один миллиард операций в секунду, он может использовать наш первоначальный алгоритм грубой силы (грубо говоря) разрешить 3-красочность графиков с точностью до 19 узлов за одну секунду. Используя алгоритм экспоненциального времени O ((1.3289 n)), мы могли бы решить примерно до 73 узлов примерно за секунду. Это огромное улучшение - мы увеличили размер, который мы можем обрабатывать в одну секунду более чем в три раза!
В качестве еще одного известного примера рассмотрим проблему коммивояжера. Существует очевидное решение O (n! & Middot; poly (n)) для TSP, которое работает, перечисляя все перестановки узлов и проверяя пути, возникающие в результате этих перестановок. Однако, используя алгоритм динамического программирования, аналогичный алгоритму кодирования цвета, можно улучшить время выполнения до "только" O (n 2 2 n), Учитывая, что 13! составляет около одного миллиарда, наивное решение позволило бы вам разрешить TSP для 13- node графиков примерно через секунду. Для сравнения, решение DP позволяет вам разрешать TSP на 28- node графиках примерно за одну секунду.
Эти быстрые алгоритмы экспоненциального времени часто полезны для увеличения размера входов, которые можно точно решить на практике. Конечно, они все еще работают в экспоненциальном времени, поэтому эти подходы обычно не пригоден для решения очень больших проблемных экземпляров.
Если вам нужно решить проблему NP -hard, не отчаивайтесь! Есть много отличных вариантов, которые могут сделать вашу трудноизвлекаемую проблему намного более доступной. Ни один из вышеперечисленных методов не работает во всех случаях, но, используя некоторую комбинацию этих подходов, обычно можно добиться прогресса даже при столкновении с NP -hardness.
Надеюсь, это поможет!