Современным компьютерам по-прежнему не хватает способностей и возможностей, чтобы отыскать лучшее решение классической задачи коммивояжёра, которая заключается в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. И даже нахождение приблизительных решений является достаточно трудной задачей для классческих машин. Она может показаться простой, но количество возможных маршрутов возрастает очень быстро по мере добавления городов. Вот почему эту головоломку так трудно решить.
Между тем поиск кратчайших путей решения задачи коммивояжёра не просто академическое упражнение: это класс проблем, которые лежат в основе реальных бизнес-задач, начиная от планирования маршрутов доставки грузов, заканчивая открытиями новых фармацевтических препаратов (например, нужно подключить похожее решение, чтобы определить, как сворачиваются белки).
Сегодня компьютеры решают проблемы комбинаторной оптимизации, пропуская некоторые неэффективные решения вместо рассмотрения всех возможностей, чтобы найти наилучшее. Но американские и японские специалисты отдельно друг от друга работают над новым специализированным компьютером – "машиной Изинга" (о причинах названия расскажем позднее).
Компьютер однажды поможет решить задачи коммивояжёра и подобные проблемы более эффективным образом, считают специалисты. Их гибридная машина сочетает в себе цифровые электронные схемы и оптические приборы, похожие на лазеры.
"Самый простой способ решения задачи коммивояжера – рассмотреть все возможные пути, но не так, как это делает обыкновенный компьютер. Если вы попытаетесь решить такую задачу с помощью ноутбука, он не проанализирует все пути, поскольку неспособен на решение задач такого объёма", — говорит Питер Макмахон (Peter McMahon), физик из Стэнфордского университета.
Новый компьютер, разрабатываемый учёными, нацелен на решения задач оптимизации на основе математического подхода, известного как модель Изинга. Эта математическая модель предназначена для описания намагничивания материала.
В физической модели Изинга каждому узлу кристаллической решётки соответствует определённое значение, называемое спином и численно обозначаемое "+1" или "−1". Число определяет направление спина: "вверх" или "вниз".
В магнитном материале каждый атом действует подобно маленькому магниту. При высоких температурах атомы находятся в неупорядоченном состоянии, и их спины указывают в случайных направлениях, так что общий магнетизм материала равен нулю. Ниже определённой температуры атомы выстраивают спины в одном направлении, придавая материалу магнитные свойства.
Модель Изинга описывает переход от случайности к упорядочиванию, "держа во внимании" массив спинов, которые направлены либо "вверх", либо "вниз", и случайно переворачиваются в зависимости от температуры. Создатели модели Изинга хотели показать, как спины внезапно меняют направленность по мере падения температуры. Хотя модель получилась очень трудной для анализа.
Теперь же исследователи разработали оптическую машину, созданную специально для решения модели Изинга (хотя бы приблизительного). Метод является детищем Ёсихисы Ямамото (Yoshihisa Yamamoto), учёного Стэнфордского университета, который в 1983 году основал лабораторию фундаментальных исследований (NTT Basic Research Laboratories) в Японии. Сегодня её сотрудники занимаются похожими разработками наравне с американскими коллегами.
Исследователи для создания "машины Изинга" использовали импульсы света, исходящие из оптического параметрического осциллятора (OPO) – устройства, похожего на лазер. Эти световые импульсы обозначали искусственные вращающиеся магниты (спины) и были измерены по отдельности и в сочетании друг с другом. В целом они образовали более крупную модель расположения крошечных вращающихся магнитов. Световые импульсы проходили через 300 метров оптического волокна.
Исследователям удалось создать машину Изинга, учитывающую 100 спинов. Для этого они добавили к своему оборудованию цифровые электронные схемы. Цифровой компонент машины имитирует взаимодействия световых импульсов, которые могли бы происходить (что облегчает работу машины), и затем все данные вводятся обратно в оптическую часть системы.
"Вместо того чтобы получить полностью оптическую машину, мы создали гибрид, в котором есть цифровые и оптические части", — говорит Макмахон. — Новая машина в некотором смысле является первой в своём роде, и по идее она открывает дополнительное поле исследований в области нетрадиционных вычислительных машин".
Исследователи провели всестороннее тестирование машины. Они запускали устройство, используя 4000 версий проблем оптимизации, чтобы показать, что решения машины не ограничиваются конкретными проблемами оптимизации. В настоящее время американская машина Изинга смогла решить задачи с сотней переменных с любым произвольным набором связей между переменными.
Взаимодополняющие исследования американских и японских учёных показали, что машину Изинга можно масштабировать до больших размеров, так что в будущем её можно будет использовать и для коммерческих целей.
Исследование опубликовано в научном издании Science.
