Вокруг света за пару часов: ученые разработан уникальный способ прокладывания маршрутов

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

Алгоритм Дейкстры, разработанный Эдсгером Дейкстрой в 1956 году, продолжает оставаться основным инструментом для решения задач поиска кратчайшего пути в графах, таких как маршруты между точками A и B. Алгоритм был создан в рамках демонстрации возможностей нового компьютера, и сам Дейкстра разработал его без использования письменных принадлежностей, за менее чем 20 минут в кафе. Изначально он предназначался для поиска кратчайшего пути от одной точки до всех остальных в сети, что делает его универсальным и важным инструментом в теории графов и алгоритмов.

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

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

Хотя эта версия алгоритма может не иметь немедленного практического применения, например, в таких системах, как Google Maps, из-за вычислительных затрат, она уже вдохновила дальнейшие исследования в теоретическом проектировании алгоритмов, способных оптимизировать поиск путей в различных ситуациях. Результаты работы будут признаны на Симпозиуме по основам компьютерных наук 2024 года, что подчеркивает их значимость для дальнейшего развития этой области.

Источник: Quanta Magazine