Алгоритмы для жизни: Простые способы принимать верные решения (Гриффитс, Кристиан) - страница 170

В конечном итоге вы найдете наилучшее решение из всех возможных перестановок. И не важно, какие соседние города вы меняете местами: оно останется таковым. Именно здесь заканчивается ваше восхождение на холм. Означает ли это, что вы нашли единственно возможный наилучший маршрут? К сожалению, нет. Вы могли найти только так называемый локальный максимум, но не глобальный максимум всех вероятностей. Холмистый ландшафт к тому же окутан туманом. Вы можете сделать вывод, что стоите на вершине холма, только на основе того факта, что вокруг вас видны уходящие вниз склоны. Но, возможно, за долиной есть гора и повыше, скрытая за облаками.

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

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

Один из таких способов – улучшить ваше восхождение на холм с помощью того, что называется «дрожание»: если вы чувствуете, что застряли на месте, попробуйте немного перемешать все планы. Внесите несколько случайных незначительных изменений (даже если они будут к худшему), а затем снова вернитесь к восхождению на холм. Возможно, вы очутитесь на более высокой вершине.

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