Золотой билет - Лэнс Фотноу

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

Любой вычислительный алгоритм – это тоже метод решения какого-либо вопроса. Эвристические алгоритмы работают подобно правилу большого пальца: иногда они ошибаются, однако в большинстве случаев находят верное решение. Для NP-полных задач такие алгоритмы начали появляться задолго до того, как об их NP-полноте стало известно. За последние десятилетия сложными эвристическими методами «обзавелось» огромное множество трудоемких задач. Ни один из этих методов не является универсальным и не годится для всех случаев сразу, однако в общем и целом они со своей работой справляются.

Рис. 6.2. Карта Соединенных Штатов

Давайте подробно рассмотрим простой, но очень мощный эвристический алгоритм раскраски карт. В третьей главе мы объяснили, почему для правильной раскраски карты Соединенных Штатов, т. е. для раскраски, при которой соседние штаты имеют разные цвета, требуется не меньше четырех цветов.

Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Для раскраски всех штатов кольца требуется не меньше трех цветов; Невада имеет с ними общие границы, так что для нее придется добавить четвертый. Другие штаты также образуют подобные кольца: к примеру, штат Кентукки окружают Теннесси, Вирджиния, Западная Вирджиния, Огайо, Индиана, Иллинойс и Миссури. Здесь нам тоже, как и в случае с Невадой, понадобится три цвета для кольца и четвертый для Кентукки.

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

На рисунке ниже представлена карта областей Армении.

Всего две из них целиком лежат внутри страны. Котайк окружен шестью областями, а столица Ереван – четырьмя. Эвристический метод говорит нам, что если все внутренние регионы имеют четное число соседей, то для раскраски карты хватит трех цветов. И мы видим, что для Армении так и получается.

Швейцарию окружает нечетное число соседей – пять. Это Франция, Италия, Австрия, Лихтенштейн и Германия. Несмотря на это, карту на рис. 6.5 тоже можно раскрасить в три цвета.

Дело в том, что Лихтенштейн вклинился между Швейцарией и Австрией и разбил их общую границу на две, поэтому Австрию нужно учитывать дважды. Оказывается, важно не количество соседних государств, а количество общих границ; у Швейцарии их шесть, а шесть – число четное. Заметим, что считаются только внешние границы, и страны, целиком лежащие внутри другого государства, не учитываются вообще (например, Ватикан внутри Италии).

Рис. 6.3. Армения

Если бы наш эвристический метод всегда выдавал верное решение, это означало бы, что для раскраски в три цвета существует эффективный алгоритм, а поскольку задача раскраски NP-полна, то и для всех остальных NP-задач тоже существует эффективный алгоритм, поэтому P = NP. Думаю, вы уже догадались, что иногда у него случаются проколы?

Эвристический метод имеет ровно два исключения.

1. На карте имеется озеро, по которому проходит граница между регионами. Например, озеро Мичиган отделяет Иллинойс от штата Мичиган.

Рис. 6.4. Раскраска Армении

2. Четыре или более регионов встречаются в одной точке. Например, Аризона, Нью-Мексико, Колорадо и Юта.

Впрочем, в случае с США исключения роли не играют, поскольку мы и так уже знаем, что цветов нужно четыре (не считая, разумеется, синего для озер).

В реальной жизни этот эвристический метод почти не ошибается. Ну а как он справится с картой воображаемого Королевства, на которой у любой провинции четное число соседей (четыре), и которую, однако, невозможно правильно раскрасить в три цвета (не считая, опять же, синего для озер)?

Рис. 6.5. Швейцария

Рис. 6.6. Раскраска Швейцарии

Каждая из одиннадцати провинций граничит ровно с четырьмя другими, при этом в ее «окружении» обязательно имеется озеро. Наш метод говорит, что карту Королевства можно правильно раскрасить в три цвета; однако он ошибается, поскольку при наличии лишь трех цветов какие-нибудь две провинции непременно окажутся одинаково окрашены.

Рис. 6.7. Карта Королевства заклятых друзей

Международная конференция The International Conference on Theory and Applications of Satisfiability Testing стремится охватить все аспекты проблемы выполнимости. Особое внимание уделяется хорошим эвристическим алгоритмам. В рамках конференции проводится конкурс SAT Race, в котором участвуют компьютерные программы по решению SAT-задач. Задачи для конкурса могут быть сгенерированы случайным образом, позаимствованы из различных областей науки и техники или же сконструированы специально с таким расчетом, чтобы решить их было крайне трудно. Многие программы-участники успешно справляются с задачами на миллион переменных.