Информатик из Индии усовершенствовал алгоритм поиска кратчайших путей в крупных сетях, устранив ограничение, которое оставалось нерешенным с 1996 года. Новый метод сохраняет скорость предыдущего, но точнее работает с близкими точками.
Ученый из Индийского технологического института в Гандинагаре Манодж Гупта усовершенствовал алгоритм поиска кратчайших путей между всеми парами точек в больших сетях. Его разработкарасширяет математическую гарантию точности, остававшейся ограниченной почти 30 лет. При этом новый метод не увеличивает всеобщее время вычислений.
Читайте также:
Столетняя математическая загадка. Ученые визуализировали проблему Томсона с помощью золота и гелия Задача поиска кратчайших путей между всеми парами вершин (APSP) состоит в определении минимального расстояния между каждыми двумя точками сети. Такие вычисления нужны не только навигационным сервисам, но и транспортным системам, интернет-инфраструктуре и исследованиям биологических сетей, включая взаимосвязи между белками и нейронами.
Традиционные алгоритмы могут нуждаться в значительных вычислительных ресурсах.
В некоторых случаях сложность возрастает пропорционально кубу количества точек: если их становится вдвое больше, объем работы увеличивается примерно в восемь раз. Поэтому исследователи ищут способы побыстрее получать достаточно точные, хотя и не обязательно идеальные результаты.
Важный шаг в этом направлении сделали в 1996 Дор, Гальперин и Цвик. Их алгоритм обеспечивал двукратное приближение: рассчитанное расстояние не превышало настоящее самое короткое более чем вдвое. К примеру, если оптимальный маршрут составляет 10 км, оценка должна была вкладываться в диапазон от 10 до 20 км.
Однако метод имел ограничение: такая гарантия действовала только для достаточно отдаленных точек. Если между двумя вершинами существовал короткий маршрут, алгоритм мог пропустить его из-за неудачного расположения выборочных точек и предложить путь, превышающий допустимую погрешность.
Гупта предложил многоуровневый подход к выбору таких точек. Вместо одного набора репрезентативных вершин он анализирует структуру сети в нескольких масштабах. Это помогает учитывать короткие маршруты, которые предыдущий метод мог не замечать.
Результаты исследования представили на 66-м ежегодном симпозиуме по основам компьютерных наук FOCS 2025. Разработка носит теоретический характер и пока не означает немедленного ускорения конкретных навигационных сервисов. Однако она совершенствует математические методы, которые могут помочь более эффективно анализировать крупные сети в транспорте, коммуникациях и искусственном интеллекте.
Читайте также:
