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




algorithms a* (16)

Как предлагают провайдеры карт (например, Google или Yahoo! Maps) направления?

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

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

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

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

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

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


Answers

Вот самые быстрые алгоритмы маршрутизации в мире, сравниваемые и доказанные для правильности:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Вот техническая беседа на тему:

youtube.com/watch?v=-0ErpE8tQbw

Вот реализация алгоритма иерархии шоссе, как обсуждалось schultes (в настоящее время только в berlin, я пишу интерфейс и разрабатывается мобильная версия):

http://tom.mapsforge.org/


Я вижу, что происходит с картами в OP:

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

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


Я делал это довольно много раз, на самом деле, используя несколько разных методов. В зависимости от размера (географического) карты вы можете захотеть использовать функцию haversine как эвристику.

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

f(n) = k*h(n) + g(n)

где k - некоторая константа, большая, чем 0.


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

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


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

Я создал анимированный gif реального пути поиска с двунаправленной Dijkstra here . Также есть еще несколько идей, чтобы сделать Дийкстра быстрее, чем делать A *, что является «целенаправленной Дейкстра». Также я создал для него gif-animation .

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

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

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

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


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

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


Этот вопрос был активной областью исследований в последние годы. Основная идея - сделать предварительную обработку на графике один раз , ускорить все последующие запросы . С помощью этой дополнительной информации маршруты могут быть рассчитаны очень быстро. Тем не менее, Алгоритм Дейкстры является основой для всех оптимизаций.

Арахнид описал использование двунаправленного поиска и обрезку краев на основе иерархической информации. Эти методы ускорения работают достаточно хорошо, но самые последние алгоритмы превосходят эти методы во что бы то ни стало. При существующих алгоритмах кратчайшие пути могут быть рассчитаны за меньшее время, чем одна миллисекунда в континентальной дорожной сети. Для быстрой реализации немодифицированного алгоритма Дейкстры требуется около 10 секунд .

В статье « Инженерные алгоритмы планирования быстрого маршрута» дается обзор хода исследований в этой области. Дополнительную информацию см. В ссылках на этот документ.

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

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

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


Вероятно, похоже на ответ на заранее рассчитанные маршруты между основными местоположениями и многоуровневыми картами, но я понимаю, что в играх для ускорения A * у вас есть карта, которая очень грубая для макронавигации и мелкозернистая карта для навигацию к границе направлений макросов. Таким образом, у вас есть 2 небольших пути для вычисления, и, следовательно, ваше пространство поиска намного меньше, чем просто один путь к месту назначения. И если вы занимаетесь этим много, у вас будет много данных, предварительно рассчитанных, так что по крайней мере часть поиска - это поиск предварительно вычисленных данных, а не поиск пути.


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

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

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


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

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


Говоря как кто-то, кто провел 18 месяцев, работая в картографической компании, которая включала в себя работу над алгоритмом маршрутизации ... да, Dijkstra's действительно работает с несколькими модификациями:

  • Вместо того, чтобы делать Dijkstra's один раз из источника в dest, вы начинаете с каждого конца и расширяете обе стороны, пока не встретитесь посередине. Это устраняет примерно половину работы (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
  • Чтобы не исследовать задние аллы каждого города между вашим источником и пунктом назначения, вы можете иметь несколько слоев данных карты: слой «шоссе», который содержит только шоссе, «вторичный» слой, который содержит только вторичные улицы и т. Д. Затем вы исследуете только более мелкие разделы более подробных слоев, расширяя по мере необходимости. Очевидно, что это описание оставляет много деталей, но вы получаете идею.

С изменениями в этих строках вы можете выполнить маршрутизацию по пересеченной местности в очень разумные сроки.


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


Нынешний уровень техники с точки зрения времени запроса для статических дорожных сетей представляет собой алгоритм маркировки концентратора, предложенный Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Прошедший и отлично написанный обзор поля был недавно опубликован в виде технического отчета Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

Короткий вариант ...

Алгоритм маркировки концентратора обеспечивает самые быстрые запросы для статических дорожных сетей, но для этого требуется большое количество бара (18 ГБ).

Маршрутизация маршрутных узлов немного медленнее, хотя требуется всего около 2 ГБ памяти и имеет более быструю предварительную обработку.

Иерархии сокращения обеспечивают хороший компромисс между быстрыми временами предварительной обработки, низкими требованиями к пространству (0,4 ГБ) и быстрыми запросами.

Ни один алгоритм полностью не доминирует ...

Этот интересный технический доклад от Peter Sanders может показаться интересным

https://www.youtube.com/watch?v=-0ErpE8tQbw

Также этот разговор Эндрю Голдберга

https://www.youtube.com/watch?v=WPrkc78XLhw

Внедрение иерархии сокращений с открытым исходным кодом доступно на веб-сайте исследовательской группы Peter Sanders в KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Также доступно легко доступное сообщение в блоге, написанное Microsoft, где используется алгоритм CRP ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/


Графовые алгоритмы, такие как алгоритм Дейкстры, не будут работать, потому что график огромен.

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

Dijkstra может фактически хорошо работать для хорошо выполненных графиков. С другой стороны, при тщательной параметризации A * всегда будет работать так же хорошо, или лучше. Вы уже пробовали, как это будет выполняться на ваших данных?

Тем не менее, мне также было бы очень интересно узнать о опыте других народов. Конечно, интересные примеры, такие как поиск в Google Map, особенно интересны. Я мог представить что-то вроде направленного ближайшего соседа эвристическим.


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

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

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

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


Я являюсь автором контроллера 2048, который лучше, чем любая другая программа, упомянутая в этом потоке. Эффективная реализация контроллера доступна на github.com/aszczepanski/2048 . В отдельном репо есть также код, используемый для обучения функции оценки состояния контроллера. Метод обучения описан в paper .

Контроллер использует expectimax-поиск с функцией оценки состояния, полученной с нуля (без экспертизы человека 2048) по варианту обучения с временным различием (метод обучения усилению). Функция состояния-значения использует сеть n-кортежей , которая в основном представляет собой взвешенную линейную функцию шаблонов, наблюдаемых на доске. Всего в нем было более 1 миллиарда весов .

Спектакль

При 1 ходу / с: 609104 (100 игр в среднем)

При 10 ходах / с: 589355 (300 игр в среднем)

При 3-слойном (около 1500 ходов / с): 511759 (в среднем по 1000 игр)

Статистика черепицы для 10 ходов / сек выглядит следующим образом:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Последняя строка означает наличие заданных фрагментов одновременно на плате).

Для 3-слойного:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Тем не менее, я никогда не видел, чтобы он получал плиту 65536.





algorithm routing mapping