Самая быстрая реализация для всех пар кратчайших путей? - PullRequest
Новая
       8

Самая быстрая реализация для всех пар кратчайших путей?

7 голосов
/ 23 августа 2011

У меня есть взвешенный граф 30k узлов 160k ребер, без отрицательных весов.Я хотел бы вычислить все кратчайшие пути от всех узлов до других.Я думаю, что не могу допустить, чтобы какая-то конкретная эвристика упростила проблему.

Я пытался использовать эту реализацию Dijkstra C http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/,, которая предназначена для одной задачи кратчайшего пути, вызывая функцию dijkstras () для всехмои 30 узлов.Как вы можете себе представить, это занимает много времени.В настоящее время у меня нет времени самостоятельно писать и отлаживать код, я должен как можно быстрее вычислить эти пути и сохранить их в базе данных, поэтому я ищу другое быстрое решение, готовое к использованию.какие-либо советы?

Мне нужно запустить его на последнем MacBook Pro с оперативной памятью 8 ГБ, и я хотел бы найти решение, для завершения которого требуется не более 24 часов.

Спасибомного заранее !!

Eugenio

Ответы [ 5 ]

13 голосов
/ 24 августа 2011

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

mini = -1;
for (i = 1; i <= n; ++i)
    if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
         mini = i;

Поскольку этот код вложен в цикл, который посещает каждый узел, сложность (как упомянуто в ссылке)O (| V | 2 ), где | V |это количество узлов.В вашем случае, так как | V |составляет 30000, будет девятьсот миллионов итераций этого цикла в целом.Это мучительно медленно (как вы уже видели), но нет необходимости делать такую ​​большую работу.

Здесь есть еще одна проблема, которая пытается найти, какое ребро на графике следует использовать для уменьшениястоимость других узлов: 

for (i = 1; i <= n; ++i)
   if (dist[mini][i])
       if (d[mini] + dist[mini][i] < d[i])
           d[i] = d[mini] + dist[mini][i];

Это сканирует всю строку в матрице смежности в поисках узлов для рассмотрения, что занимает время O (n) независимо от того, сколько исходящих ребер покидает узел.

Хотя вы можете попытаться исправить эту версию Dijkstra в более оптимизированной реализации, я думаю, что правильный вариант здесь - просто выбросить этот код и найти лучшую реализацию алгоритма Dijkstra.Например, если вы используете псевдокод из статьи Википедии , реализованный с помощью двоичной кучи , вы можете получить алгоритм Дейкстры, работающий в O (| E | log | V |).В вашем случае это значение составляет чуть более двух миллионов, что примерно в 450 раз быстрее, чем ваш текущий подход.Это огромная разница, и я готов поспорить, что с лучшей реализацией Dijkstra вы в конечном итоге получите код, выполняющийся за значительно более короткое время, чем раньше.

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

Если вы планируете запускать этот алгоритм на гораздо более плотном наборе данных (таком, где число ребер приближается к | V| 2 / log | V |), тогда вы можете рассмотреть возможность перехода на алгоритм Floyd-Warshall .Запуск алгоритма Дейкстры один раз на узел (иногда называемый алгоритм Джонсона ) занимает время O (| V || E | log | V |), а использование Флойд-Варшалла - O (| V | 3) время.Тем не менее, для набора данных, о котором вы упомянули, график достаточно разрежен, чтобы нормально работать с несколькими экземплярами Дейкстры.

Надеюсь, это поможет!

3 голосов
/ 23 августа 2011

Как насчет алгоритма Флойд-Варшалла ?

2 голосов
/ 23 августа 2011

Есть ли у вашего графика особая структура? График плоский (или почти такой)?

Я бы порекомендовал не пытаться хранить все кратчайшие пути, довольно плотная кодировка (30k ^ 2 «куда идти дальше») займет 7 гигабайт памяти.

Что такое приложение? Вы уверены, что выполнение двунаправленной Dijkstra (или A *, если у вас есть эвристика) не будет достаточно быстрым, когда вам нужно найти конкретный кратчайший путь?

0 голосов
/ 24 августа 2014

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

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

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

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

Для алгоритмов кратчайшего пути я всегда выбирал C ++. Не должно быть никаких причин, по которым реализация C не была бы слишком простой, но C ++ предлагает сокращенное кодирование с контейнерами STL, которые можно использовать в начальной реализации, и только позже реализует оптимизированный алгоритм очереди, если тесты производительности и профилирование показывают, что нужно что-то иметь. лучше, чем предлагает STL. 

#include <queue>
#include "vertex.h"

class vertex;
class edge;

class searchnode {
    vertex *dst;
    unsigned long dist;
    public:
    searchnode(vertex *destination, unsigned long distance) :
        dst(dst),
        dist(distance)
    {
    }

    bool operator<(const searchnode &b) const {
        /* std::priority_queue stores largest value at top */
        return dist > b.dist;
    }

    vertex *dst() const { return dst; }

    unsigned long travelDistance() const { return dist; }
};


static void dijkstra(vertex *src, vertex *dst)
{
    std::priority_queue<searchnode> queue;

    searchnode start(src, 0);
    queue.push(start);

    while (!queue.empty()) {
        searchnode cur = queue.top();
        queue.pop();

        if (cur.travelDistance() >= cur.dst()->distance())
            continue;

        cur.dst()->setDistance(cur.travelDistance());
        edge *eiter;
        for (eiter = cur.dst()->begin(); eiter != cur.dst()->end(); eiter++) {
            unsigned nextDist = cur.dist() + eiter->cost();

            if (nextDist >= eiter->otherVertex())
                continue;

            either->otherVertex()->setDistance(nextdist + 1);

            searchnode toadd(eiter->othervertex(), nextDist);
            queue.push(toadd);
        }
    }
}
0 голосов
/ 23 августа 2011

Если вы можете изменить алгоритм, чтобы он был многопоточным, вы могли бы завершить его менее чем за 24 часа.

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

...