и трижды делали y». Они: «О, ну ладно, что ж. Тогда мы ни за что не будем делать z». И мы возвращаемся еще на год назад… В целом мы понимаем: они думают, что есть что-то, чего они никогда не будут делать и что делают другие. В бейсболе принято считать, что The Yankees и The Mets никогда не играют домашних матчей в одно и то же время. Но это неправда. И никогда не было правдой. Они проводят как минимум три, а то и шесть домашних матчей за год в один и тот же день. Но для всего сезона в целом 81 домашний матч для каждой команды – это довольно мало. Неудивительно, что люди забывают о них.
Порой приходится прибегать к дипломатическим тонкостям, но Лагранжева релаксация – территория, где запрещенное становится наказуемым, а немыслимое нежелательным, – позволяет добиться прогресса. Как говорит Трик, вместо того чтобы тратить миллиарды лет на поиски несуществующего идеального решения, лучше использовать метод Лагранжевой релаксации и позволить себе задать вопрос наподобие: «Как близко вы можете подобраться к такому решению?» Как выясняется, достаточно близко, чтобы сделать счастливым каждого – лиги, школы, телеканалы – и разжигать огонь March Madness год за годом.
Проблемы оптимизации (с одной стороны – цели, с другой стороны – правила), возможно, самый распространенный вид вычислительных задач, с которыми мы имеем дело. И задачи дискретной оптимизации, где наши варианты сводятся к строгому выбору «или/или» без каких-либо средних значений, – наиболее типичные из них. Здесь информатика выносит обескураживающий вердикт. Многие проблемы дискретной оптимизации действительно сложны. Самые светлые головы этой области пасовали в попытках найти короткий путь к идеальным решениям, посвящая гораздо больше времени доказательствам того, что таких путей не существует, чем поиску оных.
Во всяком случае, это должно нас немного утешить. Если мы сталкиваемся лицом к лицу с задачей, которая кажется нескладной, тернистой, нерешаемой, то мы, вероятно, правы. И наличие компьютера далеко не всегда может помочь.
По крайней мере до тех пор, пока мы не научимся релаксировать.
Существует много способов ослабить проблему, и мы рассмотрели три наиболее важных. Первый из них – вынужденная релаксация – просто убирает некоторые ограничения в целом и достигает прогресса за счет уменьшения строгости задачи, прежде чем возвращается к реальности. Второй – непрерывная релаксация – превращает дискретный или бинарный выбор в бесконечное множество: прежде чем выбрать между холодным чаем и лимонадом, представьте себе напиток Арнольда Палмера