И более того, выясняется, что в задаче о коммивояжере минимальное остовное дерево – это одна из лучших стартовых точек, с которой начинаются поиски действительного решения. Этот подход позволяет решить даже самую сложную задачу о коммивояжере, какую только можно себе представить (найти кратчайший маршрут, который пройдет через все города Земли), и решить ее в пределах 0,05 % от (неизвестного) оптимального решения.
Хотя большинство из нас не сталкивались с формальной алгоритмической версией смягчения ограничений, ее основная идея знакома каждому, кто много размышлял над жизненными вопросами. «Что бы вы сделали, если бы не боялись?» – гласит мантра, которую вы не раз могли видеть в кабинете школьного психолога или на семинарах по мотивации. «Что бы вы сделали, если бы знали, что не потерпите неудачу?» Аналогичным образом, когда мы касаемся вопросов профессии и карьеры, мы интересуемся, «что вы сделаете, если выиграете в лотерею?» или, если зайти с другой стороны, «что бы вы делали, если бы все работы оплачивались одинаково?». Смысл этих мысленных упражнений точно такой же, как и в смягчении ограничений: сделать неразрешимое легко решаемым, добиться успеха в идеализированном мире, чтобы потом перенести результат в мир реальный. Если вы не можете решить стоящую перед вами проблему, попробуйте решить ее упрощенную версию и посмотрите, даст ли вам это решение отправную точку, послужит ли маяком для работы с полномасштабной проблемой. Возможно, что да.
Чего релаксация сделать не может, так это дать гарантированный доступ к идеальному решению. Но компьютерная наука может количественно выразить компромисс между потраченным временем и качеством решения, который предлагает релаксация. Во многих случаях этот коэффициент грандиозен, немыслим (например, ответ, который наполовину так же хорош, как идеальное решение, полученный в одну квадриллионную времени, требующегося для получения идеального решения). Идея простая, но глубокая: если мы готовы принять решения, которые достаточно близки, то даже самые заковыристые проблемы можно решить с помощью правильных методов.
Временное снятие ограничений, как в минимальном остовном дереве и в вопросе «что, если вы выиграете в лотерею?», является наиболее исчерпывающей и понятной формой алгоритмической релаксации. Но есть еще и два других, более трудноуловимых вида релаксации, которые неоднократно возникают в исследованиях оптимизации. Они доказали свою важную роль в решении некоторых неразрешимых проблем в этой сфере, напрямую влияя на ситуации в реальной жизни – от градостроительства и борьбы с болезнями до планирования спортивных соревнований.
Бесчисленное множество оттенков серого: непрерывная релаксация
Проблема коммивояжера и задача Меган Беллоуз по поиску лучшего плана рассадки – особый вид задач оптимизации, известный также как дискретная оптимизация – то есть задача, не имеющая бескрайнего множества решений. Коммивояжер едет либо в этот город, либо в тот; вы сидите или за пятым столиком, или за шестым. Только два варианта и никаких оттенков серого!
Подобных задач дискретной оптимизации вокруг полно. В городах, например, проектировщики стараются расположить пожарные машины так, чтобы доехать до каждого дома за определенный отрезок времени, скажем за пять минут. С математической точки зрения каждая пожарная машина «охватывает» все дома в округе, до которых можно добраться от исходной точки в течение пяти минут. Задача заключается в том, чтобы найти минимальное количество локаций, охватывающих все дома. «Представители этой профессии [пожарные и спасатели] только что перешли на такую модель покрытия, и это здорово, – говорит Лора Альберт Маклей из Висконсинского университета в Мэдисоне. – Это то, что легко смоделировать». Но так как пожарная машина либо стоит в указанном месте, либо нет, то попытки рассчитать этот минимальный набор вариантов включают дискретную оптимизацию. И, как замечает Маклей, «это та точка, начиная с которой большинство задач становятся трудными в вычислительном отношении, потому что невозможно сделать половину того и половину этого».
Задачи дискретной оптимизации проявляются также и в социальной жизни. Представьте, что вы хотите устроить вечеринку для всех своих друзей и знакомых, но совершенно не хотите платить за кучу конвертов и марок для рассылки приглашений. Вместо этого вы могли бы разослать приглашения своим самым общительным друзьям с просьбой «приводить всех, кого мы с тобой знаем». То, чего вам в идеале хотелось бы, – это иметь небольшую группу друзей, которые знакомы со всеми остальными представителями вашего социального круга, что позволило бы вам облизать минимальное количество марок и собрать при этом максимальное количество присутствующих. Правда, со стороны это может выглядеть как дополнительная куча работы ради экономии пары баксов на марках, но это именно та задача, которую руководители политических кампаний и корпоративные маркетологи хотят решить, чтобы доносить свои сообщения наиболее эффективно. И это также задача, над которой начали задумываться эпидемиологи: какое минимальное количество населения – и кого именно – нужно вакцинировать, чтобы защитить общество от инфекционных заболеваний.
Как мы уже отмечали, приверженность к целым числам и делает задачи по дискретной оптимизации столь сложными для решения: пожарный департамент может иметь в гараже одну машину, или две, или три, но не две с половиной или π машин. На самом деле и задача с пожарными расчетами, и задача с приглашениями на вечеринку – неподдающиеся: для них не существует никакого общего эффективного решения. Но, как выясняется, существует ряд успешно работающих стратегий для решения подобных проблем, где каждая частица или десятая доля и есть возможное решение. Исследователи, столкнувшиеся с задачей дискретной оптимизации, порой с завистью смотрят на эти стратегии. Но они могут сделать кое-что большее! А именно – перевести эту задачу из ряда дискретных в непрерывные и посмотреть, что будет.
В случае задачи с приглашениями перевод из дискретной в непрерывную оптимизацию означает, что решение может быть таким: послать одному гостю четвертинку приглашения, а другому две трети. Что это вообще значит? Очевидно же, что это не ответ на поставленный вопрос, но, как и минимальное остовное дерево, это дает нам точку, откуда начинать. С мягким решением в руках мы можем привести эти дробные части ближе к реалиям. Мы можем, например, просто округлить их, посылая приглашение каждому, кому по ослабленному сценарию досталась половина приглашения или больше. Или же мы можем интерпретировать их как вероятности (например, подбрасывать монетку в каждой локации, где мягкое решение предлагает нам поставить половину пожарной машины, и размещать там реальный расчет, только если выпадет орел). В любом случае, приводя эти дроби к целым числам, мы получим решение, которое подойдет нам в контексте нашей исходной, дискретной задачи. Последним этапом, как в любой релаксации, будет вопрос, настолько ли хорошо полученное нами решение в сравнении с фактически лучшим решением, которое мы могли бы получить, если бы тщательно изучали каждый возможный ответ для исходной задачи. Оказывается, что в задаче с приглашениями непрерывная релаксация с округлением даст нам довольно неплохое легко вычисляемое решение: математика гарантирует, что к вам на вечеринку придут все, кого вы хотите видеть, если вы разошлете как минимум в два раза больше приглашений, чем вам предложит решение, полученное методом перебора. Аналогично, в задаче про пожарные расчеты непрерывная релаксация с вероятностями быстро подведет нас к удобным границам оптимального решения.
