Но есть еще и третий способ: вместо того чтобы полностью положиться на волю случая, когда ты зашел в тупик, прибегайте к помощи случайности в каких-то мелочах каждый раз, когда принимаете решение. Эта техника, придуманная все той же командой из Лос-Аламоса, которая разработала метод Монте-Карло, получила название «алгоритм Метрополиса». Алгоритм Метрополиса, так же как и «восхождение на холм», работает за счет мелких перестановок в решении, но с одним большим отличием: в любой заданной точке он может принять плохие перестановки наравне с хорошими.
Давайте попробуем применить этот метод к планированию нашего отпуска. Мы снова попробуем скорректировать маршрут, меняя местами разные города. Если получившаяся случайным образом перестановка приводит к улучшению маршрута, мы принимаем ее и продолжаем процесс дальше с этой точки. Но, если изменение приводит к небольшому ухудшению, все равно остается шанс, что мы примем его (хотя чем хуже изменение, тем меньше этот шанс). Таким образом, мы не застреваем в одном локальном максимуме надолго: в конце концов, мы испробуем другое решение, пусть это и окажется немного дороже, и продолжим нашу работу по созданию нового и лучшего плана.
Не важно, будет ли это «дрожание», случайный перезапуск или готовность к временному ухудшению, случайность остается невероятно полезным способом избегать локальных максимумов. Шанс – это не только конкурентоспособный метод решения жестких проблем оптимизации; во многих случаях он играет решающую роль. Но некоторые вопросы еще остаются открытыми. Какой процент случайности нужно использовать? И когда? И – учитывая, что такие стратегии, как алгоритм Метрополиса, могут менять наш маршрут до бесконечности, – как вообще понять, что можно заканчивать? Окончательный ответ на эти вопросы немедленно даст исследователям, работающим над вопросом оптимизации, новую пищу для размышлений.
В конце 1970-х – начале 1980-х годов Скотт Киркпатрик считался физиком, а не специалистом в области информатики. В частности, его интересовала статистическая физика, в которой случайностью объяснялись некоторые явления природы, например физика отжига – то, как материалы меняют свое состояние в процессе нагрева или охлаждения. Пожалуй, самой интересной характеристикой отжига является скорость охлаждения вещества, которая оказывает огромное влияние на его конечную структуру. Как писал Киркпатрик:
Выращивание монокристалла из расплава происходит путем аккуратного отжига, когда вещество сперва расплавляют, а затем медленно понижают температуру, долгое время удерживая ее в области точки замерзания. Если этого не сделать и позволить веществу выйти из равновесного состояния, то у полученного кристалла будет множество дефектов или вещество вовсе превратится в стекло без какой-либо кристаллической структуры.