Алгоритмы для жизни: Простые способы принимать верные решения - [79]

Беллоуз разработала способ количественного выражения силы взаимоотношений между гостями. Если двое не знали друг друга, такие отношения приравнивались к 0, если знали – то к 1, если же они приходили вместе или были парой – то к 50. (Сестра невесты получила возможность поставить 10 тем людям, с которыми она хотела сидеть за одним столом.) Затем Беллоуз установила несколько ограничений: максимальное количество гостей за столом и минимальное количество баллов, необходимое для каждого из столов, чтобы никто не оказался в неудобном положении, чувствуя себя лишним среди девяти незнакомцев. Она также систематизировала цель программы: максимально увеличить баллы взаимоотношений между гостями и их соседями по столу.

На свадьбу были приглашены 107 человек, которые должны были занять свое место за одиннадцатью столами, рассчитанными на десять персон. Это значит, что существует 11 в 107-й степени вариантов рассадки: это 112-значное число, более 200 млрд гуголов, число, затмевающее почти 80-значное количество атомов в обозримой Вселенной. Беллоуз предоставила решение этого вопроса своему лабораторному компьютеру в субботу вечером и оставила его трудиться над «перемешиванием» гостей и вариантов. Когда она вернулась к компьютеру в понедельник утром, он все еще работал над задачей; она остановила выполнение этого задания и вернула его к более привычной работе – над строением белка.

Даже мощный лабораторный компьютер и 36 часов обработки данных не позволили программе оценить и крошечной части возможных вариантов рассадки. Шансы на нахождение одного-единственного оптимального решения, которое получило бы максимальное количество очков, так и не появились. И тем не менее Беллоуз была довольна результатами компьютера. «Он выявил отношения, о которых я и забыла», – сказала Беллоуз, предложив удивительные безусловные возможности, которые даже в голову не пришли бы живым организаторам. Например, компьютер предложил убрать родителей из-за семейного стола и посадить их вместе со старыми друзьями, с которыми они давно не виделись. Рекомендация была просто находкой, по мнению всех сторон, хотя мать невесты все же не удержалась от нескольких манипуляций в ручном режиме.

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

Сложность оптимизации

Прежде чем вести страну через Гражданскую войну, до составления Манифеста об освобождении рабов и произнесения Геттисбергской речи, Авраам Линкольн работал адвокатом прерии в Спрингфилде, штат Иллинойс, и путешествовал по Восьмому судебному округу дважды в год на протяжении 16 лет. Служить окружным юристом действительно означало делать своеобразный круг – колесить по городам четырнадцати разных округов, проводя судебные разбирательства. Спланировать такую поездку представляло собой настоящую задачу: как посетить все нужные города, проехав как можно меньшее расстояние и не заезжая в один и тот же город дважды.

Это пример известной математикам и программистам задачи по оптимизации с заданными ограничениями: как найти единственный лучший вариант с рядом переменных при определенных заданных правилах и системе ведения счета. По сути, это самая известная задача по оптимизации из всех. Если бы ее изучали в XIX веке, она наверняка получила бы название «задача адвоката прерий», а если бы с ней впервые столкнулись в XX веке, то ее окрестили бы задачей по перемещениям беспилотника. Но, так же как и задача о секретаре, она появилась в середине XХ века под названием «задача о коммивояжере».

Задача о планировании маршрута не привлекала внимание математического сообщества до 1930-х годов, но, когда это случилось, задача была отомщена. Математик Карл Менгер упоминал о задаче почтового служащего в 1930 году, отмечая, что не существует более простого из известных решений, кроме как испытывать каждую возможность по очереди. Хасслер Уитни из Принстона обозначил эту проблему в 1934 году, тогда она и засела плотно в уме его друга математика Меррила Флада (который, как вы помните из главы 1, причастен к распространению первого решения задачи о секретаре). Когда Флад переехал в Калифорнию в 40-е годы, он передал эту задачу своим коллегам в Институте Айн Рэнд. Каноническое название задачи впервые было упомянуто в газетной публикации в 1949 году благодаря математику Джулии Робинсон. По мере обсуждения задачи в математических кругах она постепенно приобрела печальную известность. Множество величайших умов были ею одержимы, но никто, казалось, даже не начал двигаться в верном направлении, решая ее.