Кит Йейтс - Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь

В 2008 году во время предвыборной кампании в США Джона Маккейна, объявившего о намерении выставить свою кандидатуру, вскоре после этого пригласили выступить в Google, чтобы обсудить его политическую платформу. Эрик Шмидт, в тот момент генеральный директор Google, в шутку сказал тогда Маккейну, что баллотироваться на пост президента – примерно то же самое, что и проходить собеседование при приеме на работу в Google. А затем задал ему один из вопросов, которые задают на таком собеседовании: «Как вы определите хорошие способы сортировки одного миллиона 32-битных целых чисел в двух мегабайтах оперативной памяти?» Маккейн смешался, а Шмидт, повеселившись, быстро перешел к следующему вопросу – уже серьезному. Шесть месяцев спустя, когда в прицеле Google оказался Барак Обама, Шмидт задал ему тот же самый вопрос. Обама посмотрел на публику, потер бровь и начал: «Ну, э-э-э…». Чувствуя растерянность Обамы, Шмидт попытался вмешаться, но как раз в этот момент Обама закончил, глядя Шмидту прямо в глаза: «…нет-нет-нет, я думаю, что делать это через “пузырьки” – не лучшая идея», – под гром аплодисментов и одобрительные крики собравшихся компьютерщиков. Неожиданная эрудиция Обамы – шутка «для посвященных» о неэффективности пузырькового алгоритма сортировки – была одним из ключевых элементов его, казалось бы, естественной харизмы (которую на деле обеспечивала тщательная подготовка), отличавшей всю его кампанию и в конце концов приведшей его в Белый дом.

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

Существуют, однако, проблемы, которые просты в изложении, но для их решения может потребоваться астрономическое количество времени. Представьте, что вы работаете в крупной транспортной компании вроде DHL или UPS и за смену вам нужно доставить по разным адресам несколько посылок. Поскольку вам платят по количеству доставленных посылок, а не по времени, которое вы тратите на их доставку, вы хотите найти кратчайший маршрут между всеми пунктами доставки. В этом суть старой и важной математической головоломки – задачи коммивояжера. С ростом количества пунктов доставки сложность выбора оптимального маршрута растет лавинообразно – происходит так называемый комбинаторный взрыв. Вариативность маршрута с добавлением к нему новых локаций растет быстрее экспоненты. Если вы начнете с 30 адресов доставки, то у вас будет 30 вариантов выбора первой точки, 29 – второй, 28 – третьей и так далее. В общей сложности нужно будет проверить 30 × 29 × 28 ×… × 3 × 2 разных маршрута. Итого количество возможных маршрутов с 30 остановками составляет около 265 нониллионов – 265 с 30 нулями. Но на этот раз, в отличие от проблемы сортировки, у вас нет простого решения – практического алгоритма, решающего эту задачу в полиномиальном время, не существует. Проверить правильность решения так же сложно, как и найти его, поскольку проверять необходимо все возможные решения.

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

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

Несмотря на отсутствие общего решения проблемы, для некоторых ее частных случаев (определенного множеств локаций и направлений) точные решения найти можно, хотя это и достаточно сложно. Билл Кук, профессор комбинаторики и оптимизации в Университете Ватерлоо в Онтарио, потратил почти 250 лет компьютерного времени на суперкомпьютере с параллельной архитектурой, вычисляя кратчайший маршрут между всеми пабами Соединенного Королевства. Этот мегазагул предусматривает посещение 49 687 заведений и имеет протяженность всего 40 тысяч миль – в среднем на один паб приходится 0,8 мили. Задолго до того, как Кук начал свои расчеты, Брюс Мастерс из Бедфордшира в Англии решал ту же проблему своим путем – эмпирическим. Ему принадлежит мировой рекорд Гиннесса (самая подходящая книга для такого рекорда) по посещению пабов. К 2014 году 69-летний рекордсмен выпивал в 46 495 различных заведениях. Начиная с 1960 года, по оценкам Брюса, он проехал и прошел более миллиона миль, чтобы посетить все пабы Великобритании – в 25 с лишним раз больше, чем самый эффективный маршрут Билла Кука. Если вы планируете отправиться в подобную одиссею или даже просто собираетесь прошвырнуться по местным пабам, вам, вероятно, стоит для начала свериться с алгоритмом Кука [155] Cook, W. (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press. .