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

Алгоритм Дейкстри, створений голландським комп'ютерником Едсгером Дейкстрою 1956 року, залишається наріжним каменем у розв'язанні проблеми найкоротшого шляху в графах і різних схемах, які передбачають маршрут від точки А до точки Б. Спочатку задуманий для демонстрації можливостей нового комп'ютера, Дейкстра розробив його структуру без будь-якого письмового приладдя менш ніж за 20 хвилин у кафе. Його алгоритм ефективно обчислює найкоротший маршрут від однієї початкової точки до всіх інших пунктів призначення в мережі, пише Quanta Magazine.

У Фокус.Технології з'явився свій Telegram-канал. Підписуйтесь, щоб не пропускати найсвіжіші та найцікавіші новини зі світу науки!

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

Важливо Географія могла бути іншою: середньовічний картограф увійшов в історію через неправильну карту (фото)

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

Хоча цей оновлений алгоритм, можливо, не знайде негайного практичного застосування через обмеження реального світу, як-от обчислювальні витрати в системах на кшталт Google Maps, він уже надихнув на подальші дослідження в царині теоретичного проєктування алгоритмів, здатних прокладати найпростіші та найефективніші шляхи на різноманітних картах. Отримані результати будуть відзначені премією за найкращу доповідь на Симпозіумі з основ комп'ютерних наук 2024 року, що підкреслить їхню значущість для розвитку цієї галузі.

Раніше Фокус писав про п'ять щоденних звичок, які допоможуть зміцнити здоров'я мозку. У гонитві за здоровим мозком наука і повсякденні звички перетинаються напрочуд простими способами, виливаючись у легкі та ефективні кроки зі зміцнення самопочуття нашого центру прийняття рішень.

Також Фокус писав про особисті якості, які не дають нам вірити фейковим новинам. Згідно з дослідженням, проникливість відіграє вирішальну роль у здатності оцінювати точність інформації.