Алгоритмы для жизни: Простые способы принимать верные решения - [90]
По словам Миценмахера, «идея ошибочного компромисса пространства – думаю, основная проблема в том, что люди не связывают это с вычислениями. Они полагают, что компьютер должен просто выдать ответ. Поэтому, когда на лекции, посвященной алгоритмам, вы слышите: "У вас должен получиться один ответ; но этот ответ может быть неправильным", – мне нравится думать, что это заставляет их [студентов] собраться. Думаю, люди просто не осознают, насколько часто они сталкиваются с этим в своей жизни, и не могут принять это».
Холмы, долины и ловушки
Река извивается, потому что она не умеет думать.
Ричард Кенни
Случайность также зарекомендовала себя как мощное оружие в борьбе с проблемами дискретной оптимизации, такими как создание расписания баскетбольных матчей NCAA или поиск кратчайшего маршрута для коммивояжера. В предыдущей главе мы увидели, как релаксация помогает снизить количество подобных проблем, но тактическое использование случайности стало, возможно, даже более значимым способом.
Представьте себе, что вы планируете путешествовать по миру и посетить десять городов. Ваша собственная версия проблемы коммивояжера: вы улетаете и прилетаете в Сан-Франциско и планируете побывать в Сиэтле, Лос-Анджелесе, Нью-Йорке, Буэнос-Айресе, Лондоне, Амстердаме, Копенгагене, Стамбуле, Дели и Киото. Вас не слишком волнует общая протяженность маршрута, но вы, вероятно, стремитесь снизить расходы на поездку. Первое, что стоит здесь отметить: хотя десять городов – это не так уж и много, но количество возможных вариантов маршрута – это 10! (10 факториал) – более 3,5 млн. Иными словами, у вас нет никакой практической возможности проверить каждую комбинацию и выбрать самую низкую цену. Придется получше пораскинуть мозгами.
В качестве первой попытки построить маршрут вы можете рассмотреть самый дешевый рейс из Сан-Франциско (скажем, в Сиэтл), а затем найти самый дешевый рейс оттуда в любой из оставшихся городов (пусть это будет Лос-Анджелес), потом самый дешевый оттуда (например, в Нью-Йорк) и т. д., пока вы не дойдете до десятого города, откуда вам нужно будет лететь обратно в Сан-Франциско. Это пример так называемого жадного алгоритма, который можно еще назвать близоруким: на каждом этапе пути он близоруко выбирает лучший вариант из тех, что под рукой. В теории планирования, которую мы рассмотрели в главе 5, жадный алгоритм – например, выполнение самой простой и занимающей меньше всего времени работы из доступных, не заглядывая далеко вперед, – порой может стать именно тем, что требуется для решения проблемы. В этом случае решение проблемы коммивояжера, которое может предложить жадный алгоритм, не самое плохое, но далекое от лучшего из возможных.
После того как вы построили базовый маршрут, вам стоит проверить возможные альтернативы, меняя последовательность городов, и посмотреть, получается ли лучше. Например, если мы решили сперва лететь в Сиэтл, а потом в Лос-Анджелес, можно попробовать поменять их местами: сначала Лос-Анджелес, затем Сиэтл. Для любого заданного маршрута мы, таким образом, можем переставить местами два города 11 раз. Скажем, мы перепробуем все варианты и выберем тот, который позволит нам максимально сэкономить. С этого момента у нас есть новый построенный маршрут, с которым мы будем работать дальше, и мы можем снова заняться перестановкой, чтобы извлечь какие-то дополнительные выгоды. Этот алгоритм называется «восхождение на холм», поскольку поиск лучших и худших решений среди множества вариантов можно рассматривать как путешествие по холмистой местности с целью взобраться на самую высокую гору.
В конечном итоге вы найдете наилучшее решение из всех возможных перестановок. И не важно, какие соседние города вы меняете местами: оно останется таковым. Именно здесь заканчивается ваше восхождение на холм. Означает ли это, что вы нашли единственно возможный наилучший маршрут? К сожалению, нет. Вы могли найти только так называемый локальный максимум, но не глобальный максимум всех вероятностей. Холмистый ландшафт к тому же окутан туманом. Вы можете сделать вывод, что стоите на вершине холма, только на основе того факта, что вокруг вас видны уходящие вниз склоны. Но, возможно, за долиной есть гора и повыше, скрытая за облаками.
Представьте себе лобстера, застрявшего в ловушке: бедное животное не понимает, что для того, чтобы выбраться, ему нужно вернуться к центру клетки, то есть забраться в нее поглубже. Ловушка для лобстеров не что иное, как локальный максимум из проволоки – локальный максимум, который убивает.
