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

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

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

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

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

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

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

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

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