Наверное, каждый сталкивался с тем, что ему приходилось сталкиваться с какой-то сложной задачей, решение которой не удавалось найти не только сразу, но даже после долгих тяжелых часов работы или дней.
Сегодня мы поговорим об одном из классов таких задач – NP-полных.
Реально ли столкнуться с такими задачами в повседневной жизни? На самом деле они возникают в огромном диапазоне случаев: комбинаторика, графы и сети, выполнение логических формул, работа с картами, оптимальные нагрузки, отображения, задачи дискретной оптимизации, поиск самых длинных последовательностей, поиск равных сумм и множество заданных задач! И это не полный список.
Ниже под катом неофициальное руководство — как понять, что вы можете столкнуться с проблемой NP и что делать, если это именно так.
Сегодня мы рассмотрим этот вопрос с практической точки зрения.
Убедитесь, что это действительно она
Как узнать, столкнулись ли вы с NP-полной проблемой? Во-первых, простейшая эвристика обнаружения — это перебор уже известных NP-полных задач с целью определить нечто подобное; таких списков много - Например .Во-вторых, учтите следующие свойства задач:
- Нам нужно выбрать решение, в котором есть n элементов из пространства exp(n)
- Если у вас уже есть решение длины n из этого пространства, его можно легко (полиномиально) проверить.
- Выбор одного из элементов решения (может) влияет на выбор всех остальных (не обязательно всех).
- В худшем случае варианты всегда можно перебрать, рассмотрев все экспоненциальное пространство с помощью простого поиска.
- Параметры n — длина решения или само пространство — не имеют фиксированного значения, то есть речь идет не о всегда фиксированной шахматной доске 8 на 8, а об общем виде задачи N-на-N. .
Пример работы из этого списка
Приведем простой пример задачи, которая недавно была признана NP-полной! По материалам статьи.
Вам необходимо разместить N ферзей на доске размером N на N при условии, что K <= N are already placed on the board (picture from the original scientific article) 
Во-первых, отметим, что очень похожая задача с частично заполненными латинскими квадратами 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 is not implemented in all practical scenarios - this means that conditional enumeration may be a real solution for you. Вам необходимо определить для себя: какие реальные значения параметров возможны и реально поступают в систему, каково общее распределение и особенности данных, что реально, а что нет? Нужно ли нам самое оптимальное решение? Давайте пройдемся по этим пунктам.
Распределение входных данных
Или несмотря на то, что в общем случае входные данные могут быть любыми, но опять же на примере ферзей обычно фиксируется один ферзь или даже ни один.Это значит, что в 90% случаев можно использовать очень простое решение и вызывать сложное только в крайних случаях.
Пример, где в среднем все распространенные комбинации просты: проблема дополнения ферзей - мы знаем, что условная DFS + эвристика может найти решения очень быстро в большинстве случаев и быть чрезвычайно сложной только в очень необычных ситуациях.
Вот пример того, как решение очень специализированной NP-полной задачи замощения оценивалось по сравнению с общим методом моделирования целого класса таких задач с использованием методов логического программирования: 
(из статьи Реляционная факторизация данных (Парамонов, Сергей; ван Леувен, Маттейс; Де Раедт, Люк: Реляционная факторизация данных, Машинное обучение, том 106))
Во-первых, скорость специального решения LTM-k и общего метода существенно отличаются.
Таким образом, решение именно этого типа задач с помощью эвристики может полностью решить эту проблему.
Во-вторых, пожертвовав качеством решения, общий приближенный метод дал очень похожую скорость.
Эвристика и аппроксимация
Последним и наиболее мощным инструментом является использование NP-полных систем моделирования проблем, таких как, например.
Программирование набора ответов .
Узнайте больше о языках логического программирования.
Например, решение задачи о расстановке ферзя будет выглядеть так:
Проведя простой эксперимент по поиску решений для разного количества ферзей N, получим следующее: по оси X — ферзи, по Y — время в секунду на поиск решения:% 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.
Мы видим, что несмотря на то, что рост времени явно не является полиномиальным (что логично), мы неплохо справляемся с адекватным количеством ферзей и размеров доски.
Тогда, если мы будем знать, какие размеры платы для нас реалистичны, мы сможем понять, насколько приемлемо для нас именно это решение в реальной системе.
выводы
Пройдемся по идеям из статьи в виде чек-листа.
- Определите, что ваша проблема действительно является проблемой NP.
- Поймите реалистичные значения параметров и распределение данных.
- Попробуйте написать (порядок зависит от разработчика и/или задачи):
- Точное решение, основанное на эвристике (на основе нашего анализа) – будет ли оно достаточно быстрым?
- Приблизительное решение, основанное на эвристике – будет ли оно достаточно точным?
- Будет ли точное общее решение с использованием систем моделирования задач NP удовлетворять ресурсам системы и проблемы? Потребление памяти, процессора и время работы? Зачастую они очень прожорливы.
- Проводить эксперименты и сравнивать решения: качество, время и правильность найденных решений.
- Тестирование на реальной системе — это эксперименты экспериментами, а вот как библиотеки и системы, разработанные в университетах, поведут себя в боевых условиях — до сих пор загадка.
Нам нужно проверить!
Другие заметки от Date satanist:
Что может пойти не так с Data Science? Сбор данных Заметки ученого-датировщика: как рассчитать время марафонского бега, лежа на диване Заметки специалиста по данным: маленькие утилиты – большие преимущества Заметки специалиста по данным: персонализированный обзор языков запросов к данным Заметки Data Scientist: на что обратить внимание при выборе модели машинного обучения — личный топ-10 Заметки Date Scientist: с чего начать и нужно ли это? Заметки Дата Сатанист: честность модели
Теги: #Машинное обучение #Большие данные #машинное обучение #наука о данных #анализ данных #Интеллектуальный анализ данных #ruvds_articles #ruvds_articles #честность #справедливость
-
Локьер, Джозеф Норман
19 Oct, 24 -
Евросоюз Грозит Microsoft Огромными Штрафами
19 Oct, 24 -
Яблоко И Цены
19 Oct, 24 -
Прием Платежей На Сайте
19 Oct, 24 -
Tp-Link Archer C2: Wi-Fi Ac В Массы
19 Oct, 24
