Как работает программа поиска маршрутов?

Question

Я спрашиваю на довольно высоком, независимом от языка уровне.

Как работает поиск маршрута (как в Google Maps «Проложить маршрут» или GPS)? Я не могу поверить, что он пробует все мыслимые маршруты и выбирает самый короткий / быстрый и т. Д. Должен быть какой-то логичный способ найти лучший маршрут с учетом начальной и конечной точки.

Любое объяснение было бы замечательно.

Answer 1

Вы должны прочитать о проблеме кратчайшего пути и Алгоритм Дейкстры .Оба они используются для определения пути между двумя точками.Карты Google (и другие картографические приложения) добавляют дополнительные функции (например, изменение маршрута и т. Д.), Но эти две концепции являются основной предпосылкой решения проблемы.

Answer 2

Очень старая запись, но я просто искал этот конкретный вопрос и нашел хорошую статью с объяснением: http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

В основном, он использует A * алгоритм поиска и классификация маршрутов (короткий маршрут, длинный маршрут и т. д.), чтобы уменьшить вычислительные затраты и требования к памяти.