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

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

Тем не менее надо же как-то справиться со сложностью задачи. Таким образом, «нам приходится работать с лигами, чтобы ослабить некоторые из ограничений, которые могут у них быть», – объясняет Трик. Число таких ограничений при планировании спортивного сезона поистине огромно, и оно включает в себя не только требования, проистекающие из базовой структуры лиги, но и всякого рода специфические запросы и сомнения. Некоторые лиги хотят играть только во второй половине сезона и только в домашних, а не выездных матчах. Другие лиги это категорически не устраивает, но они тем не менее требуют, чтобы команды не играли вместе снова, пока не сыграют со всеми остальными по разу. Некоторые настаивают, чтобы противостояние знаменитых команд имело место в финальной игре сезона. Некоторые команды не могут играть домашние матчи в определенные дни, потому что в эти даты арены уже заняты под другие мероприятия. В случае с баскетбольными играми Национальной ассоциации студенческого спорта Трику пришлось также принять во внимание требования телевизионных каналов, транслирующих игры. Телеканалы за год предугадывают, какие из матчей станут «А-играми» и «В-играми», то есть играми, которые привлекут наибольшую аудиторию (матч Duke против UNC, например, уже много лет является А-игрой). Каналы, таким образом, планируют одну А-игру и одну В-игру в неделю, но ни в коем случае не одновременно, чтобы не расколоть зрительскую аудиторию.

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

Как правило, когда люди приходят к нам со спортивным расписанием, они начинают качать права… «Мы никогда не будем делать x и никогда не будем делать y!» Тогда мы смотрим на их расписание и говорим: «Ну, в прошлом году вы дважды делали x и трижды делали y». Они: «О, ну ладно, что ж. Тогда мы ни за что не будем делать z». И мы возвращаемся еще на год назад… В целом мы понимаем: они думают, что есть что-то, чего они никогда не будут делать и что делают другие. В бейсболе принято считать, что The Yankees и The Mets никогда не играют домашних матчей в одно и то же время. Но это неправда. И никогда не было правдой. Они проводят как минимум три, а то и шесть домашних матчей за год в один и тот же день. Но для всего сезона в целом 81 домашний матч для каждой команды – это довольно мало. Неудивительно, что люди забывают о них.

Порой приходится прибегать к дипломатическим тонкостям, но Лагранжева релаксация – территория, где запрещенное становится наказуемым, а немыслимое нежелательным, – позволяет добиться прогресса. Как говорит Трик, вместо того чтобы тратить миллиарды лет на поиски несуществующего идеального решения, лучше использовать метод Лагранжевой релаксации и позволить себе задать вопрос наподобие: «Как близко вы можете подобраться к такому решению?» Как выясняется, достаточно близко, чтобы сделать счастливым каждого – лиги, школы, телеканалы – и разжигать огонь March Madness год за годом.

Учимся релаксации

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

Во всяком случае, это должно нас немного утешить. Если мы сталкиваемся лицом к лицу с задачей, которая кажется нескладной, тернистой, нерешаемой, то мы, вероятно, правы. И наличие компьютера далеко не всегда может помочь.

По крайней мере до тех пор, пока мы не научимся релаксировать.

Существует много способов ослабить проблему, и мы рассмотрели три наиболее важных. Первый из них – вынужденная релаксация – просто убирает некоторые ограничения в целом и достигает прогресса за счет уменьшения строгости задачи, прежде чем возвращается к реальности. Второй – непрерывная релаксация – превращает дискретный или бинарный выбор в бесконечное множество: прежде чем выбрать между холодным чаем и лимонадом, представьте себе напиток Арнольда Палмера