155
Проблема із заплутаністю багатьох переплетених маршрутів спіткала не одного мандрівника, роблячи його похід болісним. Однак прагнучи змінити цю ситуацію, вчені розробили прототип алгоритму, який може стати найкращим путівником.
Алгоритм Дейкстри, створений голландським комп’ютерником Едсгером Дейкстрою 1956 року, залишається наріжним каменем у розв’язанні проблеми найкоротшого шляху в графах і різних схемах, які передбачають маршрут від точки А до точки Б. Спочатку задуманий для демонстрації можливостей нового комп’ютера, Дейкстра розробив його структуру без будь-якого письмового приладдя менш ніж за 20 хвилин у кафе. Його алгоритм ефективно обчислює найкоротший маршрут від однієї початкової точки до всіх інших пунктів призначення в мережі, пише Quanta Magazine.
Попри свою простоту й адаптивність, що зробило його основоположною темою в навчанні інформатики, Алгоритм Дейкстри залишав місце для оптимізації структур даних, щоб прискорити виконання різних завдань. З роками з’явилися такі вдосконалення, як «купи», які збільшували час роботи алгоритму за рахунок швидкого пошуку найближчих вершин. Розробка такої спеціалізованої купи 1984 року встановила теоретичний стандарт для задач найкоротших шляхів з одним джерелом, зробивши алгоритм неперевершеним за найгірших умов, йшлося в дослідженні, опублікованому в arXiv.
Однак дослідників, як і раніше, інтригувала можливість знайти алгоритм, оптимальний у всіх сценаріях, — концепція, відома як «універсальна оптимальність». У результаті нового наукового прориву команда під керівництвом Вацлава Рожона і Бернхарда Хойплера розробила універсально оптимальний варіант алгоритму Дейкстри. Ця нова версія ефективно працює в будь-якій схемі мережі за найгірших умов трафіку, використовуючи властивість деяких структур купи, що раніше не використовувалася. Їхнє досягнення, спрощення складних конструкцій, підкреслює потенціал простих алгоритмів для виконання суворих завдань.
Хоча цей оновлений алгоритм, можливо, не знайде негайного практичного застосування через обмеження реального світу, як-от обчислювальні витрати в системах на кшталт Google Maps, він уже надихнув на подальші дослідження в царині теоретичного проєктування алгоритмів, здатних прокладати найпростіші та найефективніші шляхи на різноманітних картах. Отримані результати будуть відзначені премією за найкращу доповідь на Симпозіумі з основ комп’ютерних наук 2024 року, що підкреслить їхню значущість для розвитку цієї галузі.
