A * Алгоритм для очень больших графиков, есть мысли по поводу кеширования ярлыков?

Я пишу симулятор курьера /логистики на картах OpenStreetMap и понял, что базовый алгоритм A *, как показано ниже, не будет достаточно быстрым для больших карт (таких как Большой Лондон).

http://i.imgur.com/u2tVpML.jpg

Зеленые узлы соответствуют тем, которые были помещены в открытую очередь /очередь приоритетов, и из-за огромного количества (вся карта примерно 1-2 миллиона), чтобы найти изображенный маршрут, требуется около 5 секунд. К сожалению, 100 мс на маршрут - это мой абсолютный предел.

В настоящее время узлы хранятся как в списке смежности, так и в пространственном двумерном массиве 100x100.

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

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

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

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

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

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

65 голосов | спросил drspa44 15 PMpWed, 15 Apr 2015 20:32:01 +030032Wednesday 2015, 20:32:01

9 ответов


0

Вы должны быть в состоянии сделать это намного быстрее, обмениваясь оптимальностью. См. Допустимость и оптимальность в Википедии.

Идея состоит в том, чтобы использовать значение epsilon, которое приведет к решению не хуже, чем 1 + epsilon кратное оптимальному пути, но это приведет к тому, что алгоритм будет учитывать меньше узлов. Обратите внимание, что это не означает, что возвращаемое решение всегда будет 1 + epsilon кратным оптимальному пути. Это просто худший случай. Я не знаю точно, как это будет вести себя на практике для вашей проблемы, но я думаю, что это стоит изучить.

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

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

ответил IVlad 15 PMpWed, 15 Apr 2015 20:51:21 +030051Wednesday 2015, 20:51:21
0

Существуют специальные алгоритмы для этой задачи, которые выполняют много предварительных вычислений. По памяти предварительное вычисление добавляет к графику информацию, которую A * использует для получения гораздо более точной эвристики, чем расстояние по прямой линии. Википедия приводит названия ряда методов в http://en.wikipedia.org/wiki/Shortest_path_problem #Road_networks и говорит, что Hub Labeling является лидером. Быстрый поиск по этому вопросу приводит к http://research.microsoft.com/pubs/142356 /HL-TR.pdf . Более старый, использующий A *, находится по адресу http://research.microsoft. .com /Пабы /64505 /Goldberg-SP-wea07.pdf .

Вам действительно нужно использовать Haversine? Чтобы покрыть Лондон, я бы подумал, что вы могли бы предположить, что у вас плоская земля и использовать Пифагора, или сохранить длину каждой ссылки в графе.

ответил mcdowella 15 PMpWed, 15 Apr 2015 21:05:12 +030005Wednesday 2015, 21:05:12
0

Есть действительно замечательная статья, которую Microsoft Research написала на эту тему:

http://research.microsoft.com/en- нас /новости /характеристики /shortestpath-070709.aspx

Оригинал статьи размещен здесь (PDF):

http://www.cc .gatech.edu /~ Тад /6601-gradAI-fall2012 /02-розыскная-Gutman04siam.pdf

По сути, есть несколько вещей, которые вы можете попробовать:

  1. Начните как с источника, так и с места назначения. Это помогает минимизировать количество потраченной впустую работы, которую вы выполняете при переходе от источника к месту назначения.
  2. Используйте ориентиры и шоссе. По сути, найдите некоторые позиции на каждой карте, которые обычно являются траекториями, и проведите предварительный расчет, чтобы определить, как эффективно перемещаться между этими точками. Если вы можете найти путь от источника до ориентира, затем до других ориентиров, а затем до пункта назначения, вы сможете быстро найти жизнеспособный маршрут и оптимизировать его оттуда.
  3. Исследуйте алгоритмы, такие как алгоритм "досягаемости". Это помогает минимизировать объем работы, которую вы будете выполнять при обходе графа, путем минимизации количества вершин, которые необходимо учитывать, чтобы найти правильный маршрут.
ответил mattbasta 15 PMpWed, 15 Apr 2015 21:05:26 +030005Wednesday 2015, 21:05:26
0

GraphHopper делает еще две вещи, чтобы получить быструю, неэвристическую и гибкую маршрутизацию (примечание: я автор и Вы можете попробовать это онлайн здесь )

  1. Не столь очевидная оптимизация - избегать отображения 1: 1 узлов OSM на внутренние узлы. Вместо этого GraphHopper использует только узлы в качестве узлов и сохраняет примерно 1/8 пройденного узла.
  2. Имеет эффективные инструменты для A *, Dijkstra или, например, один ко многим Дейкстра. Что делает возможным маршрут до 1 секунды по всей Германии. (Не эвристическая) двунаправленная версия A * делает это еще быстрее.

Так что должна быть возможность быстро добраться до большого Лондона.

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

ответил Karussell 16 AMpThu, 16 Apr 2015 10:11:50 +030011Thursday 2015, 10:11:50
0

Я думаю, что стоит проработать вашу идею с "квадрантами". Точнее, я бы назвал это поиском маршрута с низким разрешением.

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

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

Это также может быть распространено на несколько разрешений, а не только на высокое /низкое.

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

ответил valdo 15 PMpWed, 15 Apr 2015 21:25:09 +030025Wednesday 2015, 21:25:09
0

Здесь есть десятки вариантов A *, которые могут соответствовать всем требованиям. Вы должны подумать о своих случаях использования.

  • Вы ограничены в памяти (а также в кеше)?
  • Можете ли вы распараллелить поиск?
  • Будет ли ваша реализация алгоритма использоваться только в одном месте (например, в Большом Лондоне, а не в Нью-Йорке, Мумбае или где-либо еще)?

У нас нет возможности узнать все подробности, которые вы и ваш работодатель имеете в виду. Таким образом, ваша первая остановка должна быть CiteSeer или Google Scholar: ищите документы, которые относятся к поиску пути с тем же общим набором ограничения, как вы.

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

Как уже было сказано, из-за небольшого масштаба удаления целевой области Haversine, вероятно, является вашим первым шагом, экономящим драгоценное время на дорогих оценках триггеров. ПРИМЕЧАНИЕ: я не рекомендую использовать евклидово расстояние в координатах широта /долгота - перепроецируйте вашу карту, например, в. Поперечный Меркатор около центра и используйте декартовы координаты в ярдах или метрах!

Предварительные вычисления являются вторым, и изменение компиляторов может быть очевидной третьей идеей (переключитесь на C или C ++ - см. https://benchmarksgame.alioth.debian.org/ для получения подробной информации).

Дополнительные этапы оптимизации могут включать в себя избавление от динамического выделения памяти и использование эффективной индексации для поиска среди узлов (представьте R-дерево и его производные /альтернативы).

ответил Deer Hunter 15 PMpWed, 15 Apr 2015 22:15:16 +030015Wednesday 2015, 22:15:16
0

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

Во-первых, A * полностью устарела. Его главное преимущество в том, что он «технически» не требует предварительной обработки. На практике вам все равно нужно предварительно обработать карту OSM, так что это бессмысленное преимущество.

Основной прием, который даст вам огромный прирост скорости - это флаги дуги. Если вы разделите карту, скажем, на 5x6 разделов, вы можете выделить 1 битную позицию в 32-битном целом числе для каждого раздела. Теперь вы можете определить для каждого ребра, будет ли он полезен при переходе в раздел {X,Y} из другого раздела. Довольно часто дороги являются двунаправленными, и это означает, что полезно только одно из двух направлений. Таким образом, в одном из двух направлений этот бит установлен, а в другом - очищен. Это может показаться нереальным преимуществом, но это означает, что на многих перекрестках вы уменьшаете количество вариантов для рассмотрения с 2 до всего 1, и для этого требуется всего лишь одна битовая операция.

ответил MSalters 16 AMpThu, 16 Apr 2015 11:53:34 +030053Thursday 2015, 11:53:34
0

Обычно A * сопровождается слишком большим потреблением памяти, а не временем.

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

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

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

ответил xuma202 22 PMpWed, 22 Apr 2015 19:33:42 +030033Wednesday 2015, 19:33:42
0

Старый вопрос, но пока:

Попробуйте использовать разные кучи "бинарной кучи". «Лучшая асимптотическая куча сложности» - определенно куча Фибоначчи, и ее вики-страница получила хороший обзор:

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

Обратите внимание, что двоичная куча имеет более простой код и реализована поверх массива, а обход массива предсказуем, поэтому современный процессор выполняет операции двоичной кучи намного быстрее.

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

Этот вопрос кажется достаточно большим.

ответил user1928750 8 J000000Saturday17 2017, 15:13:23

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132