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

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

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

статьи Разработка Быстрых Алгоритмов Планирования Маршрута дается обзор хода исследований в этой области. Дополнительную информацию см. в ссылках на этот документ.

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

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

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

просто обращаясь к нарушениям неравенства треугольника, надеюсь, что дополнительный фактор, который они оптимизируют, - это здравый смысл. Вы не обязательно хотите, самый короткий или быстрый маршрут, так как это может привести к хаосиуничтожение. Если вы хотите, чтобы ваши направления предпочитали основные маршруты, которые удобны для грузовиков и могут справиться с тем, чтобы каждый водитель sat-nav-following отправлял их, вы быстро отбрасываете неравенство треугольника[1].

Если Y это узкая жилая улица между X и Z, вы, вероятно, хотите использовать только ярлык через Y, если пользователь явно просит X-Y-Z. Если они просят X-Z, они должны придерживаться основных дорог, даже если это немного дальше и занимает немного больше времени. Это похоже на парадокс Браесса - Если каждый пытается взять самый короткий, самый быстрый маршрут, результирующая перегрузка означает, что это не самый быстрый маршрут для кого-либо больше. Отсюда мы уходим от теории графов в игру теория.

[1] фактически, любая надежда на то, что произведенные расстояния будут функцией расстояния в математическом смысле, умирает, когда вы допускаете односторонние дороги и теряете требование симметрии. Потеря неравенства треугольника тоже просто втирает соль в рану.

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

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

вот технический разговор google на эту тему:

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

вот реализация алгоритма highway-hierarchies, как обсуждалось Шульцем (в настоящее время только в Берлине, я пишу интерфейс и мобильную версию разрабатывается также):

http://tom.mapsforge.org/

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

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

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

Я не работал на картах Google или Microsoft или Yahoo раньше, поэтому я не могу сказать вам, как они работают.

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

мы использовали метод под названием ACO (Ant colony optimization), чтобы расписание и маршрут движения грузовиков. Этот метод является методом ИИ, который был применен к проблеме коммивояжера для решения проблем маршрутизации. Трюк с ACO заключается в том, чтобы построить расчет ошибок на основе известных фактов маршрутизации, чтобы модель решения графа знала, когда нужно выйти (когда ошибка достаточно мала).

вы можете google ACO или TSP, чтобы найти больше об этой технике. Однако я не использовал ни один из инструментов AI с открытым исходным кодом для этого, поэтому не могу предложить его (Хотя я слышал Рой был довольно всеобъемлющим).

текущее состояние техники с точки зрения времени запроса для статических дорожных сетей-это алгоритм маркировки хаба, предложенный 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 гиб) и быстрым временем запроса.

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

Это Google технический разговор Питера Сандерса может представлять интерес

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

также это выступление Эндрю Голдберга

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

реализация иерархий сжатия с открытым исходным кодом доступна на веб-сайте исследовательской группы Питера Сандерса в KIT. http://algo2.iti.kit.edu/english/routeplanning.php

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

Я немного удивлен, что не вижу для Floyd Warshall это упомянутые здесь. Этот алгоритм работы очень похож на Dijkstra В. Он также имеет одну очень приятную особенность, которая позволяет вычислять до тех пор, как вы хотели бы продолжать позволяя больше промежуточных вершин. Поэтому он, естественно, найдет маршруты, которые используют междугородние или автомобильные дороги довольно быстро.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для GraphHopper я решил использовать Иерархии Сужение потому что это относительно легко реализовать и никак не берите возраст для подготовки графика. Это все еще приводит к очень быстрому времени отклика, как вы можете проверить на нашем онлайн-экземпляре GraphHopper Maps. Е. Г. из Южной Африки в Восточный Китай что приводит в расстоянии 23000км и почти 14 днях управляя времени для автомобиля и принимало только ~0.1 с на сервере.

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

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

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

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

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

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

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

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

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

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

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