Есть несколько простых примеров практически важных NP-проблем.
1) Задача о раскрое листа. Есть лист фанеры (или чего угодно), его нужно распилить на несколько частей. Задача в том, чтобы использовать лист как можно лучше и ошметков осталось как можно меньше. Этим занимался еще Леонид Канторович в 1938, позже ему дали Нобелевскую премию. В моей книге есть пример о картонной игрушке, см.тут.
Вариант этой задачи -- заполнять грузовик/фуру ящиками разного размера. Конечно, хочется чтобы фур/грузовиков было меньше. Кстати, это почти как Тетрис.
Еще вариант этой задачи -- рассовывать виртуальные машины по серверам, так, чтобы использовать как можно меньше серверов. Или попроще -- рассовать файлы по флешкам так, чтобы задействовать минимум флешек.
2) Составление расписаний. Школьных, ВУЗовских, расписания поездов. Например, есть 20 человек, они встречаются друг с другом группами по 4 человека. Встречи будут проходить 5 дней. Нужно, чтобы каждый человек встретился со всеми 19 людьми по очереди, в эти 5 дней. Иными словами, любая пара человек из этих 20-и не должна встречаться друг с другом чаще одного раза. Варианты этой задачи - social golfer problem (проблема общительных гольфистов), Kirkman's Schoolgirl Problem (проблема школьниц).
Одно из решений:
Mon ABCD EFGH IJKL MNOP QRST Tue AEIM BJOQ CHNT DGLS FKPR Wed AGKO BIPT CFMS DHJR ELNQ Thu AHLP BKNS CEOR DFIQ GJMT Fri AFJN BLMR CGPQ DEKT HIOS
Еще.
Проблема довольно трудная. Попробуйте составить такую таблицу вручную, или при помощи какого угодно мощного компьютера. Хотя с виду, всё легко. Вот в этом скрипте, например, эта задача вовсе не решается на компьютере, там внутри просто набор готовых решений, которые показываются в зависимости от состояния кнопок.
Тут проявляется одно из важных свойств NP-проблем -- найти решение очень трудно, но проверить решение очень легко, можно даже без компьютера, вручную.
Так и Судоку. Найти решение иногда трудно, а вот проверить его верность легко, глазами обойти все ряды, столбцы и квадраты 3*3.
Еще есть известная игра Sokoban. Выглядит вроде бы просто. Но найти решение бывает очень трудно. Посмотрите список уровней. Разумеется, есть практическая польза от таких задач -- планирование перемещения по складу, для человека или для робота.
В научпопе, когда тема касается NP-проблем, часто вспоминают Судоку. Это тоже NP-проблема, но пример не очень удачный.
Так же вспоминают задачу о 8-и ферзях. Где-то я читал (забыл) что эта задача появилась когда кто-то хотел расставить военных так, чтобы они покрывали как можно больше территории. Раз уж так, то есть другая NP-задача на эту тему: задача о вершинном покрытии (vertex cover). У вас есть здание, внутри коридоры и не движущиеся охранники. Каждый охранник видит несколько коридоров вокруг себя. Нужно обойтись минимальным кол-вом охранников так, чтобы все они могли наблюдать все коридоры.
В сериале Numb3rs, математик в приступах депрессии пытается решить задачу про minesweeper (сапёр). Пример не очень удачный как для научпопа. А поиск мин в сапёре это действительно NP-задача, у меня она в книге решается тут.
Также есть очень популярное заблуждение что поиск более хорошего алгоритма для решения NP-задач (проблема P=NP?) поможет взломать сразу все криптоалгоритмы (в широком смысле) или только RSA (в узком смысле, факторизация больших чисел). Например, об этом есть кино Travelling Salesman (2012). Это неверно. Поиск более хорошего алгоритма не обязательно сделает решение быстрым. Например, Дональд Кнут считает, что возможно будет прогресс в этой области, но решение будет ненамного быстрее уже существующих алгоритмов, так что решение особой радости никому не доставит.
Но основная масса ученых считает что человечество пока не готово к пониманию NP-задач.
Пока что, эти задачи решаются полным перебором + эвристиками. Включая SAT-солверы.
Человек, способный найти решение получше, скорее всего, оставит заметный след в информатике и математике.
Post updated: 20240717 08:28:58 CEST.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.