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

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

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

Как мы уже отмечали, приверженность к целым числам и делает задачи по дискретной оптимизации столь сложными для решения: пожарный департамент может иметь в гараже одну машину, или две, или три, но не две с половиной или π машин. На самом деле и задача с пожарными расчетами, и задача с приглашениями на вечеринку – неподдающиеся: для них не существует никакого общего эффективного решения. Но, как выясняется, существует ряд успешно работающих стратегий для решения подобных проблем, где каждая частица или десятая доля и есть возможное решение. Исследователи, столкнувшиеся с задачей дискретной оптимизации, порой с завистью смотрят на эти стратегии. Но они могут сделать кое-что большее! А именно – перевести эту задачу из ряда дискретных в непрерывные и посмотреть, что будет.

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

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