Быстрый алгоритм подсчета числа ациклических путей на ориентированном графе

Как упоминалось spinning_plate, эта проблема является #P-полной, поэтому начните искать свои аппроксимации :). Мне очень нравится доказательство #P-полноты для этой задачи, поэтому я думаю, что было бы неплохо поделиться им:

Пусть N-число путей (начиная сs ) в графе, а p_k-число путей длиныk . У нас есть:

N = p_1 + p_2 + ... + p_n

Теперь построим второй граф, изменив каждое ребро на пару паралельных ребер.Для каждого пути длины k теперь будет k^2 пути так:

N_2 = p_1*2 + p_2*4 + ... + p_n*(2^n)

Повторяя этот процесс, но сi ребрами вместо 2, до n, мы получим линейную систему (с матрицей Вандермонда), позволяющую найти p_1,..., p_n.

N_i = p_1*i + p_2*(i^2) + ...

Таким образом, найти число путей в графе так же трудно, как найти число путей определенной длины. В частности, p_n-это число гамильтоновых путей (начиная с s ), истинная #P-полная задача.

---

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

---

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

Важность постановки задачи

Непонятно, что подсчитывается.

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

Определите свою проблему так, чтобы не было неточности.

Оценка

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

Две Точки Оптимизации

Модель std:: bitset будет медленнее, чем значения bool для большинства процессорные архитектуры из-за механики набора команд тестирования бита при определенном смещении бита. Битовый набор более полезен, когда объем памяти, а не скорость является критическим фактором.

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

Обращение к кластерам

Задача может быть выполнена на кластере путем распределения в соответствии с начальным узлом. Некоторые проблемы просто требуют супер-вычислений. Если у вас есть 1 000 000 стартовых узлов и 10 процессоров, вы можете разместить 100 000 вариантов стартовых узлов на каждом процессоре. Вышеуказанные исключения и сокращения случаев должны быть сделаны до распределения случаев.

Типичная глубинная первая рекурсия и как ее оптимизировать

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

#include <iostream>
#include <list>

class DirectedGraph {

    private:
        int miNodes;
        std::list<int> * mnpEdges;
        bool * mpVisitedFlags;

    private:
        void initAlreadyVisited() {
            for (int i = 0; i < miNodes; ++ i)
                mpVisitedFlags[i] = false;
        }

        void recurse(int iCurrent, int iDestination,
               int path[], int index,
               std::list<std::list<int> *> * pnai) {

            mpVisitedFlags[iCurrent] = true;
            path[index ++] = iCurrent;

            if (iCurrent == iDestination) {
                auto pni = new std::list<int>;
                for (int i = 0; i < index; ++ i)
                    pni->push_back(path[i]);
                pnai->push_back(pni);

            } else {
                auto it = mnpEdges[iCurrent].begin();
                auto itBeyond = mnpEdges[iCurrent].end();
                while (it != itBeyond) {
                    if (! mpVisitedFlags[* it])
                        recurse(* it, iDestination,
                                path, index, pnai);
                    ++ it;
                }
            }

            -- index;
            mpVisitedFlags[iCurrent] = false;
        } 

    public:
        DirectedGraph(int iNodes) {
            miNodes = iNodes;
            mnpEdges = new std::list<int>[iNodes];
            mpVisitedFlags = new bool[iNodes];
        }

        ~DirectedGraph() {
            delete mpVisitedFlags;
        }

        void addEdge(int u, int v) {
            mnpEdges[u].push_back(v);
        }

        std::list<std::list<int> *> * findPaths(int iStart,
                int iDestination) {
            initAlreadyVisited();
            auto path = new int[miNodes];
            auto pnpi = new std::list<std::list<int> *>();
            recurse(iStart, iDestination, path, 0, pnpi);
            delete path;
            return pnpi;
        }
};

int main() {

    DirectedGraph dg(5);

    dg.addEdge(0, 1);
    dg.addEdge(0, 2);
    dg.addEdge(0, 3);
    dg.addEdge(1, 3);
    dg.addEdge(1, 4);
    dg.addEdge(2, 0);
    dg.addEdge(2, 1);
    dg.addEdge(4, 1);
    dg.addEdge(4, 3);

    int startingNode = 0;
    int destinationNode = 1;

    auto pnai = dg.findPaths(startingNode, destinationNode);

    std::cout
            << "Unique paths from "
            << startingNode
            << " to "
            << destinationNode
            << std::endl
            << std::endl;

    bool bFirst;
    std::list<int> * pi;
    auto it = pnai->begin();
    auto itBeyond = pnai->end();
    std::list<int>::iterator itInner;
    std::list<int>::iterator itInnerBeyond;
    while (it != itBeyond) {
        bFirst = true;
        pi = * it ++;
        itInner = pi->begin();
        itInnerBeyond = pi->end();
        while (itInner != itInnerBeyond) {
            if (bFirst)
                bFirst = false;
            else
                std::cout << ' ';
            std::cout << (* itInner ++);
        }
        std::cout << std::endl;
        delete pi;
    }

    delete pnai;

    return 0;
}