Решена самая сложная «задача коммивояжера» в истории

Над ней математики бились веками.

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

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

Задача объединяет теорию графов («карту» точек с путевыми ветвями между ними) с комбинаторикой (в данном случае различные способы подсчета через граф) и оптимизацией (выбор наилучшего, кратчайшего маршрута из данного графа). Это обстоятельство делает задачу коммивояжера любимым упражнением для студентов на уроках математики и информатики во многих учебных учреждениях.

Секрет успеха в решении данной задачи кроется в специальной схеме, разработанной для расчета маршрутов. В обычном компьютерном процессоре сначала составляет план маршрутов, а затем все они проходят через процессор по одной точке за раз — система является линейной.

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

Исследователи взяли традиционную схемотехнику и изменили одну важную вещь: они переставили специальные «спиновые ячейки», представляющие все точки графа. В результате все спиновые ячейки могли сообщаться друг с другом, а не только с непосредственным окружением, связанным линиями на графе. Новая схема позволяет создавать маршруты, используя несколько точек одновременно, а не одну, уменьшая нагрузку на вычислительный ресурс системы.

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