Золотой билет - Страница 33

Рис. 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-задач. Задачи для конкурса могут быть сгенерированы случайным образом, позаимствованы из различных областей науки и техники или же сконструированы специально с таким расчетом, чтобы решить их было крайне трудно. Многие программы-участники успешно справляются с задачами на миллион переменных.

Эвристические алгоритмы не всегда способны выдать правильный ответ, и на конкурсе SAT Race их оценки далеки от высшего балла. Тем не менее они нередко умудряются решать задачи гигантских размеров – благодаря различным хитростям и невероятно высокой производительности современных компьютеров.

Иголка в стоге сена

Предположим, мы ищем клику из трех человек среди всех 20000 жителей Королевства. По самым грубым подсчетам нужно проверить чуть больше триллиона вариантов – сущая ерунда для любого современного компьютера. Однако дальше варианты начинают размножаться с космической скоростью, перед которой компьютеры очень быстро пасуют: для клики размера четыре требуется уже 6 квадриллионов проверок, для клики размера пять – 26 квинтиллионов, а для клики размера шесть – 88 секстиллионов (т. е. 88 и 21 ноль).

Впрочем, поиск «иголки в стоге сена» не всегда превращается в такую катастрофу. Группа жителей Королевства считается очень приятной, если для любой пары друзей хотя бы один из них в эту группу входит.

Рис. 6.8. Дружеские связи

На представленной выше диаграмме Боб, Даниэль, Фрэнк и Гарри образуют очень приятную группу, поскольку все дружеские связи (линии на схеме) завязаны на них.

Рис. 6.9. Очень приятная группа размера четыре

А вот очень приятную группу размера три составить уже не получится. Например, если взять Элис, Чарли и Фрэнка – потеряются дружеские связи Ева – Даниэль и Джордж – Гарри.

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

Давайте взглянем на дружеские связи Фрэнка. Если Фрэнк не является членом очень приятной группы, то тогда в нее должны входить Джордж, Даниэль и Ева, поскольку все они с Фрэнком друзья. Каждая очень приятная группа обязательно содержит либо Фрэнка, либо всех его друзей – даже если их не три, а целых сто.

При помощи подобных хитростей можно избежать полного перебора всех потенциальных вариантов при поиске небольших очень приятных групп. Для группы размера пять понадобится около 100000 проверок, для группы размера 10–200000 проверок, а для группы размера 30–601000 проверок; любой ноутбук справится с такой задачей за считаные доли секунды. Поиск очень приятной группы размера 113 потребует проверки триллиона вариантов и будет длиться не дольше, чем поиск клики из каких-то несчастных трех человек.

Рис. 6.10. Не очень приятная группа размера 3

Стоп. Выходит, очень приятные группы искать не так уж сложно? Но разве Карп не доказал, что поиск очень приятной группы минимального размера (т. е. минимального вершинного покрытия) – задача NP-полная? Дело в том, что у жителей Королевства друзей обычно очень много. Маловероятно, что все дружеские связи завязаны лишь на 113 жителях. А как только мы замахнемся на группы побольше, число вариантов тут же резко возрастет.