Методы физики применили в решении проблем логистики

Ученые из Бостонского университета и Университета Центральной Флориды попробовали использовать методы статистической механики для решения задач, требующих объемных вычислений. О том, что из этого вышло, они рассказали в журнале Nature Communications.

Статистическая механика применяется для описания состояния твердых тел, жидкостей и газов, ее используют также для изучения таких явлений, как магнетизм и сверхпроводимость. Однако методы, разработанные в рамках этой области физики, иногда применяют в исследованиях уличного движения, нейронных сетей, лавин и даже колебаний на фондовой бирже.

Ранее уже предпринимались попытки использования статистической механики для решения вычислительных задач. В рамках этого подхода задача формулируется как граф с бинарными значениями переменных в узлах. Решением искомой проблемы является состояние графа с наименьшей энергией. Проблемой этого подхода является наличие фазовых переходов, похожих на переход жидкость — стеклообразное вещество, порождающих много состояний с низкой энергией.

Авторы исследования придумали статистическую модель, лишенную объемных фазовых переходов. Они предложили использовать для вычислений двумерную сетку, в которой каждая вершина соответствует логическому вентилю, соединенному с четырьмя соседними. Данные на вход и на выход поставляются на границы решетки.

«Мы подаем энергию на каждый из логических вентилей. Мы спроектировали это таким образом, чтобы каждый раз, когда на нем получается единица, энергия очень мала, следовательно, когда единицы на всех вентилях, общая энергия системы должна быть очень низкой», — рассказал один из авторов работы, профессор Университета Центральной Флориды Эдуардо Муччоло. Достижение наименьшей энергии системы обозначает найденное решение.

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