![Заметки Датасатаниста: что делать, если перед вами оказалась NP-полная задача - 1 Заметки Датасатаниста: что делать, если перед вами оказалась NP-полная задача - 1](https://www.pvsm.ru/images/2020/11/26/zametki-datasatanista-chto-delat-esli-pered-vami-okazalas-NP-polnaya-zadacha.png)
Наверное, каждый сталкивался с тем, что приходилось столкнуться с какой-то сложной задачей, решение к которой не удавалось подобрать не то что сразу — а даже после долгих упорных часов работы или дней. Об одном из классов таких задач — NP-полных, мы сегодня и поговорим.
А вообще реально ли встретить такие задачи в обычной жизни? На самом деле, они возникают в огромном ряде случаев: комбинаторика, графы и сети, выполнение логических формул, работа с картами, оптимальные загрузки, отображения, задачи дискретной оптимизации, нахождение самых длинных последовательностей, поиск равных сумм и многие задачи на множества! И это далеко не полный список.
Под катом неформальный гайд — как понять, что перед вам может быть NP задача и что делать, если это именно она и оказалась. Сегодня мы атакуем этот вопрос с практической стороны.
Читать полностью »