8. Релаксация
Пусть катится
В 2010 году Меган Беллоуз днем работала над докторской диссертацией по химической инженерии в Принстоне, а ночью занималась подготовкой к собственной свадьбе. Ее исследование было посвящено нахождению такого места для размещения аминокислот в белковой цепи, чтобы получилась молекула с определенными характеристиками. («Если вы максимально увеличите энергию связи между двумя белками, тогда вы сможете успешно создать пептидный ингибитор некоторой биологической функции и воспрепятствовать развитию болезни».) В части предсвадебной подготовки она столкнулась с проблемой рассадки гостей.
Среди приглашенных была группа из девяти ее друзей по колледжу, и Беллоуз мучительно пыталась придумать, кого можно добавить в эту воссоединившуюся компанию, чтобы укомплектовать стол на десять человек. В остальном ситуация была еще хуже. Она насчитала одиннадцать близких родственников. Кого пришлось бы выпихнуть из компании, собравшейся за почетным родительским столом, и как все объяснить? А как поступить с соседями со времен детства, няней или родителями коллег по работе, которые и вовсе никого не знают на свадьбе?
Проблема была такой же трудной, как и задача с белковой цепью. Затем ее осенило. Это же была та же задача, над которой она работала в лаборатории. Однажды вечером, рассматривая свою таблицу с рассадкой, «я поняла, что ситуация с рассадкой гостей точь-в-точь напоминала мое исследование об аминокислотах и белках». Беллоуз попросила жениха принести ей лист бумаги и начала записывать уравнения. Аминокислоты стали гостями, энергии связки – отношениями между гостями, а взаимодействие так называемых соседних элементов молекул превратились в соседское взаимодействие. Теперь она могла применить алгоритм из своего исследования в организации собственной свадьбы.
Беллоуз разработала способ количественного выражения силы взаимоотношений между гостями. Если двое не знали друг друга, такие отношения приравнивались к 0, если знали – то к 1, если же они приходили вместе или были парой – то к 50. (Сестра невесты получила возможность поставить 10 тем людям, с которыми она хотела сидеть за одним столом.) Затем Беллоуз установила несколько ограничений: максимальное количество гостей за столом и минимальное количество баллов, необходимое для каждого из столов, чтобы никто не оказался в неудобном положении, чувствуя себя лишним среди девяти незнакомцев. Она также систематизировала цель программы: максимально увеличить баллы взаимоотношений между гостями и их соседями по столу.
На свадьбу были приглашены 107 человек, которые должны были занять свое место за одиннадцатью столами, рассчитанными на десять персон. Это значит, что существует 11 в 107-й степени вариантов рассадки: это 112-значное число, более 200 млрд гуголов, число, затмевающее почти 80-значное количество атомов в обозримой Вселенной. Беллоуз предоставила решение этого вопроса своему лабораторному компьютеру в субботу вечером и оставила его трудиться над «перемешиванием» гостей и вариантов. Когда она вернулась к компьютеру в понедельник утром, он все еще работал над задачей; она остановила выполнение этого задания и вернула его к более привычной работе – над строением белка.
Даже мощный лабораторный компьютер и 36 часов обработки данных не позволили программе оценить и крошечной части возможных вариантов рассадки. Шансы на нахождение одного-единственного оптимального решения, которое получило бы максимальное количество очков, так и не появились. И тем не менее Беллоуз была довольна результатами компьютера. «Он выявил отношения, о которых я и забыла», – сказала Беллоуз, предложив удивительные безусловные возможности, которые даже в голову не пришли бы живым организаторам. Например, компьютер предложил убрать родителей из-за семейного стола и посадить их вместе со старыми друзьями, с которыми они давно не виделись. Рекомендация была просто находкой, по мнению всех сторон, хотя мать невесты все же не удержалась от нескольких манипуляций в ручном режиме.
Тот факт, что вся компьютерная мощь Принстонского университета не смогла найти идеальный план рассадки, может показаться удивительным. В большинстве областей, которые мы ранее обсуждали, четкие алгоритмы могли гарантировать оптимальные решения задач. Но, согласно открытиям специалистов в области информатики, сделанным за несколько последних десятилетий, существуют целые классы задач, в которых найти идеальное решение невозможно вне зависимости от скорости работы наших компьютеров или мастерства программирования. По сути, никто не понимает так отчетливо, как программисты, что перед лицом нерешаемой на первый взгляд задачи не стоит подвергать себя бесконечным мукам поиска решения или же сразу сдаваться, но – как мы видим – стоит попробовать третий вариант.
