Глава 6. Преодолевая трудности

Во второй главе мы с вами побывали в идеальном мире. Равенство P и NP сделало нашу жизнь прекрасной и удивительной. Исследовать можно было все. Оптимизировать – тоже. Машины умели выполнять почти все мыслимые и немыслимые операции. Прекрасно, волшебно, пугающе… и, скорее всего, нереально.

На самом деле мир наверняка далек от совершенства – этакая «неэлегантная вселенная», в которой P и NP не равны. Во всяком случае, именно в таком мире мы будем жить до тех пор, пока не найдем эффективный алгоритм для решения задач из NP. Но что же делать, если мы не можем эффективно решить какую-то задачу? Оставить на потом?

К сожалению, некоторые трудные задачи нельзя так просто взять и отмести. Гарри работает планировщиком на производственном предприятии «Рога и копыта». Его босс Эми поручает ему настроить линию на сборку последней модели мобильного телефона «Эйфон» и минимизировать при этом время сборки. Гарри читал предыдущие главы нашей книги, поэтому смело отвечает: «Извините, но эта задача NP-полная. Если даже известные ученые считают, что быстрого решения нет, то что уж мне пытаться? Я лучше в боулинг пойду поиграю». На что Эми разрешает ему веселиться хоть до утра, поскольку в «Рогах и копытах» он больше не работает.

На место Гарри в срочном порядке наняли Джорджа. К счастью для себя, Джордж читал эту главу и потому сумел настроить линию на производство «Эйфонов». Неужели он изобрел гениальный алгоритм, который всегда оптимально распределяет подзадачи? Нет. Но с работой он все-таки справился? Безусловно.

NP-полные задачи «приручить» не так-то просто. Если P ? NP, то мы никогда и ни для одной из них не найдем хороший, быстрый алгоритм, который бы во всех случаях выдавал наилучшее решение. Впрочем, это вовсе не значит, что сделать ничего нельзя. В данной главе мы рассмотрим несколько подходов к решению трудных задач.

Современные процессоры настолько мощны, что, когда размер входа не очень велик, можно просто перебрать все потенциальные решения. Также можно применять алгоритмы, которые не годятся для некоторых частных случаев, однако по большей части работают вполне приемлемо. Кроме того, существуют алгоритмы, которые выдают пусть и не оптимальное, но все же довольно близкое к нему решение.

Иногда NP-полная задача упорно не желает поддаваться. Что с ней делать? Перейти к другой NP-полной задаче. Или взять и плюнуть на все, потому что есть дела и поважнее.