Предположим, что я программист, и у меня есть NP-полная проблема, которую мне нужно решить. Какие методы доступны для решения проблем с NPC? Есть опрос или что-то похожее на эту тему?

Есть много хорошо изученных стратегий; что лучше в вашем приложении зависит от обстоятельств.

• Улучшение времени выполнения в наихудшем случае
  Используя понимание проблемы, вы часто можете улучшить простой алгоритм. Например, естьалгоритмы для покрытия вершин с[1]; это огромное улучшение по сравнению с наивными может сделать размеры экземпляров подходящими для вас.c < $O(c^n)$$c < 1.3$$\Omega(2^n)$

• Улучшение ожидаемого времени выполнения
  Используя эвристику, вы часто можете разработать быстрые алгоритмы во многих случаях. Если те включают в себя большинство, что вы встречаете на практике, вы золотой. Примерами являются SAT, для которого существуют достаточно сложные решатели, и алгоритм Simplex (который решает полиномиальную проблему, но все же). Одна из основных техник, которая часто полезна, - это ветвление и связывание .

• Ограничьте проблему
  Если вы можете сделать больше предположений относительно своих входных данных, проблема может стать легкой.

  • Структурные свойства.
    Ваши входные данные могут иметь свойства, которые упрощают решение проблемы, например, плоскостность, двухсторонность или отсутствие второстепенных для графов. Смотрите здесь некоторые примеры классов графов, для которых CLIQUE легко.
  • Ограничивающие функции ввода
    Еще одна вещь, на которую стоит обратить внимание, это параметризованная сложность ; некоторые проблемы разрешимы за время для некоторого параметра экземпляра (максимальная степень узла, максимальный вес ребра, ...) и константа . Если вы можете связать полилогарифмической функцией от в ваших настройках, вы получите полиномиальные алгоритмы. Саид Амири приводит подробности в своем ответе .k m k $O(2^kn^m)$$k$$m$$k$$n$
  • Ограничение входных величин
    Кроме того, некоторые проблемы допускают алгоритмы, которые выполняются за псевдополиномиальное время , то есть их время выполнения ограничено полиномиальной функцией от числа, которое является частью ввода; Наивная проверка первичности - пример. Это означает, что, если величины, закодированные в ваших экземплярах, имеют разумный размер, у вас могут быть простые алгоритмы, которые работают хорошо для вас.

• Ослабление результата
  Это означает, что вы допускаете ошибочные или неполные результаты. Есть два основных вкуса:

  • Вероятностные алгоритмы
    Вы получите правильный результат только с некоторой вероятностью. Есть несколько вариантов, наиболее известные алгоритмы Монте-Карло и Лас-Вегас . Известным примером является критерий первичности Миллера-Рабина .
  • Алгоритмы аппроксимации
    Вы больше не ищете оптимальные решения, но почти оптимальные. Некоторые алгоритмы допускают относительные («не хуже, чем двойные оптимальные»), другие абсолютные («не хуже, чем плюс оптимальные») оценки ошибки. Для многих задач открыто, насколько хорошо они могут быть приближены. Некоторые из них могут быть сколь угодно хорошо аппроксимированы за полиномиальное время, в то время как другие, как известно, не позволяют этого; проверить теорию схем аппроксимации полиномиального времени .$5$

Обратитесь к Algorithmics для жестких проблем путем Hromkovič для тщательного лечения.

1. Простота - это красота. Улучшенные верхние границы для покрытия вершин . Авторы: Chen Jianer, Iyad A. Kanj, Ge Xia (2005).

Другие ответы касались этого с более теоретической точки зрения. Вот более практичный подход.

Для «типичных» NP-полных задач решения ( «существует ли вещь, удовлетворяющая всем этим ограничениям?» ), Это то, что я всегда сначала пробую:

1. Напишите простую программу, которая кодирует ваш проблемный экземпляр как экземпляр SAT .

2. Затем возьмите хороший SAT-решатель , запустите его (используя самый быстрый многоядерный компьютер, какой у вас есть) и посмотрите, что произойдет.

Попробуйте сначала с небольшими экземплярами, чтобы понять, сколько времени это может занять.

Удивительно, но этот подход гораздо лучше, чем пытаться реализовать свой собственный решатель специально для вашей текущей проблемы:

• SAT решатели очень умны и хорошо оптимизированы. Они легко превосходят вашу собственную реализацию поиска с возвратом (независимо от того, сколько времени вы тратите на оптимизацию своего кода). Они также легко превосходят многие альтернативы, такие как решатели целочисленного линейного программирования.

• Это требует очень мало программирования. Шаг 1 относительно прост и не критичен к производительности; Вы можете использовать скриптовые языки, такие как Python. Кто-то уже позаботился о реализации всего, что вам нужно для шага 2.

Для типичных NP-сложных задач оптимизации ( «найдите самую маленькую вещь, которая удовлетворяет всем этим ограничениям» ) этот подход может работать или не работать.

Если вы легко можете превратить ее в проблему решения ( «существует ли вещь размером 4, которая удовлетворяет всем этим ограничениям?» , «Как насчет размера 3?» ), Отлично, используйте тот же подход, что и выше, с проблемами решения.

В противном случае вы можете прибегнуть к эвристическому решателю, который пытается найти маленькое решение (не обязательно самое маленькое решение). Например:

1. Кодируйте вашу проблему как (взвешенный) экземпляр MAX-SAT .

2. Используйте эвристические решатели из пакета UBCSAT . Эвристические решатели распараллеливаются тривиально; попытаться найти компьютерный кластер с сотнями компьютеров. Вы можете запускать решатели столько времени, сколько хотите, а затем принять лучшее решение, которое вы нашли на данный момент.

Параметризованная сложность

Один из способов атаковать неразрешимость - думать о проблеме в контексте параметризованной сложности.

$k$$f(k) \cdot p(n)$$k$$f(k)$

$O(n^{f(k)})$$\neq$

Вот некоторые примеры в разных классах иерархии W:

1. Покрытие вершин - это FPT (как и непересекающиеся пути вершин на неориентированных графах)
2. Независимый набор и клика являются W [1] -полными
3. Доминирующим множеством является W [2] -Complete.

Это еще один уровень сложности, позволяющий более точно классифицировать проблемы NP, и, если вы хотите большего, вы можете взглянуть на параметризованную сложность схемы и иерархию W по Downey et al (1998).

А если вы хотите еще больше, хорошо бы прочитать Теорию параметризованной сложности Флума и Гроэ .

И наконец:

Параметризованная сложность в сравнении с алгоритмами аппроксимации:

Известно, что если в задаче есть FPTAS ( схема приближения полностью за полиномиальное время ), то это тоже FPT (что очевидно). Но в обратном направлении ничего не известно, также есть некоторые работы по отношению PTAS и XP, но есть Не очень тесная связь между PTAS и W иерархии (по крайней мере, я не знаю, в данный момент).

Также в некоторых случаях мы можем зафиксировать некоторые другие параметры, например: длина самого длинного пути в графе ограничена, а размер решения ограничен (например, в наборе вершин обратной связи), ...

Пример практического использования:

Может быть, некоторые люди считают, что параметризованная сложность на практике бесполезна. Но это неправильно. Многие из параметризованных алгоритмов обнаруживаются в реальных приложениях, когда вы можете исправить некоторые параметры, вот пример:

1. Одна из основных теорем в параметризованной сложности, это сделать для Courcell, он обеспечивает алгоритм времени выполнения для некоторых классов параметризованных задач. Число башен в равно , что означает, что для невозможно. Но одна группа реализовала его алгоритм с некоторыми модификациями для более особого случая, и они получили чрезвычайно быстрый алгоритм покрытия вершин, который в настоящее время используется на некоторых станциях метро в Германии.2 O ( k ) k = $2^{.^{.^{.^2}}}O(n)$$2$$O(k)$$k=10$

2. Один из самых быстрых и точных эвристических алгоритмов для TSP: Слияние туров и разложение ветвей , в которых используется параметризация задачи (не напрямую, а разложение ветвей и используемый ими метод динамического программирования, основанный на некоторых хороших предположениях).

Полнота NP - это проходимость в худшем случае. В зависимости от того, над какой проблемой вы работаете, многие классы экземпляров могут быть решены за разумное время на практике (хотя вам может потребоваться более специализированный алгоритм, чтобы получить хорошее время выполнения).

Подумайте о том, чтобы увидеть, существует ли эффективное сокращение вашей проблемы до проблемы с хорошими доступными решателями, такими как булево соответствие или целочисленное линейное программирование.

$v_i$$v_j$$v_k$$G$$G$Используйте терпимый алгоритм, чтобы решить вашу проблему в геометрической прогрессии . Среди экспоненциальных алгоритмов время выполнения некоторых из них может быть допустимым, если размер входного файла вашей задачи меньше определенного значения.

Несмотря на то, что мы кратко затронули некоторые ответы, позвольте мне подчеркнуть, что на практике NP-полные проблемы решаются (или приближаются) постоянно. Основная причина, по которой вы можете решить NP-полные задачи на практике:

Случаи, встречающиеся на практике, не являются «наихудшими».

Еще одна причина расхождения:

Трудно формально анализировать эвристические алгоритмы.

На практике вы используете эвристические алгоритмы для решения ваших NP-полных задач и надеетесь на лучшее. Результаты часто потрясающие.

Другая проблема, затронутая в других ответах:

Иногда экспоненциальные алгоритмы достаточно быстры.

Это, конечно, зависит от проблемы. Когда речь идет о больших данных, у нас есть противоположный принцип:

Иногда единственно возможные алгоритмы являются квазилинейными.

Боюсь, что толпа здесь довольно теоретически склонна. Вы можете получить лучшие ответы на главном сайте обмена стека.