Алгоритм Fastest Path

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

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

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

Есть ли хорошие алгоритмы для этого? Или, по крайней мере, хорошая модификация A *?

источник

2010-09-29 radek

«Самый быстрый» алгоритм пути - это всего лишь алгоритм кратчайшего пути, где весовые коэффициенты рельефа представляют собой взвешенное время в пути вместо расстояния. A * по-прежнему будет вашим лучшим выбором, вам просто придётся придумать хороший способ оценить весы на основе имеющихся данных (и придумать эвристику). –

Почему вы не можете просто учитывать все факторы при расчете стоимости кросс (как вы предлагаете для качества дороги)? – dave

Я думал, что должен быть лучший подход. Но если все подскажут, что A * - лучшее решение, тогда я буду с этим согласен. – radek

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

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

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

источник

2010-09-29 19:37:05 aioobe

A * всегда оптимален, если он эвристичен, допустим, по крайней мере, по определению «оптимального» в компьютерной науке –

Хм .. Я не уверен, что получаю то, что допустимо в этом контексте. Однако я сомневаюсь, что такая эвристическая функция возможна для графа с произвольными весами ребер. – aioobe

Вы, безусловно, можете - допустимые функции для этих случаев легко найти (например, для реального расстояния - вы просто измеряете воздушную линию (это как вы это называете?)) –

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

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

источник

2010-09-29 19:35:39 Claudiu

Алгоритм Fastest Path

ответ

Смежные вопросы