Золотой билет. P, NP и границы возможного - Лэнс Фортноу Страница 26

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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