Лэнс Фотноу - Золотой билет
А как обстоит дело с игрой на большом поле? Например, с сеткой 25 × 25, в которой каждая строка, каждый столбец и каждый мини-квадрат должны содержать все буквы от A до Y?
В этом случае вычисление займет уже гораздо больше времени, а с сеткой 100 × 100 вообще ни один современный компьютер не справится.
Рис. 4.4. Гигантское судоку
Поиск решения гигантского судоку – задача NP-полная. Считаете себя мастером судоку? Или знаете надежный способ решения какой-нибудь другой гигантской головоломки? Тогда в ваших руках ключ от решения задачи о выполнимости, задачи коммивояжера и тысячи других NP-полных проблем!
Есть еще много игр для одного игрока, решение которых представляет собой NP-полную задачу. Возьмем, к примеру, встроенного в Microsoft Windows «Сапера».
Рис. 4.5. «Сапер»
Число в ячейке говорит о количестве мин, расположенных в соседних с ней квадратиках – по вертикали, горизонтали и диагонали. Вы должны либо открыть ячейку, чтобы узнать это число, либо поставить на ней флажок, если думаете, что в ячейке бомба. Откроете бомбу – проиграете. Нахождение выигрышной стратегии в гигантском «Сапере» также представляет собой NP-полную задачу. На рисунке ниже показано расположение оставшихся бомб.
Другой пример – «Тетрис», в котором нужно передвигать и поворачивать фигурки так, чтобы образовывались сплошные горизонтальные ряды. Заполненный ряд тут же исчезает. Игра заканчивается, когда на экране больше не осталось свободных рядов; цель играющего – продержаться как можно дольше.
Фигурки бывают разных форм. В классическом варианте «Тетриса» вы не знаете, какая фигурка выпадет следующей. Впрочем, если бы вам даже заранее сообщили последовательность появления фигурок, выбор оптимальной стратегии все равно остался бы NP-полной задачей.
Рис. 4.6. Оставшиеся бомбы
Рис. 4.7. «Тетрис»
Кто бы мог подумать, что, научившись мастерски играть в судоку, «Тетрис» или «Сапер», можно доказать равенство P и NP и решить одну из задач тысячелетия!
Рис. 4.8. Виды фигурок в «Тетрисе»
Как насчет кубика Рубика? Наверняка это тоже NP-полная задача: ведь если даже освоение классического варианта 3 × 3 × 3 занимает столько времени, что уж говорить о больших кубах?
Рис. 4.9. Кубик Рубика. Фото: Том ван дер Занден
На самом деле все совсем не так. Благодаря такой области математики, как теория групп, у нас есть эффективные алгоритмы, способные справиться даже с гигантскими кубами. Оптимального решения они не дают, но все же позволяют собрать кубик относительно быстро вне зависимости от его начального состояния.
Верится с трудом, но это правда – кубик Рубика намного проще «Тетриса», «Сапера» и судоку.
А как обстоит дело с играми для двоих? Шахматы, шашки, го, «Отелло»? Если говорить о гигантских версиях, то они не уступают по сложности ни проблеме выполнимости, ни другим NP-полным задачам, однако к классу NP, тем не менее, не принадлежат. Вы спросите, почему? Потому что если я скажу, что белые обеспечат себе выигрыш, передвинув пешку на «e3», то вы вряд ли сможете быстро это проверить. Ученые полагают, что на самом деле эти игры намного труднее любой NP-полной задачи.
Цепочка из почек
Почки выводят из организма балластные вещества. У большинства людей обе почки здоровы; если одна отказала, другая будет работать за двоих, позволяя человеку жить полноценной жизнью. Иногда отказывают обе почки, и тогда от смерти может спасти только регулярный диализ, который дорого стоит и отнимает много времени.
Если ваши почки здоровы, вы можете стать донором и отдать одну из них тому, у кого почки не функционируют вообще, – при условии совместимости с организмом реципиента. Совместимость проверяется с помощью несложного анализа крови.
Допустим, почки Элис вышли из строя. Ее муж, Боб, согласен стать донором. Если Боб пройдет тест на совместимость, врачи пересадят Элис его почку.
А если не пройдет? Тогда можно будет попытаться совершить обмен почками.
Предположим, Чарли требуется почка, его брат Дэвид готов отдать свою, но его почка не подходит. Если Дэвид совместим с Элис, а Боб – с Чарли, то можно провести операцию сразу на четырех пациентах, и в результате и Элис, и Чарли получат рабочую почку.
Представьте, что у нас имеется база данных с информацией по всем совместимым парам донор-реципиент. Тогда мы можем запустить на ней эффективный алгоритм, который найдет наибольшее возможное число обменов. Задача совсем не сложная и аналогична задаче о максимальном числе паросочетаний, рассмотренной в предыдущей главе.
Ограничиваться двумя парами за раз совсем не обязательно. В конце 2011 года силами шестидесяти хирургов была проведена цепочка из тридцати таких операций. Для тридцати человек это был единственный способ обрести здоровье.
Если мы в нашей базе разрешим обмен по цепочке, желая помочь как можно большему числу людей, то снова придем к NP-полной задаче. Равенство P и NP спасет чьи-то жизни, а это уже гораздо серьезнее, чем гарантированный выигрыш в игре «Сапер»!
Мастера конспирации
Как правило, те NP-задачи, которыми ученые занимались в середине семидесятых, довольно быстро либо оказывались NP-полными, либо «скатывались» в класс P, поскольку для них появлялись эффективные алгоритмы. Однако некоторые особо вредные экземпляры упорно не желали поддаваться классификации; одни сумели продержаться несколько лет, другие не удалось рассекретить до сих пор.
Изоморфизм графов
В Королевстве насчитывается несколько сотен фанатов «Блейд Квеста» – массовой многопользовательской ролевой онлайн-игры. Как и в других играх подобного плана, участники здесь получают новую личность, или аватар; каждый исполняет роль определенного персонажа и общается с другими персонажами, за которыми тоже стоят реальные жители Королевства. В виртуальном мире дружеские связи сохраняются: те, кто дружат в жизни, становятся друзьями и в игре, а те, кто враждуют, заново проникаются взаимной неприязнью.
Джон, Изабель, Кевин, Лаура, Молли и Нэнси очень любят играть в «Блейд Квест».
Рис. 4.10. Любители «Блейд Квеста»
Их персонажей зовут Акрис, Лэмбо, Криард, Де Гарольд, Хрхрхр и Вирус, но кто под каким именем скрывается – неизвестно: эта информация пользователям игры недоступна, и они могут видеть только схему дружеских связей между персонажами.
Рис. 4.11. Аватары в «Блейд Квесте»
Проанализировав обе схемы, Лаура отправила остальным игрокам сообщение от имени своего аватара: «Я знаю, кто ты!» А вы уже догадались, кто есть кто?
Схемы будут соответствовать друг другу лишь в том случае, если Изабель – это Хрхрхр, Джон – Де Гарольд, Кевин – Криард, Лаура – Лэмбо, Молли – Акрис, а Нэнси – Вирус. Например, «реальная» Молли дружит с Лаурой и Нэнси, а ее аватар Акрис – с Лэмбо и Вирусом.
Установить, соответствуют ли друг другу подобные схемы, – это все равно что определить, изоморфны два графа или нет. Некоторые схемы сопоставить нельзя, другие – можно, иногда даже несколькими способами. Проблема изоморфизма графов лежит в NP, поскольку, зная, кто есть кто, можно легко проверить соответствие дружеских связей.
Вопрос о том, относится ли проблема изоморфизма также и к классу P, до сих пор открыт; никто пока не придумал хороший алгоритм, который всегда находил бы искомое соответствие в случае, если оно действительно есть. Мы также не знаем, является ли эта проблема NP-полной, хотя, по мнению ученых, некоторые признаки косвенно указывают на то, что не является. Изоморфизм графов стоит в ряду немногочисленных задач, занимающих некое промежуточное положение: они вроде бы труднее, чем задачи из P, но легче, чем задачи NP-полные, вроде поиска гамильтонова пути или максимального разреза.
Простые числа. Разложение на множители
Число 15 можно разложить на множители, т. е. представить в виде произведения других натуральных чисел, двумя способами: 15 × 1 и 5 × 3. Для числа 24 способов уже гораздо больше, например – 24 × 1, 12 × 2, 8 × 3, 6 × 4. А вот число 17 иначе как в виде 17 × 1 не представишь: оно простое, т. е. делится только на себя и на единицу. Множество простых чисел бесконечно; первые восемь его представителей – 2, 3, 5, 7, 11, 13, 17, 19. Самое большое простое число, известное на момент написания этой книги, состоит из 12978189 цифр и начинается так: 316470269330255923143453723…
