Киркпатрик в то время работал в компании IBM, где самой сложной и важной проблемой было нанесение электросхем на чипы, производимые компанией. Проблема была громоздкой и труднорешаемой: существовало множество путей решения, и при этом имелись некоторые сложные ограничения. Так, например, в общем и целом стоило располагать элементы близко друг к другу, но не слишком, чтобы оставалось место для соединения. И каждый раз, как что-то сдвигалось, приходилось по новой рассчитывать, как все соединения будут работать при гипотетическом новом расположении.
В те времена процессом руководил своего рода тайный гуру компании IBM. Киркпатрик вспоминает: «Тот парень мог напихать на чип больше всего микросхем… и у него был весьма загадочный способ объяснять, что он делает. Он реально не любил об этом рассказывать».
Друг и коллега Киркпатрика Дэн Гелатт проявил живой интерес к этой проблеме и увлек ею и самого Скотта, с которым случилось внезапное прозрение. «Способ изучения [физических систем] заключался в том, чтобы нагреть их, затем охладить и дать системе возможность самоорганизоваться. С данной точки зрения, это выглядело совершенно естественным способом решения всех типов проблем оптимизации, как если бы количество степеней свободы, которые вы пытаетесь организовать, были бы маленькими атомами, спинами или чем там еще».
В физике то, что мы называем температурой, на самом деле является скоростью – хаотичное движение частиц на молекулярном уровне. Это очень похоже, рассуждал Киркпатрик, на хаотичное «дрожание», которое может применяться вместе с алгоритмом восхождения на холм, чтобы иногда отказываться от лучших решений в пользу худших. На самом деле алгоритм Метрополиса был изначально создан, чтобы моделировать хаотичное поведение частиц в физических системах (конкретно в том случае моделировались ядерные взрывы). И что же случится, вопрошал Киркпатрик, если вы попробуете решить проблему оптимизации как проблему отжига – сперва «нагреете» ее, а затем медленно «охладите»?
Возвращаясь к задачке с десятью городами, мы могли бы начать с «высокой температуры», выстраивая первый маршрут полностью случайным образом, выбирая один из множества возможных вариантов решения независимо от цены. После этого мы можем медленно «остужать» наши поиски, бросая кубик каждый раз, когда рассматриваем изменение последовательности посещения городов. Выбор лучших вариантов всегда обоснован, но мы будем выбирать худшие, когда нам выпадает, скажем, два очка или больше. Через какое-то время мы еще немного «снизим температуру», выбирая более дорогие варианты, если на кубике выпадет 3 или больше – а потом 4, а потом 5. В конечном итоге мы практически взойдем на холм, отступая назад только иногда, когда выпадет 6. Наконец мы начали бы идти только в гору и остановились бы, достигнув следующего локального максимума.