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

Фото: Getty Images

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

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

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

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

Ирина Скиба / Skibair
Журналист AOinform