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

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

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

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

Штраф за превышение скорости: Лагранжева релаксация

Виззини: Непостижимо.

Иниго Монтойя: Ты постоянно используешь это слово. Не думаю, что оно означает то, что ты думаешь, что оно означает.

Фильм «Принцесса-невеста»

Однажды в детстве Брайан полдня жаловался матери на все, что ему приходилось делать: уроки, работу по дому… «С юридической точки зрения ты не обязан ничего делать, – ответила ему мать. – Ты не обязан слушаться учителей. Ты не обязан слушаться меня. Ты не обязан даже подчиняться закону. Но у любого поступка есть последствия, и только тебе решать, когда ты захочешь с этими последствиями столкнуться».

Детский мозг Брайана взорвался. Это был мощный посыл, пробуждающий ощущение силы, ответственность, моральные суждения. Но было это также и кое-что другое: эффективная методика вычислений под названием Лагранжева релаксация. Идея Лагранжевой релаксации проста. Задача оптимизации состоит из двух частей: правила и оценка производительности. В рамках Лагранжевой релаксации мы берем некоторые из ограничивающих условий задачи и внедряем их в систему количественных показателей. Таким образом, мы превращаем невозможное в затратное. (В задаче со свадебной рассадкой, к примеру, мы можем убрать ограничение, что за каждым столом может сидеть максимум 10 человек, и допустить «перенаселение» за столами с вероятностью слегка потолкаться локтями.) Когда условие задачи оптимизации гласит «Делай только так, а не то…», Лагранжева релаксация вопрошает: «А не то что?» Однажды мы позволяем себе выйти за границы (хотя бы чуть-чуть, пусть даже за счет высоких расходов) – и вот уже задачи становятся разрешимыми.

Лагранжевы релаксации занимают огромную часть во всей теоретической литературе, посвященной задаче коммивояжера и другим сложным задачам в области информатики. Кроме того, они служат важным инструментом для ряда практических случаев. Вспомним, к примеру, Майкла Трика из Университета Карнеги – Меллон, который, как мы помним из главы 3, отвечал за расписание Главной лиги бейсбола и ряд конференций Национальной ассоциации студенческого спорта. О чем мы не упоминали, так это о том, как он это делает. Составление расписания на каждый год представляет собой гигантскую задачу дискретной оптимизации, слишком сложную для того, чтобы компьютер мог решить ее методом перебора. Поэтому каждый год Трик и его коллеги из группы спортивного планирования прибегают к помощи Лагранжевой релаксации. Каждый раз, когда вы включаете телевизор или занимаете место на трибуне стадиона, помните, благодаря чему состоялась встреча этих двух команд на этой площадке в этот конкретный вечер. Ну хорошо, необязательно это будет оптимальный спортивный матч. Но близко к тому. И поблагодарить за это нам стоит не только Майкла Трика, но и французского математика XVIII века Жозефа Луи Лагранжа.