Алгоритм Дейкстры: потребление памяти

Question

Алгоритм Дейкстры: потребление памяти

У меня есть реализация алгоритма Дейкстры, основанная на коде этот сайт. По сути, у меня есть несколько узлов (скажем, 10000), и каждый узел может иметь от 1 до 3 подключений к другим узлам.

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

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

Кто-нибудь знает альтернативный способ реализации алгоритма для уменьшения объема памяти или есть другой алгоритм, который использует меньше памяти?

7

algorithm c++dijkstra memory memory-management

Решение

Другие решения

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

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

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

Например, рассмотрим пункты ниже:

.B        .C
.E
.A           .D
.F                   .G

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

Скажем, вы начинаете с D:

выберите closest points в D в пределах данного number of hops;
использовать алгоритм Дейкстры на выбранных записях, начиная с D;
использовать решение как граф с центральным узлом D и последние узлы в кратчайших путях как узлы, непосредственно связанные с D;
расширить график, повторяя алгоритм, пока все узлы не будут рассмотрены.

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

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

3

Мне очень нравится boost :: graph. Потребление памяти очень приличное (я использовал его в дорожных сетях с 10 миллионами узлов и 2 Гб оперативной памяти).

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

Некоторые люди упоминали другие алгоритмы. Я не думаю, что это сыграет большую роль в использовании памяти, но, скорее, в скорости. Узлы 2M, если топология близка к уличной сети, время работы от одного узла до всех остальных будет меньше секунды.

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html

1

Источник

Accepted Answer

Согласно вашему комментарию выше, вы представляете края графика с помощью матрица расстояний long dist[GRAPHSIZE][GRAPHSIZE], Это займет O(n^2) памяти, что слишком много для больших значений n, Это также не очень хорошее представление с точки зрения времени выполнения, когда у вас есть только небольшое количество ребер: это заставит алгоритм Дейкстры принять O(n^2) время (где n число узлов), когда оно потенциально может быть быстрее, в зависимости от используемых структур данных.

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

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

8