Сравнительный анализ математических алгоритмов показал, что метод Дейкстры не только быстрее других, но и исключает ошибки при расчетах за счет однократного прохождения каждой точки маршрута

КАЗАНЬ, 17 февраля. /ТАСС/. Исследователи из Казанского национального исследовательского технического университета им. А. Н. Туполева (КНИТУ-КАИ) выявили оптимальный метод расчета транспортных маршрутов. Сравнительный анализ математических алгоритмов показал, что метод Дейкстры не только быстрее других, но и исключает ошибки при расчетах за счет однократного прохождения каждой точки маршрута, сообщили ТАСС в пресс-службе университета.

"Исследователи провели сравнительный анализ трех наиболее распространенных алгоритмов поиска кратчайших расстояний. Алгоритм Дейкстры работает как навигатор, прокладывая путь от заданной точки старта ко всем возможным пунктам назначения, постепенно "исследуя" территорию и выбирая оптимальные варианты маршрута. Алгоритм Флойда сразу рассчитывает все возможные маршруты между всеми точками на карте, что требует больше времени, но может быть полезно при долгосрочном планировании. Алгоритм Беллмана действует как пошаговый планировщик, анализируя каждый участок пути последовательно", - рассказали в пресс-службе.

Тестирование на реальных маршрутных данных показало существенное преимущество алгоритма Дейкстры: он выполняет расчеты за 0,969 секунды, в то время как алгоритмам Флойда и Беллмана требуется 1,029 и 1,004 секунды соответственно. Однако главное достоинство метода заключается в его надежности: алгоритм работает только с положительными расстояниями между точками маршрута, что соответствует реальным условиям, и исключает повторное прохождение через одну и ту же точку, предотвращая ошибки при расчетах.

На практике это означает, что логистическая компания может за считанные минуты проложить оптимальный маршрут между любыми городами, учитывая все возможные варианты путей. При планировании доставки груза из Шанхая в Казань система автоматически проанализирует все возможные варианты путей с учетом морских портов, железнодорожных узлов и автомагистралей, предложив оптимальный маршрут за несколько секунд вместо многочасовой ручной работы с картами.

"Наше исследование показало, что при выборе алгоритма для расчета маршрутов важна не только скорость вычислений, но и способность алгоритма избегать ошибок, таких как зацикливание на одних и тех же участках пути. Алгоритм Дейкстры оказался оптимальным именно по совокупности характеристик - он и быстрый, и надежный", - приводит пресс-служба слова кандидата технических наук, доцента кафедры автоматизированных систем обработки информации и управления КНИТУ-КАИ Ильдуса Ризаева.

Разработанная методика может найти применение в логистических компаниях, службах доставки, а также при планировании городских транспортных маршрутов. Использование геоинформационных систем в сочетании с эффективными алгоритмами расчета позволяет существенно оптимизировать процессы доставки грузов и товаров, сокращая время на планирование и минимизируя риск человеческих ошибок при составлении маршрутов. Результаты исследования опубликованы в номере научного журнала "Нанотехнологии: наука и производство".

https://nauka.tass.ru/nauka/23166755

22.02.25