Как работает программа поиска маршрутов?
Я спрашиваю на довольно высоком, независимом от языка уровне.
Как работает поиск маршрута (как в Google Maps "Проложить маршрут" или GPS)? Я не могу поверить, что он пробует все мыслимые маршруты и выбирает самый короткий / быстрый и т. Д. Должен быть какой-то логичный способ найти лучший маршрут с учетом начальной и конечной точки.
Любое объяснение было бы здорово.
2 ответа
Вы должны прочитать о кратчайшем пути и алгоритме Дейкстры. Оба они используются для определения пути между двумя точками. Карты Google (и другие картографические приложения) добавляют дополнительные функции (например, изменение маршрута и т. Д.), Но эти две концепции являются основной предпосылкой решения проблемы.
Очень старый пост, но я просто искал этот конкретный вопрос и нашел хорошую статью с объяснением: http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html
В основном, он использует алгоритм поиска A* и классификацию маршрутов (короткий маршрут, длинный маршрут и т. Д.), Чтобы уменьшить вычислительные требования и требования к памяти.