pathfinding - а*algorithm




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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

youtube.com/watch?v=-0ErpE8tQbw

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

http://tom.mapsforge.org/


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

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

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


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

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


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

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


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

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

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


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

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

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

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


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

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


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

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

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

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

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

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


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

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

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

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


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





mapping