[Russian] Что такое NP-проблемы: для неспециалистов

Есть несколько простых примеров практически важных 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-проблем -- найти решение очень трудно, но проверить решение очень легко, можно даже без компьютера, вручную.

Еще есть известная игра Sokoban. Выглядит вроде бы просто. Но найти решение бывает очень трудно. Посмотрите список уровней. Разумеется, есть практическая польза от таких задач -- планирование перемещения по складу, для человека или для робота.

В научпопе, когда тема касается NP-проблем, часто вспоминают Судоку. Это тоже NP-проблема, но пример не очень удачный.

Так же вспоминают задачу о 8-и ферзях. Где-то я читал (забыл) что эта задача появилась когда кто-то хотел расставить военных так, чтобы они покрывали как можно больше территории. Раз уж так, то есть другая NP-задача на эту тему: задача о вершинном покрытии (vertex cover). У вас есть здание, внутри коридоры и не движущиеся охранники. Каждый охранник видит несколько коридоров вокруг себя. Нужно обойтись минимальным кол-вом охранников так, чтобы все они могли наблюдать все коридоры.

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

Также есть очень популярное заблуждение что поиск более хорошего алгоритма для решения NP-задач (проблема P=NP?) поможет взломать сразу все криптоалгоритмы (в широком смысле) или только RSA (в узком смысле, факторизация больших чисел). Например, об этом есть кино Travelling Salesman (2012). Это неверно. Поиск более хорошего алгоритма не обязательно сделает решение быстрым. Например, Дональд Кнут считает, что возможно будет прогресс в этой области, но решение будет ненамного быстрее уже существующих алгоритмов, так что решение особой радости никому не доставит.

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

Пока что, эти задачи решаются полным перебором + эвристиками. Включая SAT-солверы.

Человек, способный найти решение получше, скорее всего, оставит заметный след в информатике и математике.

Дальше об этом


List of my other blog posts.

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.