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

И более того, выясняется, что в задаче о коммивояжере минимальное остовное дерево – это одна из лучших стартовых точек, с которой начинаются поиски действительного решения. Этот подход позволяет решить даже самую сложную задачу о коммивояжере, какую только можно себе представить (найти кратчайший маршрут, который пройдет через все города Земли), и решить ее в пределах 0,05 % от (неизвестного) оптимального решения.

Хотя большинство из нас не сталкивались с формальной алгоритмической версией смягчения ограничений, ее основная идея знакома каждому, кто много размышлял над жизненными вопросами. «Что бы вы сделали, если бы не боялись?» – гласит мантра, которую вы не раз могли видеть в кабинете школьного психолога или на семинарах по мотивации. «Что бы вы сделали, если бы знали, что не потерпите неудачу?» Аналогичным образом, когда мы касаемся вопросов профессии и карьеры, мы интересуемся, «что вы сделаете, если выиграете в лотерею?» или, если зайти с другой стороны, «что бы вы делали, если бы все работы оплачивались одинаково?». Смысл этих мысленных упражнений точно такой же, как и в смягчении ограничений: сделать неразрешимое легко решаемым, добиться успеха в идеализированном мире, чтобы потом перенести результат в мир реальный. Если вы не можете решить стоящую перед вами проблему, попробуйте решить ее упрощенную версию и посмотрите, даст ли вам это решение отправную точку, послужит ли маяком для работы с полномасштабной проблемой. Возможно, что да.

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

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

Бесчисленное множество оттенков серого: непрерывная релаксация

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

Подобных задач дискретной оптимизации вокруг полно. В городах, например, проектировщики стараются расположить пожарные машины так, чтобы доехать до каждого дома за определенный отрезок времени, скажем за пять минут. С математической точки зрения каждая пожарная машина «охватывает» все дома в округе, до которых можно добраться от исходной точки в течение пяти минут. Задача заключается в том, чтобы найти минимальное количество локаций, охватывающих все дома. «Представители этой профессии [пожарные и спасатели] только что перешли на такую модель покрытия, и это здорово, – говорит Лора Альберт Маклей из Висконсинского университета в Мэдисоне. – Это то, что легко смоделировать». Но так как пожарная машина либо стоит в указанном месте, либо нет, то попытки рассчитать этот минимальный набор вариантов включают дискретную оптимизацию. И, как замечает Маклей, «это та точка, начиная с которой большинство задач становятся трудными в вычислительном отношении, потому что невозможно сделать половину того и половину этого».

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