10

简而言之，我需要一种快速算法来计算简单有向图中有多少条非循环路径。

简单的图表是指没有自环或多重边的图表。路径可以从任何节点开始，并且必须在没有出边的节点上结束。如果一条路径中没有边出现两次，则该路径是非循环的。

我的图（经验数据集）只有 20-160 个节点，但是，其中一些有很多循环，因此会有非常多的路径，而我的幼稚方法对于某些图来说根本不够快我有。

我目前正在做的是使用递归函数沿着所有可能的边缘“下降”，同时跟踪我已经访问过哪些节点（并避免它们）。到目前为止，我最快的解决方案是用 C++ 编写的，并在递归函数中使用 std::bitset 参数来跟踪哪些节点已被访问（访问的节点由位 1 标记）。该程序在样本数据集上运行 1-2 分钟（取决于计算机速度）。对于其他数据集，运行需要超过一天的时间，或者显然更长。

样本数据集： http: //pastie.org/1763781 （每行是一个边对）

示例数据集的解决方案（第一个数字是我开始的节点，第二个数字是从该节点开始的路径计数，最后一个数字是总路径计数）： http: //pastie.org/1763790

如果您对更复杂的算法有想法，请告诉我。我也对近似解决方案感兴趣（用一些蒙特卡洛方法估计路径的数量）。最终我还想测量平均路径长度。

编辑：也以相同的标题发布在 MathOverflow 上，因为它可能在那里更相关。希望这不违反规则。无法链接，因为网站不允许超过 2 个链接...

4

3 回答 3

9

这似乎是#P-complete。（参考http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf）。链接有一个近似值

如果您可以放宽简单的路径要求，您可以使用修改后的 Floyd-Warshall 版本或图幂来有效地计算路径的数量。查看所有对图上的所有路径

于 2011-04-06T16:18:19.320 回答
4

正如 spin_plate 所提到的，这个问题是#P-complete，所以开始寻找你的近似值:)。我真的很喜欢这个问题的#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，将给我们一个线性系统（带有 Vandermonde 矩阵），允许我们找到 p_1，...，p_n。

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

因此，在图中找到路径的数量与找到一定长度的路径的数量一样困难。特别是，p_n 是哈密顿路径的数量（从s开始），这是一个真正的 #P 完全问题。

我没有做数学我也猜想类似的过程应该能够证明仅仅计算平均长度也很困难。

注意：大多数时候讨论这个问题的路径从单个边缘开始并停止在任何地方。这与您的问题相反，但是您应该通过反转所有边缘来等效。

于 2011-04-06T17:49:08.553 回答
0

问题陈述的重要性

目前尚不清楚计算的是什么。

  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;
}
于 2017-02-18T08:29:37.237 回答