Компьютерное моделирование физических явлений. Малютин В.М - 151 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

8.5 Другие применения модели Изинга
8.5.1. Задача о коммивояжере
Алгоритм, сходный с алгоритмом Метрополиса, может быть
использован в достаточно неожиданной области — в задаче поиска
кратчайшего пути на графе. Эта задача называется задачей о бродячем
торговце (задачей о коробейнике, задачей о коммивояжере).
Пусть имеется n городов. Некоторые из них связаны между собой
дорогами различной длины. Бродячий торговец хотел бы посетить все
эти города по одному разу, пройдя при этом наименьшее расстояние.
Точно задача может быть решена методом полного перебора, что
приводит к колоссальному объему вычислений в реальных задачах. А
задачи такие возникают очень часто, особенно на транспорте. В то же
самое время можно найти решение, близкое к оптимальному, использую
метод Монте-Карло.
Обозначим через а некоторую последовательность посещения
городов, а через L(a) — соответствующую этой последовательности
длину пути. Мы хотим найти такую последовательность а, при которой
длина пути была бы минимальной. Будем применять для этой цели
алгоритм Метрополиса, с той лишь разницей, что мы вместо переворота
спинов будем менять последовательность посещения городов. Тогда
второй пункт алгоритма Метрополиса будет звучать примерно так: «В
заданной последовательности посещения городов случайным образом
выбираем два города и меняем их местами». Роль энергии в этом случае
будет играть длина пути. Но что же такое в этом случае температура?
Температура — это некоторый управляющий параметр. Первоначально
он выбирается достаточно большим, а затем медленно понижается. Если
при дальнейшем понижении температуры длина пути перестает
меняться, то значит, минимум достигнут.
Понятно, что при малом числе городов трудоемкость метода
будет чрезвычайно большой. В то же время, поскольку трудоемкость
обычных методов растет экспоненциально с ростом системы, этот метод
становится весьма эффективным именно для больших систем.
8.5.2. Распознавание образов
Удивительное и неожиданное применение модели Изинга связано
с задачами распознавания образов. Такое применение модели
предложил в 1982 г. Хопфилд. Оказалось, что ферромагнитная модель
Изинга имеет много общих черт с ассоциативной памятью, то есть
151

Страницы