Какие алгоритмы вычисляют направления от точки A к точке B на карте?

Question

Как поставщики карт (такие как Google или Yahoo! Maps) предлагают маршруты?

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

Алгоритмы графа, такие как алгоритм Дейкстры, не будут работать, потому что граф огромен. К счастью, эвристические алгоритмы типа A *, вероятно, будут работать. Тем не менее, наши данные очень структурированы, и, возможно, какой-то многоуровневый подход может сработать? (Например, сохраните предварительно вычисленные направления между определенными «ключевыми» точками далеко друг от друга, а также некоторые локальные направления. Тогда направления для двух удаленных точек будут включать локальные направления к ключевым точкам, глобальные направления к другой ключевой точке, а затем локальные направления снова.)

Какие алгоритмы фактически используются на практике?

PS. Этот вопрос был мотивирован нахождением причуд в направлениях картографирования онлайн. Вопреки неравенству треугольника, иногда Карты Google считают, что X-Z занимает больше времени и дальше, чем использование промежуточной точки, как в X-Y-Z . Но, может быть, их маршруты для прогулок тоже оптимизированы для другого параметра?

PPS. Вот еще одно нарушение неравенства треугольника, которое предполагает (для меня), что они используют какой-то многоуровневый подход: X-Z против X-Y-Z . Бывший, кажется, использует выдающийся Севастопольский бульвар, хотя он немного в стороне.

Редактировать : Кажется, что ни один из этих примеров больше не работает, но оба работали во время исходного сообщения.

Answer 1

У меня было еще несколько мыслей по этому поводу:

1) Помните, что карты представляют физическую организацию. Сохраните широту / долготу каждого пересечения. Вам не нужно проверять многое за точки, которые лежат в направлении вашей цели. Только если вы оказались заблокированы, вам нужно выйти за рамки этого. Если вы сохраняете наложение превосходных соединений, вы можете ограничить его еще больше - обычно вы никогда не встретите одно из них таким образом, чтобы это было далеко от вашего конечного пункта назначения.

2) Разделите мир на множество зон, ограниченных связью, определите все точки соединения между зонами. Найдите зоны, в которых находятся ваш источник и цель, для маршрута начальной и конечной зоны от вашего местоположения до каждой точки подключения, для зон между просто отображением между точками подключения. (Я подозреваю, что многие из них уже предварительно рассчитаны.)

Обратите внимание, что зоны могут быть меньше, чем столичная зона. Любой город с элементами местности, которые разделяют его (например, река), будет состоять из нескольких зон.

Answer 2

Мне было очень любопытно, какая эвристика использовалась, когда некоторое время назад мы получили маршруты из одной и той же стартовой точки возле Санта-Роза, к двум разным лагерям в национальном парке Йосемити. Эти разные пункты назначения дали совершенно разные маршруты (через I-580 или CA-12), несмотря на тот факт, что оба маршрута сошлись за последние 100 миль (вдоль CA-120), после чего снова разошлись на несколько миль в конце. Это было довольно повторяемым. Эти два маршрута были на расстоянии до 50 миль на расстоянии около 100 миль, но расстояния и время были довольно близки, как и следовало ожидать.

Увы, я не могу воспроизвести это - алгоритмы, должно быть, изменились. Но мне было любопытно по поводу алгоритма. Все, что я могу предположить, - это то, что было некоторое направленное сокращение, которое оказалось чрезвычайно чувствительным к крошечной угловой разнице между пунктами назначения, видимой издалека, или были разные предварительно вычисленные сегменты, выбранные выбором конечного пункта назначения.

Answer 3

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

Учитывая, что это приложение Google, также разумно предположить, что большая часть магии делается с помощью обширного кэширования. :) Я бы не удивился, если бы кэширование 5% самых распространенных запросов маршрута Google Map позволяло обрабатывать большой кусок (20%? 50%?) Запросов простым поиском.

Answer 4

Говоря о GraphHopper , быстрый планировщик маршрутов с открытым исходным кодом на основе OpenStreetMap, я прочитал немного литературы и реализовал некоторые методы. Самым простым решением является Dijkstra, а простым улучшением является двунаправленная Dijkstra, которая исследует примерно только половину узлов. С двунаправленной Dijkstra маршрут через всю Германию занимает уже 1 секунду (для автомобильного режима), в C это будет, вероятно, только 0,5 с или около того;)

Я создал анимированный GIF-файл поиска по реальному пути с помощью двунаправленной Dijkstra здесь . Также есть еще несколько идей, чтобы сделать Dijkstra быстрее , как, например, A *, который является "ориентированным на цель Dijkstra". Также я создал для нее gif-анимацию .

Но как это сделать (намного) быстрее?

Проблема в том, что для поиска пути необходимо исследовать все узлы между точками, и это действительно дорого, поскольку в Германии их уже несколько миллионов. Но дополнительная проблема Dijkstra и т. Д. Заключается в том, что при таких поисках используется много оперативной памяти.

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

Для GraphHopper я решил использовать Сжатие Иерархии , потому что это относительно «легко» реализовать и не требует много времени для подготовки графа. Это по-прежнему приводит к очень быстрому времени отклика, как вы можете проверить на нашем онлайн-экземпляре GraphHopper Maps . Например. из Южной Африки в восточный Китай , что составляет 23000 км и почти 14 дней езды на автомобиле и занимает всего ~ 0,1 с на сервере.

Answer 5

Я работал над маршрутизацией в течение нескольких лет, с недавним всплеском активности, вызванным потребностями моих клиентов, и я обнаружил, что A * достаточно быстро; на самом деле нет необходимости искать оптимизацию или более сложные алгоритмы. Маршрутизация по огромному графу не является проблемой.

Но скорость зависит от наличия в памяти всей сети маршрутизации, под которой я подразумеваю направленный граф дуг и узлов, представляющих сегменты и соединения маршрутов соответственно. Основные временные затраты - это время, необходимое для создания этой сети. Некоторые приблизительные цифры, основанные на обычном ноутбуке под управлением Windows и маршрутизации по всей Испании: время, необходимое для создания сети: 10-15 секунд; время, необходимое для расчета маршрута: слишком мало для измерения.

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

Answer 6

Я вижу, что случилось с картами в ОП:

Посмотрите на маршрут с указанной промежуточной точкой: маршрут идет немного назад из-за этой дороги, которая не является прямой.

Если их алгоритм не вернется назад, он не увидит более короткий маршрут.

Answer 7

Алгоритм кратчайшего пути для всех пар вычисляет кратчайшие пути между всеми вершинами графа. Это позволит предварительно вычислять пути вместо того, чтобы вычислять путь каждый раз, когда кто-то хочет найти кратчайший путь между источником и пунктом назначения. Алгоритм Флойда-Варшалла является алгоритмом кратчайшего пути для всех пар.

Answer 8

Карты никогда не принимают во внимание всю карту. Я думаю: 1. В зависимости от вашего местоположения они загружают место и ориентиры на этом месте. 2. Когда вы ищете пункт назначения, то есть когда они загружают другую часть карты и составляют график из двух мест, а затем применяют алгоритмы кратчайшего пути.

Кроме того, существует важный метод динамического программирования, который, я подозреваю, используется при расчете кратчайших путей. Вы также можете сослаться на это.