Золотой билет

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

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

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

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

Полный перебор

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

Однако раньше все было совсем по-другому. В 1971 году, когда Стивен Кук поднял вопрос о равенстве P и NP, компания Intel выпустила микропроцессор Intel 4004 – первый полноценный центральный процессор, который уместился на одном кристалле и стал доступным для потребителей. Intel 4004 мог выполнять 92000 операций в секунду и для того времени был очень скоростным.

Возьмем для примера подробно разобранную Куком задачу о выполнимости и рассмотрим случай с двадцатью переменными. Применим к ней простейший алгоритм, который методично перебирает все возможные комбинации значений переменных, устанавливая их в TRUE или FALSE. Если предположить, что на обработку одной комбинации уходит 100 шагов, то выполнимость всей формулы будет проверяться примерно 19 минут. Долго, конечно, но ведь могло быть и хуже! Однако проблема в том, что с двадцатью переменными каши особо не сваришь.

Двадцать пять переменных обрабатывались бы примерно 10 часов. Тридцать – чуть больше 13 суток. Ну а с сорока переменными мы бы ждали с 1971-го года по 2009-й.

Сейчас Intel каждый год выпускает несколько новых моделей процессоров. Рассмотрим, к примеру, появившийся в 2009-м Intel i7–870, который мог выполнять 2,93 миллиарда операций в секунду – в 30000 раз больше, чем Intel 4004. С сорока переменными он справился бы часов за десять, так что в 1971-м быстрее было бы просто подождать 38 лет и воспользоваться технологиями 2009-го.

Для некоторых NP-полных задач можно привести и более впечатляющие примеры. Возьмем задачу о коммивояжере, который ищет кратчайший маршрут, проходящий через максимально возможное число городов. Применяя метод секущих плоскостей, мы легко найдем решение даже для 10000 городов. На рисунке ниже представлено решение для 13509 населенных пунктов с населением от 500 человек.

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

Современные микросхемы работают почти на пределе физических возможностей. Впрочем, число транзисторов на одном кристалле неизменно увеличивается, так что производительность компьютеров пока продолжает расти с той же бешеной скоростью, подтверждая закон Мура. Когда-нибудь мы наверняка научимся решать NP-полные задачи гораздо большего размера. Однако при увеличении размера входа трудоемкость задачи также сильно возрастает, поэтому не стоит ждать, что уже в ближайшем будущем мы сможем быстро проверять выполнимость для 150 переменных или находить коммивояжеру оптимальный маршрут на 20000 городов.

Рис. 6.1. Коммивояжер: города с населением более 500 человек

Эвристические методы

Когда английскому плотнику XVII века требовалось прикинуть расстояние в дюймах, он ориентировался на ширину своего большого пальца. Вероятно, отсюда и пошло так называемое правило большого пальца – простой и неточный, но вполне приемлемый метод решения того или иного вопроса. К примеру, поговорка «Красный закат – моряк, веселись! Красный рассвет – моряк, берегись!» дает нам примитивный, но достаточно надежный метод предсказания погоды. А закон Мура грубо оценивает рост мощности компьютеров.