Ученым удалось решить алгоритмическую загадку 50-х годов

Главная » Маркетинг, Статьи » Ученым удалось решить алгоритмическую загадку 50-х годов

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

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

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

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

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

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

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

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

Факты о проблеме кратчайшего пути:

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

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

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

Награда в США

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

В то же время научная статья, в которой подробно описывается их открытие, была удостоена награды «за лучший доклад» на конференции FOCS (Foundation of Computer Science) в Денвере, штат Колорадо.

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

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

В настоящее время исследование доступно на сайте arXiv