Книга: Золотой билет

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

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

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

Однако раньше все было совсем по-другому. В 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 человек

Оглавление книги