Решение задачи коммивояжера с помощью магнонного комбинаторного устройства

Том 13 научных отчетов, номер статьи: 11708 (2023) Цитировать эту статью

207 Доступов

Подробности о метриках

Задача коммивояжера (TSP) — это задача принятия решений, которая важна для ряда практических приложений. Сегодня эта проблема решается на цифровых компьютерах, использующих архитектуру логического типа путем проверки одного за другим ряда возможных маршрутов. В этой работе мы описываем специальный тип оборудования для решения TSP. Это магнонное комбинаторное устройство, состоящее из магнитной и электрической частей, соединенных в активную кольцевую цепь. Существует несколько возможных путей распространения в магнитной сетке, состоящей из фазовращателей, частотных фильтров и аттенюаторов. Фазовращатели имитируют города в TSP, а расстояние между городами кодируется в затухании сигнала. Набор частотных фильтров заставляет волны разных частот распространяться по разным маршрутам. Принцип работы основан на классической волновой суперпозиции. Существует множество волн, приходящих по всем возможным маршрутам параллельно, накапливающих различные фазовые сдвиги и затухающие амплитуды. Однако только та волна(ы), которая накапливает определенный фазовый сдвиг, будет усилена электрической частью. В первую очередь усиливаются волны, обладающие минимальными потерями при распространении. Это делает этот тип устройства подходящим для решения TSP, где волны подобны продавцам, путешествующим по всем возможным маршрутам одновременно. Мы представляем результаты численного моделирования, иллюстрирующие решения TSP для четырех и шести городов. Также мы представляем экспериментальные данные для решения TSP с четырьмя городами. Прототип устройства построен из коммерчески доступных компонентов, включая магнитные фазовращатели/фильтры, коаксиальные кабели, разветвители, аттенюаторы и широкополосный усилитель. Есть три примера поиска кратчайшего маршрута между городами для трех разных наборов расстояний между городами. Предлагаемый подход масштабируется для TSP с большим количеством городов. Также обсуждаются физические ограничения и проблемы.

TSP — одна из самых известных задач комбинаторной оптимизации1. Его можно сформулировать следующим образом: «По списку городов и расстояниям между каждой парой городов найти кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город». Это недетерминированная задача с полиномиальной сложностью по времени (NP-трудная), что означает, что нет гарантии получения оптимального маршрута и нет точного алгоритма для его решения за полиномиальное время. TSP важен во многих практических приложениях, включая транспортировку2, планирование3 и геномику4. Математически его можно определить как набор \(n\) городов с именами \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n }\right\}\) и перестановки \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). Цель состоит в том, чтобы выбрать \({\sigma }_{i}\) так, чтобы сумма всех евклидовых расстояний между городами в туре была минимизирована. TSP можно смоделировать как неориентированный взвешенный граф, как показано на рис. 1, где города — это вершины графа, пути — это ребра графа, а расстояние пути — это вес ребра. TSP можно решить, проверив один за другим все возможные \(\left(n-1\right)!/2\) возможные маршруты. Сравнительно легко проверить все возможные маршруты для небольшого количества городов. Например, для TSP с четырьмя городами существуют маршруты \(\left(4-1\right)!/2=3\). Число возможных маршрутов увеличивается пропорционально \(n\) факториалу, что затрудняет решение задачи для большого числа городов с использованием классических вычислительных устройств.

Неориентированный взвешенный график для TSP с четырьмя городами. Города — это вершины графа, пути — это ребра графа, а расстояние пути — это вес ребра.

Было несколько попыток создать специальное оборудование для решения TSP5,6. Например, задача TSP для 6 городов была решена с использованием оптической сети типа Кохонена6. Однако ни один из этих подходов не привел к созданию практически жизнеспособного устройства. Недавно к TSP7 были применены различные методы оптимизации, используемые в искусственном интеллекте (ИИ). Это может значительно ускорить решение TSP, но не может обеспечить фундаментального преимущества при реализации на обычном оборудовании.