Алгоритм быстрого пути

Question

В настоящее время я внедряю навигационную систему для маршрутизации по Европе.Пока что у меня реализован кратчайший путь (Дейкстра и А *).Это была легкая часть, теперь мне нужен алгоритм для быстрого пути.Это должно быть быстро и надежно.

Я знаю, что это можно сделать, просто присвоив значения качеству дороги (например, 1 магистраль, 2 основные дороги ...), затем умножив эти значения на стоимость маршрута и, наконец, используйте Дейкстра или А *, ноэто не достаточно сложно.

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

Есть ли для этого хорошие алгоритмы?Или хотя бы хорошую модификацию A *?

Answer 1

В вашей реализации для кратчайшего пути вы выбрали расстояние в качестве веса для ребра.

Теперь, если вы хотите найти самый быстрый путь, вы просто выбираете ожидаемое время прохождения вместо веса для ребер .Точно так же, если вы хотите самый надежный путь, вы выбираете измерение «надежности» в качестве веса для ребер.

A * (хотя не всегда оптимально, так как оно зависит от эвристической функции), вероятно, вам лучшевариант для этого типа приложения.Если ваш A * недостаточно точен, я предлагаю вам либо пойти на Dijkstras, либо потратить некоторое время на настройку и улучшение своей эвристической функции.

Answer 2

Это зависит от того, что вы подразумеваете под «самым быстрым» путем. Если бы вы знали среднюю скорость, по которой вы могли бы путешествовать на каждом участке дороги, то вы могли бы просто преобразовать свой график, чтобы на его краях было «время, затраченное на прохождение» вместо «расстояние». Затем вы можете создать алгоритм кратчайшего пути над новым графом.

Кажется, вы упомянули, что этого недостаточно. Я думаю, проблема в том, что вы должны определить, что означает «самый быстрый». Как качество дороги влияет на скорость? Как насчет светофора? Это все переменные, которые вы должны найти способ учета. Если вы как человек не знаете метрики, которую будете использовать, вам будет сложно заставить компьютер это делать.