Математику из Дании удалось решить 40-летнюю задачу поиска кратчайшего пути их точки А в точку Б

На IEEE Symposium on Foundations of Computer Science было представлено оптимальное решение простой с первого взгляда задачи с учетом сопутствующих изменений

Трое ученых из Копенгагенского университета представили на конференции IEEE Symposium on Foundations of Computer Science решение задачи, над решением которой многие умы трудились 40 лет. Как стало известно «Регион online», речь идет о поиске кратчайшего пути между двумя точками. При этом условия перемещения между точками постоянно меняются. Именно из-за несовершенства формулы навигаторы не всегда правильно показывают кратчайшую дорогу.

– Новый алгоритм позволяет при затрате минимального количества ресурсов найти лучший маршрут в сети. И речь не только о дорогах, – рассказывают ученые на симпозиуме, презентуя новую формулу из Дании.

Работа выполнена в виде динамического графа. В нем сеть представлена абстрактно, с использованием ребер и узлов. Если смотреть на примере дорог, то узлы – это перекрестки, а ребра – дороги. Программа может вычислять путь в зависимости от состояния основных точек. Это может также применяться в информационных потоках для управления сетью.

А в это время в России становятся снова популярными VPN-сервисы. Из-за замедления Twitter.