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