Алгоритм Дейкстри тривалий час вважався найефективнішим способом знаходження найкоротших маршрутів на графах. Проте тепер дослідники довели, що цей алгоритм є «універсально оптимальним».
Уявіть, що ви довгий час користуєтеся одним і тим же маршрутом на роботу, але одного дня через аварію чи ремонт доріг цей шлях стає найдовшим. Подібні ситуації є викликом і для дослідників, які розробляють алгоритми – покрокові процедури для вирішення завдань комп’ютером. І хоча існує багато алгоритмів для пошуку найкоротшого маршруту, час, необхідний для знаходження відповіді, може змінюватися в залежності від умов використання.
Для більшості задач неможливо знайти «ідеальний» алгоритм, який працюватиме швидше за інші у будь-яких умовах. Проте нове математичне доведення свідчить, що для пошуку найкоротших шляхів у найгірших умовах існує майже ідеальний алгоритм, який підходить для будь-якої вуличної сітки. Більше того, цей алгоритм – це класичний алгоритм Дейкстри, якому майже 70 років і який широко вивчають у комп’ютерних науках.
Історія алгоритму Дейкстри
Алгоритм Дейкстри був розроблений у 1956 році молодим нідерландським вченим Едсгером Дейкстрою, який хотів продемонструвати можливості нового комп’ютера ARMAC. Ідея алгоритму прийшла йому, коли він відпочивав у кафе. Оскільки під рукою не було ні ручки, ні паперу, Дейкстра розробив алгоритм у голові.
Цей алгоритм не лише знаходить найшвидший маршрут до однієї точки, а й формує впорядкований список часу подорожі від початкової точки до кожної іншої на графі, вирішуючи задачу, яку вчені називають задачою найкоротшого шляху з одного джерела. У 1984 році комп’ютерні науковці вдосконалили цей алгоритм, розробивши спеціальну структуру даних – «купу», яка забезпечила досягнення найнижчої теоретичної межі часу виконання алгоритму.
Пошук ідеального рішення
Більшість дослідників оцінюють алгоритми за тим, як вони працюють у найгірших випадках. Проте у новому дослідженні команда вчених поставила питання про те, чи можна розробити алгоритм, який був би найшвидшим для будь-якої можливої мережі доріг за будь-яких умов трафіку. Це спонукало їх до створення «універсально оптимального» алгоритму – алгоритму, що залишатиметься найефективнішим незалежно від особливостей графу або умов руху.
Протягом 2021 року команда дослідників на чолі з Бернхардом Гойплером довела можливість створення універсально оптимальних алгоритмів для низки важливих задач на графах. Цей прорив надихнув інших учених на пошуки оптимального алгоритму для задачі найкоротшого шляху з одного джерела.
Нова ера для алгоритму Дейкстри
У 2023 році команда з трьох аспірантів, включаючи Вацлава Рожоня та його колег, почала досліджувати можливість створення універсально оптимального варіанту алгоритму Дейкстри. Вони зосередилися на виборі структури даних і зрештою довели, що змінювати сам алгоритм не потрібно – достатньо було змінити лише структуру купи.
Цей універсально оптимальний алгоритм не матиме безпосереднього впливу на повсякденні програми, наприклад, Google Maps, оскільки на практиці враховуються й інші аспекти, окрім теоретичної ефективності. Проте це дослідження відкриває нові перспективи у вивченні оптимальності, надихаючи дослідників переглянути усталені підходи до аналізу алгоритмів.
Тепер вчені знають, що прості алгоритми зі складними гарантіями можуть бути більш поширені, ніж передбачалося раніше, і команда вже визначила два інших приклади для подальшого дослідження.
