Запрос относительно алгоритма dijkstra

Я пытаюсь найти кратчайший путь между двумя узлами в наборе данных. I реализовал алгоритм dijkstra и использую его для подтверждения данных двух узлов (например: Andrew_Card и Dick_Cheney) там нет существует путь между источником и пунктом назначения. Тем не менее, я нахожу , что моя программа убивается операционной системой.Запрос относительно алгоритма dijkstra

После отладки я обнаружил, что проблема может быть связана с распределением ресурсов в ОЗУ. Что касается алгоритма Дейкстры, если число узлов, п = 16375503, то требование пространства

n*n = 16,375,503 * 16,375,503 > 10^{14}.

Для выполнения этого алгоритма в памяти мы должны, по крайней мере

(10^{14} * 4)/(1024 * 1024 * 1024) = 10^5 GB (approximately equal) 
of RAM.

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

Я реализовал программу в C++

No. ребер = 25.908.132

источник

2014-11-02 Jannat Arora

Сколько ребер имеет граф? – kraskevich

Количество ребер = 25,908,132 –

да, это очень большое число ... Но какая ошибка вы получаете. Кстати, вам нужно использовать отладчик в этом случае, чтобы узнать, что именно происходит ... – ravi

Если количество ребер относительно невелико (так что все ребра могут вписываться в основную память), вы можете просто сохранить график с помощью списка смежности. Он требует O(V + E) памяти, а не O(V^2). Кроме того, вы можете использовать алгоритм Дейкстры с приоритетной очередью. Он хорошо работает для разреженных графиков (имеет временную сложность O(E log V)). Этот подход должен отлично работать для графика с вершинами и краями около 2 * 10^7 (хорошая реализация может легко вписаться в основную память и работать не более нескольких минут).

источник

2014-11-02 20:29:26 kraskevich

Если вам нужно только расстояние между двумя узлами, использовать что-то вроде A*.

Но если вы делаете все кратчайшие пути, то вы определенно застряли в пространстве O(n^2). Вы находите ответы O(n^2) - так что вы не можете сделать ничего лучше, чем хранить их все.

источник

2014-11-02 20:27:01 Barry

A * и Dijkstra аналогичны, за исключением того, что Dijkstra не использует эвристику. A * является специализированным случаем Дейкстры, и если он использует Дийкстра, вероятность того, что допустимая эвристика недоступна. – Andersnk

Он сказал, что «O (n^2)» tho - у меня создалось впечатление, что он делал все пары. Dijkstra для только одного источника - 'O (n)' тоже. – Barry

@ AndersNK, Dijkstra - частный случай A *, а не наоборот. – avakar

С уверенностью, что ваша программа действительно исчерпала память, заверните свой call-сайт в блок try-catch и посмотрите, получаете ли вы исключение std :: bad_alloc. Пока вы не увидите исключение, которое вы ловите, не делайте предположений о том, какая часть вашей программы терпит неудачу

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

A *: * http://en.wikipedia.org/wiki/A _search_algorithm

Сужение иерархия: http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

источник

2014-11-02 20:33:08 leorex

Если он находится на Liniux, он, скорее всего, просто будет разорван убийцей OOM без исключения. –

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

источник

2014-11-02 20:56:54 Samer

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

источник

2014-11-05 06:49:41

Запрос относительно алгоритма dijkstra

ответ

Смежные вопросы