Заметки Датасатаниста: что делать, если перед вами оказалась NP-полная задача

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

А вообще реально ли встретить такие задачи в обычной жизни? На самом деле, они возникают в огромном ряде случаев: комбинаторика, графы и сети, выполнение логических формул, работа с картами, оптимальные загрузки, отображения, задачи дискретной оптимизации, нахождение самых длинных последовательностей, поиск равных сумм и многие задачи на множества! И это далеко не полный список.

Под катом неформальный гайд — как понять, что перед вам может быть NP задача и что делать, если это именно она и оказалась. Сегодня мы атакуем этот вопрос с практической стороны.

Убедиться, что перед вам действительно она

Как понять, что перед вами оказалась NP-полная задача? Во-первых, самая простая эвристика на обнаружение — поиск по уже известным NP-полным задачам с целью определить что-то похожее, таких списков немало — например.

Второе, рассмотреть следующие свойства задач:

• Нужно выбрать решение, в котором n элементов из пространства exp(n)
• Если у вас уже есть решение длины n из этого пространства — оно легко (полиномиально) проверяется
• Выбор одного из элементов решения (может) влияет на выбор всех остальных (не обязательно всех).
• В худшем случае варианты всегда можно перебрать, рассмотрев все экспоненциальное пространство простым перебором.
• Параметры n — длина решения или само пространство не имеют фиксированного значения, то есть речь не идет о всегда фиксированной шахматной доске 8 на 8, а об общем виде задачи N-на-N.

Подробнее про свойства NP-полных задач тут и тут.

Пример работы по данному списку

Приведем простой пример на задаче, которую недавно утвердили как NP-полную!

По материалам статьи. Нужно расставить N ферзей на доске размера N на N, при условии, что уже K <= N расставлены на доске (картинка из оригинальной научной статьи)

Во-первых, заметим, что очень похожая задача с частично заставленным латинским квадратов NP полна.

А далее идем по списку:

• Нужно найти N ферзей на из пространства exp(N) (=N^2 * (N^2-1) *....).
• Решение из N ферзей тривиально проверяется — для каждого ферзя надо проверить диагонали, вертикали и горизонтали.
• Постановка одного делает выбор ряда других невалидным — т.е. есть зависимости между элементами решения (нельзя расставить ферзей независимо).
• Здесь можно решить задачу перебором для произвольно выбранной доски за exp(N) — ставим первого в первого на (i,j) позицию, второго на любую другую незанятую, и тд. Перебор с возвратом гарантированно найдет решение.
• Задача не имеет фиксированных параметров — то есть сформулирована в общем виде и по мере роста N растет и сложность.

Заметьте, что один из пунктов списка не выполняется, если всегда известно, что доска чистая и задача становится тривиальной.

И более того, это условный практический подход — эвристика по обнаружению NP-полных задач (со всеми плюсами и минусами).

Сведение

Источник

Почему имея на руках аналогичные задачи бывает непросто понять формально, что перед нами NP-задача? По-настоящему мы должны свети NP задачу к нашей, тогда мы точно будет знать, что наша задача NP-трудная! И если мы смогли ее смоделировать, как в списке выше, то она полная — то есть по крайней мере NP и не более чем NP, фактически “самая трудная среди NP задач” (как и остальные NP-полные).

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

А нужно либо (об этом всем мы поговорим ниже):

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

Не опускать руки!

Самое важное — это оценить размеры-параметры и реалистичные сценарии!

xkcd.com/287

Например, вы знаете, что несмотря на то, что значения параметров не фиксированы, но условный N < 100 на всех практических сценариях не реализуется — значит, что условный перебор может для вас быть реальным решением.

Вам нужно определить для себя: какие у меня реальные значения параметров возможные и реально приходят в систему, какое вообще распределение и особенности данных, что реально, а что нет? А нужно ли нам самое оптимальное решение? Пройдемся по этим пунктам.

Распределение входных данных

Или несмотря на то, что в общем случае входные данные могут быть любыми, но опять же на примере ферзей — обычно фиксирован один ферзь или даже ни одного. Значит, что в 90% случаев вы можете использовать очень простое решение и вызывать сложное только в крайних случаях.

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

Вот пример, того как оценивалось решение для очень специализированной задачи NP-полной tiling против общего метода моделирования целого класса таких задач с помощью методов логического программирования:

(из статьи Relational Data Factorization (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Relational data factorization, Machine Learning, volume 106))

Во-первых, скорость у спец решения LTM-k и общего метода существенно отличаются. Таким образом решение для именно такого типа задач на эвристиках может полностью решать эту проблему.

Во-вторых, пожертвовав качеством решения, общий приближенный метод давал очень похожую скорость.

Эвристики и аппроксимация

Последний и самый мощный инструмент — это использовать системы моделирования NP-полных задач, такие как например Answer Set Programming.

Подробнее про языки логического программирования.
Например решение задачи о расстановке ферзей будет выглядеть вот так:

% domain
row(1..n).
column(1..n).

% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X)    } 1 :- column(Y).

% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.

Проведя простой эксперимент по поиску решений для разного количества ферзей N — мы получим следующее: по оси Х — ферзи, по Y — время в секунда по поиску решения:

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

Тогда, если мы знаем, какие размеры доски являются для нас реальным, мы можем понять насколько это точное решение приемлемо для нас в настоящей системе.

Выводы

Тезисно пройдемся, по идеям из статьи в виде чек листа

• Определить, что перед вами действительно NP задача.
• Понять какие реалистичные значения параметров и распределение данных.
• Попробовать написать (порядок зависит от разработчика и/или задачи):
  • Точное решение на эвристиках (на основе нашего анализа) — будет ли достаточно быстро?
  • Приближенное решение на эвристиках — будет ли достаточно точно?
  • Точное общее решение с помощью систем моделирования NP-задач — будет ли удовлетворять ресурсам системы и задачи? Потребление памяти, CPU и время работы? Часто они очень прожорливы.
• Провести эксперименты и сравнить решения: качество, время и корректность найденных решений.
• Тестирование на реальной системе — эксперименты экспериментами, а как будут вести себя библиотеки и системы разработанные в университетах в боевых условиях — еще та загадка. Надо проверять!

Другие заметки Дата Сатаниста:

Автор: paramonov_ruvds

Источник