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