Как провайдеры карт (например, Google или Yahoo! Maps) предлагают указания?
Я имею в виду, что они, вероятно, имеют реальные данные в той или иной форме, включая расстояния, но, возможно, такие вещи, как скорость движения, наличие тротуаров, расписание поездов и т.д. Но предположим, что данные были в более простом формате, скажем, очень большой направленный граф с весами ребер, отражающими расстояния. Я хочу иметь возможность быстро вычислить направления из одной произвольной точки в другую. Иногда эти точки будут близко друг к другу (в пределах одного города), а иногда они будут далеко друг от друга (кросс-кантри).
Графовые алгоритмы, такие как алгоритм Дейкстры, не будут работать, потому что граф огромен. К счастью, эвристические алгоритмы вроде A *, вероятно, будут работать. Однако наши данные очень структурированы и, возможно, может возникнуть какой-то многоуровневый подход? (Например, сохраните предварительно вычисленные направления между определенными "ключевыми" точками далеко друг от друга, а также некоторые локальные направления. Затем направления для двух отдаленных точек будут включать локальные направления в ключевые точки, глобальные направления в другую ключевую точку, а затем локальные направления снова.)
Какие алгоритмы фактически используются на практике?
PS. Этот вопрос был мотивирован поиском причуд в направлениях онлайн-сопоставления. В отличие от неравенства треугольника, иногда Google Maps считает, что XZ занимает больше времени и дальше, чем использование промежуточная точка, как в XYZ. Но, может быть, их направление движения оптимизируется и для другого параметра?
ПФС. Здесь другое нарушение неравенства треугольника, которое предлагает (мне), что они используют какой-то многоуровневый подход: XZ по сравнению с XYZ. Первый, похоже, использует видный бульвар Себастополя, хотя он немного в стороне.
Изменить. Ни один из этих примеров больше не работает, но оба делались во время исходного сообщения.