Алгоритм Дейкстры на огромных графах

15

Я очень знаком с Dijkstra, и у меня есть конкретный вопрос об алгоритме. Если у меня есть огромный граф, например, 3,5 миллиарда узлов (все данные OpenStreetMap), то я явно не смог бы иметь граф в памяти, поэтому граф хранится на диске в базе данных.

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

Извлечение списка смежности каждой посещенной вершины потребовало бы около 1500 запросов к базе данных на 10 000 узлов согласно моим статистическим данным, так что, очевидно, это не так, как они это делают. Это было бы слишком медленно.

Как они это делают? Я пытаюсь реализовать это сам.

dimitris93
источник
2
Вы уверены, что они используют Dijkstra? Существует множество других алгоритмов кратчайшего пути, которые лучше подходят для описываемой вами ситуации.
Дэвид Ричерби
1
Вы смотрели в код? Откуда нам знать? «запросы к базе данных» - надеюсь, вы не используете СУБД для хранения графиков?
Рафаэль
@DavidRicherby да я уверен, посмотрите на эту ссылку
dimitris93
2
«Это был бы чрезвычайно утомительный процесс изучения чистого кода на языке Си». Но это единственный способ узнать, что делает код. Итак, вы просто просите нас выполнить ваше утомительное задание за вас, что не самая
лучшая
1
@Shiro Вы явно спрашиваете: «Как они это делают?» Если это не тот вопрос, который вы хотите задать, вам нужно перефразировать.
Рафаэль

Ответы:

6

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

Вы можете использовать БД, пользовательский формат файла для чтения с диска и настройки в памяти.

Но по моему опыту использование БД примерно в 5-10 раз медленнее и требует гораздо больше памяти, чем запись собственного формата файла на основе «простого» формата связанного списка.

Хорошо, что есть несколько программных сред, использующих OSM, которые имеют открытый исходный код, поэтому вы можете посмотреть прямо в код, например, см. Здесь . В движке маршрутизации с открытым исходным кодом GraphHopper очень легко переключиться с настройки отображения памяти (на основе диска) на настройку в памяти - оба в одном и том же формате. Параметр «mmap» позволяет даже использовать мобильные устройства с ограниченным объемом памяти, и последние работают намного быстрее, если у вас есть необходимый объем оперативной памяти, например, на сервере. Например, для всемирного графика (> 100 миллионов узлов) вам потребуется около 8-10 ГБ ОЗУ, плюс много ОЗУ, если вы хотите еще больше ускорить процесс, например, с помощью иерархии сжатия - примерно на 5-8 ГБ больше для каждого автомобиля, который вы хотите.

Формат очень прост и в основном хранит только те данные, которые вам нужны, с помощью нескольких приемов, чтобы сделать его компактным. Подробнее об этом читайте здесь . Отказ от ответственности: я автор GraphHopper.

Что касается других ответов:

Алгоритм Дейкстры, хотя и применим, считается неоптимальным для этой задачи

«Нормальный» Dijkstra может работать очень разумно (<1 с для запросов по всей стране, как, например, ваш узел 3mio) и является оптимальным в «теоретическом смысле», но нуждается в небольшой настройке, чтобы быстро работать в производственных сценариях. А такие методы, как Contraction Hierachies, используют его двунаправленную модификацию и работают очень хорошо.

Дорожные сети являются иерархическими и плоскими.

дорожные сети являются иерархическими только для автомобилей, а не плоскими (мосты, туннели, ...)

Karussell
источник
У меня есть еще один вопрос. Как вы находите NodeIDближайший узел из latitude/longitude? Это необходимо для расчета кратчайшего пути A-> B. Также необходимо помнить, что A и B могут не существовать как узлы, потому что не каждый квадратный метр содержит узел. Итак, нам нужно найти 2 ближайших NodeIDs A и B.
dimitris93
Это делается в LocationIndexTree, который является своего рода квадродеревом, эффективно хранящим NodeID в ячейке, которая имеет, например, для GraphHopper радиус ~ 500 м. Если ничего не найдено, радиус увеличивается до определенной степени. Это звучит просто в теории, но очень сложно, поскольку у вас могут быть ребра, пересекающие область, вам нужно быть эффективными при ее создании и запросах, а также многое другое.
Karussell
Разве KD-Trees не эффективнее при поиске ближайшего соседа? Почему вы выбрали QuadTrees вместо KD-Trees? Я внедряю KD-Trees для моего механизма маршрутизации прямо сейчас. Я начал внедрять QuadTrees, но остановился, потому что решил, что KD-Trees - это то же самое, но его легче кодировать и быстрее запрашивать ближайшего соседа. Я ошибаюсь ?
dimitris93
При использовании четырех деревьев нет необходимости явно хранить ограничивающую рамку, что дает ему преимущество в хранении, что было более критично для моего сценария использования (также я считаю, что четыре дерева проще;)). Скорость запроса не является проблемой. На самом деле кто-то изучал такие попытки, и он превосходил любые другие реализации, в том числе. KD деревья, но я предполагаю, что все зависит от конкретной реализации ...
Karussell
Если вы посмотрите на страницу 9 этого PDF- файла из Стэнфорда, для поиска ближайшего соседа в KD-Trees вам вовсе не нужно знать ограничивающие рамки. И еще одна вещь: поскольку мы заранее знаем все точки, мы можем создать сбалансированное дерево высоты logn. Вы все еще уверены в том, что дерево имеет какое-либо преимущество перед деревьями kd?
dimitris93
2

Вам не нужно помещать все ребра, которые находятся рядом, в очередь с приоритетами. «Лгите» алгоритму Дейкстры и задайте ему только самую короткую вершину v, падающую на вершину, скажем, w, извлеченную из стека. Затем, когда v извлекается из очереди, вы говорите «упс», я сделал ошибку и должен был дать вам и эту вершину, которая является ближайшей к вершине w. Легко видеть, что таким образом у вас будет правильное решение, и размер очереди резко сокращается только до одной инцидентной вершины вместо множества. Тем не менее, вам нужно отслеживать случаи, чтобы всегда указывать следующую ближайшую вершину - когда это необходимо. В одном из комментариев утверждается, что дорожные сети плоские, что неверно. Фактически, исследование показало, что они очень неплоские. Подумайте о всех автомагистралях, пересекающих мосты через город, порождающих множество неплоскостей.

user49040
источник
0

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

  • графовая структура может быть «скомпилирована» из данных списка смежности. это подход в библиотеке, которую вы цитируете , SpatiaLite. эти структуры графиков хранятся в сжатом двоичном формате, где местоположения графиков представлены двоично-кодированными целыми числами и т. д., поэтому представление и манипулирование графиком занимает гораздо меньше места, чем сохранение всех названий дорог и т. д .; Похоже, что алгоритм SpatiaLite не "онлайн" и работает полностью в памяти.

  • Есть параллельные / распределенные алгоритмы. см., например, Масштабируемый графический обход графического процессора / Merrill, Garland, Grimshaw.

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

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

  • эта (235p!) кандидатская диссертация особенно применима. Планирование маршрута в дорожных сетях / Schultes

  • некоторые алгоритмы используют многие из этих идей и других, являются высоко настроенными и запатентованными и граничат с конкурентными коммерческими секретами. например, Google. могут быть некоторые вводящие в заблуждение СМИ на эту тему. Например, Простой, Элегантный Алгоритм, который делает Карты Google возможными, который утверждает / подразумевает, что Google использует алгоритм Dijkstras без какой-либо ссылки.

ВЗН
источник
1
Карты Google, безусловно, обновились до чего-то лучшего, чем Dijskstra. Каждый компетентный разработчик на полпути использовал бы A * для дорожных карт, но на моей предыдущей работе мы выяснили, что движок Google может перепланировать 2500 км маршрутов через путевую точку за <100 мс. Это слишком быстро для A *, поэтому, вероятно, они используют что-то вроде ArcFlags.
MSalters
Ответ Каруссела оспаривает это вступительное предложение «Алгоритм Дейкстры, хотя и применимый, считается неоптимальным для этой проблемы», которое не ожидалось, что будет спорным. есть очень сильная поддержка утверждению в тезисе Шульте (в начале), который также является очень всеобъемлющим / недавним обзором области, а также объясняет «иерархические и плоские» «приближения». К сожалению, кажется, что нет никаких указаний на фактические алгоритмы Google в открытой литературе по беглому поиску.
vzn
-2

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

Например, рассмотрим следующий пример. Допустим, я пытаюсь найти степени разделения между любыми двумя актерами (число Бэкона), и я хочу найти наименее взвешенный путь (путь с использованием новейших возможных фильмов). Теперь, скажем, у меня есть функция с именем shortestPath(actor A, actor B);. Рассмотрим следующий сценарий.

Если актер A действует с 1970 года, а актер B действует с 2000 года, то, учитывая эту информацию, было бы гораздо более логичным найти путь, начиная с первого фильма актера B, а затем пройти путь к актеру A. Как в отличие от перебора всех фильмов, в которых действовал актер А.

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

РЕДАКТИРОВАТЬ: Допустим, вы пытаетесь найти кратчайший путь между 2 городами в одной и той же стране, и если эта страна длиннее, чем она шире, например, в Аргентине, то вы можете выполнять свои запросы на основе долготы и широты стран границы. Затем вы можете начать движение по вертикали (используя долготу), а не по горизонтали. Конечно, должна быть обработка исключений, но вы поймете общую идею.

Джонатан
источник
1
Как вы используете Union-Find в Дейкстре?
Рафаэль
Данные являются пространственными данными, широтой и долготой. Я думал, что это было ясно.
dimitris93