Есть такие работы, как Reach for A * от исследователей Microsoft и Highway Hierarchies Сандерса и Штольца (если я правильно произношу это имя) из Karlsruhe Uni . Оба они значительно уменьшают порядок вычислений и ускоряют работу в тысячи раз на больших графиках (см. Результаты в связанных документах). Последняя работа привела к созданию Open Source Routing Machine , которая, к сожалению, недостаточно популярна и не адаптирована (я не смог скомпилировать ее, хотя и старался).
В то же время, пробные базы данных, Spatialite и PgRouting, согласно их документам, предлагают только алгоритмы Dijkstra и A * . Я даже не упомянул двунаправленный поиск, который в моем опыте экономит время вычислений дважды.
Есть ли лучшие алгоритмы для баз данных или других приложений?
источник
Ответы:
Правда состоит в том, что большинство людей используют собственные варианты алгоритма A * . Вы увидите это на большинстве «больших парней» (я не могу сказать, кто они, на публичном форуме, но я могу сказать, что вы, вероятно, используете один из них - гарантировано), где модификация эвристики очень зависит от наборов данных, которые они используют.
Вы уже упоминали о pgrouting , который я бы назвал «традиционным» вариантом. Это хорошо для выполнения простых алгоритмов маршрутизации и для большинства задач. Он также прост в использовании и использует традиционную базу данных на своем бэкэнде.
Тем не менее, это действительно зависит от масштаба и типа проблемы, которую вы пытаетесь решить, а маршрутизация является проблемой графа .
Еще раз, у «больших парней» обычно есть много данных, связанных с их графиком (например, данные трафика, автобусные маршруты, пешеходные маршруты), которые влияют на алгоритм маршрутизации. Они известны как мультимодальные планировщики поездок (где у вас также есть выбор «режимов» планирования - нет велосипедных дорожек - только общественный транспорт - подобные вещи). Вы можете думать , как планирование поездки также становится время деликатного вопроса (то есть , если вы идете назад несколько ребер назад, вы сможете поймать метро , который доставит вас к месту назначения вперед гораздо быстрее , чем если бы вы просто пытались перейти края вперед используя самую низкую стоимость).
«Большие парни» не хранят свои данные в традиционной базе данных как таковые, они используют предварительно вычисленные графы (добро пожаловать в кластеры hadoop / mapreduce!). Как вы можете себе представить, эти графы становятся действительно большими, поэтому знание того, как соединить ребра смежных графов, может стать проблемой.
В любом случае, я бы порекомендовал вам взглянуть на некоторые мультимодальные проекты графа маршрутизации:
Graphserver приходит на ум. Не много документации, но много чистого кода (AFAIK, я думаю, MapQuest использует вариант этого проекта для некоторых своих продуктов маршрутизации).
Другим вариантом может быть OpenTripPlanner, за которым стоит много умных людей (включая людей из Graphserver).
источник
Не уверен, что он новее, но pgRouting имеет алгоритм Shooting-Star :
Расширение ESRI Network Analyst использует упомянутый вами иерархический подход для ограничения времени решения:
На сайте ESRI есть очень подробная техническая документация с примерами этого подхода, однако для загрузки требуется войти в систему (Иерархические маршруты в документе ArcGIS Network Analyst).
источник
Сократительная иерархия - это очень быстрый алгоритм:
Этот алгоритм дружествен к ОЗУ при выполнении запроса (для хранения сжатого графа требуется еще немного ОЗУ, а также массовая предварительная обработка)
Есть несколько других алгоритмов, включая те, которые решают маршрутизацию общественного транспорта:
Microsoft также проводит некоторые исследования:
(ну, Даниэль Деллинг тоже из Карлсруэ)
Вы можете получить хорошее представление и обзор доступных алгоритмов:
Внимание: немецкие (!) Лекции. но по крайней мере заголовки могут помочь вам получить больше информации (ALT, Arc-Flags, CHASE, ...) или прилагаемой литературы!
Обновить
GraphHopper теперь реализует иерархии сжатия, а также другие алгоритмы, вы также можете попробовать демо .
источник