Тайны чисел. Математическая одиссея - Маркус Дю Сотой

Имеется другое любопытное свойство, связывающее все NP-полные задачи. Если вы найдете эффективную программу для одной из задач, это будет означать существование таких программ для всех остальных задач. Например, если вам удастся написать умную программу, которая будет выдавать коммивояжеру кратчайший путь, ее можно будет переделать в эффективную программу проверки того, может ли еще ваша команда стать чемпионом. Чтобы дать пример того, как это может сработать, рассмотрим две задачи из класса «иголка в стоге сена», или NP-полных задач, которые кажутся совершенно разными.

Задача о дипломатичном званом обеде

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

Задача о раскраске карты тремя цветами

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

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

Рис. 3.18. Линией соединены люди, которых нельзя пригласить на один обед

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

Рис. 3.19. Линией соединены страны, имеющие общую границу

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

Сапер

Это компьютерная игра для одного участника, которая имеется в каждом установочном комплекте операционной системы Microsoft. Цель игры состоит в том, чтобы очистить сетку от мин. Если вы щелкаете по квадратику на сетке, и там нет мины, то появляется число, показывающее, во скольких квадратиках вокруг данного есть мины. Если же вы щелкаете по мине… то взлетаете на воздух. Но саперный вызов на миллион долларов предлагает вам сделать несколько иное. Следующий рисунок не может появиться в настоящей игре, потому что никакое расположение мин не может дать такие числа (рис. 3.20). Число 1 означает, что лишь в одном из неоткрытых квадратиков есть мина, а число 2 означает, что заминированы оба.

Рис. 3.20

Но что можно сказать о следующем рисунке – можно ли увидеть такой в настоящей игре?

Рис. 3.21

Существует ли возможность разместить мины так, чтобы появились эти числа? Или же данный рисунок никоим образом не может возникнуть в настоящей игре, потому что не существует расположения мин, совместимого с этими числами? Ваша задача состоит в том, чтобы разработать эффективную программу, которая сумеет дать ответ на этот вопрос для какой угодно картинки.

Задача об упаковке

Вы руководите фирмой по переезду. Все ваши упаковочные ящики имеют одинаковую ширину и высоту, совпадающие с внутренними размерами вашего грузовика (ну, или чуть меньше этих размеров, так, чтобы их можно было разместить внутри). Но длина ящиков разная. Длина вашего грузовика 150 футов, а у имеющихся ящиков следующие длины: 16, 27, 37, 42, 52, 59, 65 и 95 футов.

Рис. 3.22. Упаковка коробок является математически сложной задачей

Можете ли вы найти комбинацию ящиков, которая наполнит грузовик самым эффективным способом? Вы должны найти алгоритм, определяющий для любого заданного числа N и набора меньших чисел n(1), n(2), …, n(r), существует ли набор меньших чисел, складывающийся в большее число.

Судоку

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

Такого рода задачи не являются просто играми: они возникают в бизнесе и промышленности, когда компаниям необходимо найти самое эффективное решение какой-то практической проблемы. Незанятое пространство или перерасход топлива влекут денежные потери, и менеджерам часто приходится решать одну из этих NP-задач. В телекоммуникационной промышленности даже используются коды, дешифровка которых зависит от того, удается ли найти иголку в стоге сена. Поэтому не только математики или заядлые игроки заинтересованы в решении этой задачи на миллион долларов.

Будь то математический анализ футбольных игр или организация званых приемов, раскрашивание карт или расчистка минных полей – задача на миллион долларов из этой главы появляется в столь разнообразных обличьях, что вы наверняка сумеете найти привлекательный для себя вариант. Но имейте в виду следующее: эта задача может казаться забавной и игровой, тем не менее она – одна из самых трудных задач на миллион долларов. Математики полагают, что во всех этих задачах имеется некая существенная сложность, из-за чего может не найтись эффективной программы для их решения. К сожалению, всегда оказывается труднее показать, почему что-то не существует, чем показать его существование. Но, по крайней мере, для вас может быть забавно попытаться получить миллион этой главы.