Учёные Лаборатории искусственного интеллекта Сбербанка и ИТМО нашли способ улучшить транспортную логистику в мегаполисах.
Поиск кратчайшего пути между двумя вершинами — одна из фундаментальных задач теории графов. Можно проиллюстрировать это на примере навигатора. Прокладывая маршрут из точки «А» в точку «В», программа перебирает множество вариантов, чтобы найти оптимальный путь. В крупных городах с огромным количеством дорог и перекрёстков поиск на основе традиционных способов требует больших вычислений. Метод позволяет эффективно предсказывать области, содержащие кратчайший маршрут, благодаря чему многократно повышается скорость расчётов без потери точности.
Разработанный метод позволит не только упростить городскую навигацию и оптимизировать логистику грузоперевозок, но и эффективно работать с абстрактными графовыми структурами в различных сферах. Его можно использовать, например, в социальных сетях для быстрого поиска связей между пользователями через общих знакомых или для мгновенного доступа к нужной информации. Кроме того, метод имеет большой потенциал в биомедицине — в частности, при анализе графовой структуры белков.