Вчений з Копенгагенського університету разом з двома колегами створив алгоритм, який здатний знаходити найкоротший шлях між двома точками в будь-якій ситуації оптимальним чином. Над цим завданням дослідники билися 40 років.
Як скласти найкоротший маршрут, якщо дорожня ситуація постійно змінюється? Тепер вчений створив алгоритм, який здатний враховувати всі зміни і ефективно обробляти інформацію, що надходить, витрачаючи менше часу і ресурсів, ніж всі сучасні програми
Одне з класичних алгоритмічних завдань пов'язане з обчисленням найкоротшого шляху між двома точками. Здавалося б, це повинно бути досить просто, але у програм виникають проблеми, якщо маршрут проходить по змінюваній мережі - будь то дороги і розв'язки або потоки інформації. Багато хто стикався з тим, що навігатори іноді ведуть водія по не найкоротшому маршруту, через що з помічників ці програми перетворюються на заважаючий софт.
Тепер данський вчений розробив новий алгоритм, який здатний знайти оптимальний шлях між двома точками. Під оптимальним в даному контексті розуміється алгоритм, який витрачає якомога менше часу і пам'яті комп'ютера на обчислення найкращого маршруту в мережі. Це відноситься не тільки до дорожніх і транспортних мереж, але і до інтернету або будь-якого іншого типу мереж.
Дослідники представили мережу у вигляді так званого динамічного графа. Він являє собою абстрактне представлення мережі, що складається з ребер і вузлів. Якщо переводити це на транспортну аналогію, то ребрами будуть дороги, а вузлами - перехрестя. Динамічний граф може змінюватися з плином часу, тому новий алгоритм здатний враховувати такі зміни.
Витрачаючи мінімальну кількість обчислювальних ресурсів програма визначає найшвидший шлях, враховуючи, наприклад, зміну довжини ребер графа у часі. Для транспортної мережі це еквівалентно утворенню затору. Також, за словами авторів дослідження, розробку можна використовувати для оптимізації обробки даних - алгоритм дозволить знизити час і обчислювальні ресурси, необхідні для операцій з інформаційними потоками.
Дослідження було представлено на конференції IEEE Symposium on Foundations of Computer Science.
