В поисках билета
Иногда найти билет все же удается. Предположим, мне нужно поехать из Чикаго в Нью-Йорк на машине. Не долго думая, я забиваю адрес в навигатор, который уже через минуту-другую показывает оптимальный маршрут, и жму на газ. Подробная карта США со всеми городами и улицами занимает миллионы байт; возможные маршруты исчисляются гораздо более крупными цифрами. Сколько маршрутов можно проложить из Чикаго в Нью-Йорк? Грубейший подсчет даст нам свыше вигинтиллиона (единица и 63 нуля) вариантов, и запрет движения по встречке на односторонних улицах мало что изменит. У навигатора просто нет времени на такое количество проверок; как же он умудряется найти самый быстрый маршрут?
На самом деле маршруты обладают одной интересной особенностью. Добавим в программу промежуточный пункт назначения – скажем, Питтсбург. Кратчайший маршрут из Чикаго в Нью-Йорк через Питтсбург – это сумма кратчайших маршрутов из Чикаго в Питтсбург и из Питтсбурга в Нью-Йорк. Без заезда в Питтсбург до Нью-Йорка можно добраться и быстрее, однако при наличии промежуточной точки наилучшим решением будет склеить два кратчайших маршрута.
Именно так и сужают круг поиска навигационные программы. Десять тысяч или даже сто тысяч вариантов – это уже не вигинтиллион; современный процессор проверит их без труда.
Поиск кратчайшего пути не охватывает все аспекты проблемы равенства P и NP. Задача коммивояжера доказывает, что при наличии огромного числа вариантов совсем не обязательно перебирать их все; главный вопрос, однако, заключается в том, всегда ли можно обойтись без такого перебора.
Долгая дорога
Эта книга расскажет вам захватывающую историю о P и NP. Что это за классы? Какая между ними разница? Что такое NP-полные, или самые трудные, поисковые задачи? Как они связаны с проблемой P и NP?
Для наглядности приведу один маленький пример. Сколько человек входит в максимальную клику на Facebook, т. е. в наибольшую по численности группу, в которой все дружны между собой? Может, сотня? А может быть, тысяча? Даже при наличии доступа ко всем необходимым данным ответить на этот вопрос будет крайне непросто; искать максимальную клику не легче, чем возиться с какой-нибудь другой поисковой проблемой.
Какая перспектива ожидает нас, если классы равны? Совершенный мир, в котором все можно вычислить быстро. Ответы на вопросы будут приходить почти мгновенно; смертельных болезней не останется, и вселенная раскроет нам все свои тайны. Однако есть здесь и своя ложка дегтя: с компьютерами, которые могут почти все, нас ждет безработица и потеря конфиденциальности.
Впрочем, жизнь в совершенном мире нам, скорее всего, не грозит. Так что трудные поисковые задачи никуда от нас не денутся. Впрочем, это еще не повод опускать руки: для таких задач разработаны особые методы. Эвристические алгоритмы, к примеру, почти во всех случаях выдают корректный ответ, а приближенные позволяют получить решение, близкое к оптимальному.
Какова