Звучит сложно? Возможно. Но на самом деле этот тип вычислений уже используется в широком спектре приложений и технологий, от которых мы зависим, чтобы ориентироваться - например, Google Maps направляет нас по ландшафтам и городам.

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

"Мы обнаружили алгоритм, который решает проблему практически за линейное время, самым быстрым из возможных способов. Это фундаментальная алгоритмическая проблема, которая изучается с 1950-х годов и преподается по всему миру. Это было одной из причин, побудивших нас решить ее", - объясняет доцент Кристиан Вульф-Нильсен, которому явно трудно оставить нерешенную алгоритмическую проблему в покое.

Более быстрые расчеты для маршрутизации электромобилей

В прошлом году Вульф-Нильсен совершил еще один прорыв в той же области, который привел к результату, который касался того, как найти кратчайший путь в сети, которая меняется с течением времени. Его решение недавней загадки основывается на этой работе.

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

"Мы добавляем измерение, которого не было в предыдущих алгоритмах. Это измерение позволяет нам взглянуть на то, что мы называем отрицательными весами. Практическим примером этого может быть привязка к холмам в дорожной сети, что полезно знать, если у вас есть электромобиль, который заряжается во время движения под гору", - объясняет Вульф-Нильсен.

Факты о проблеме кратчайшего пути из одного источника

• Цель кратчайший путь из одного источника проблема состоит в том, чтобы найти кратчайшие пути от данного начального узла ко всем остальным узлам в сети.
• Сеть представлена в виде графа, состоящего из узлов и соединений между ними, называемых ребрами.
• Каждое ребро имеет направление (например, это может быть использовано для представления дорог с односторонним движением), а также вес, который выражает, насколько дорого обходится проезд по этому краю. Если все веса ребер неотрицательны, задача может быть решена практически за линейное время с помощью классического алгоритма Дейкстры.
• Новый результат решает проблему почти за то же время, что и алгоритм Дейкстры, но также допускает отрицательные веса ребер.

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

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

Удостоен чести в США

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

В то же время исследовательская статья, в которой подробно описывается их открытие, была удостоена премии "Лучшая статья" на конференции FOCS (Foundation of Computer Science) в Денвере, штат Колорадо. Наряду с STOC, это самая престижная конференция в области теоретической информатики. Конференция FOCS проходила с 31 октября по 3 ноября 2022 года.

"Люди со всего мира посещают эту конференцию, чтобы увидеть, как будут представлены наилучшие результаты", - говорит Кристиан Вульф-Нильсен.

Исследование проводилось в сотрудничестве между Кристианом Вульфом-Нильсеном из департамента компьютерных наук, Данупоном Нанонгкаем из Института Макса Планка и их американским коллегой Аароном Бернштейном из Университета Ратгерса.