java - 有向概率图 - 减少循环的算法？

Question

考虑从第一个节点 1 遍历的有向图到一些最终节点(没有更多的出边)。图中的每条边都有一个与之相关的概率。总结所有可能的最终节点的每条可能路径的概率返回1 . (这意味着，我们保证最终会到达最终节点之一。)

如果图中不存在循环，问题将很简单。不幸的是，图中可能会出现相当复杂的循环，它可以被无限次遍历(显然，随着每次循环遍历，概率会成倍下降)。

是否有通用算法来找到到达每个最终节点的概率？

一个特别讨厌的例子:

我们可以将边表示为矩阵(从行(节点)x 到行(节点)y 的概率在条目 (x,y) 中)

{{0, 1/2, 0, 1/14, 1/14, 0, 5/14}, 
 {0, 0, 1/9, 1/2, 0, 7/18, 0}, 
 {1/8, 7/16, 0, 3/16, 1/8, 0, 1/8}, 
 {0, 1, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}}

或者作为有向图:



起始节点 1为蓝色，最终节点 5,6,7是绿色的。当从它们起源的节点开始时，所有边都用遍历它们的概率标记。

这有八条不同的路径从起始节点 1到最终节点:

{{1/14, {1, 5}}, {5/14, {1, 7}}, {7/36, {1, 2, 6}}, 
 {1/144, {1, 2, 3, 5}}, {1/144, {1, 2, 3, 7}}, 
 {1/36, {1, 4, 2, 6}}, {1/1008, {1, 4, 2, 3, 5}}, {1/1008, {1, 4, 2, 3, 7}}}

(每条路径的符号是{probability,sequence of nodes参观})

并且有五个不同的循环:

{{1/144, {2, 3, 1}}, {7/144, {3, 2}}, {1/2, {4, 2}}, 
{1/48, {3, 4, 2}}, {1/1008, {4, 2, 3, 1}}}

(循环的符号是{遍历循环一次的概率，访问的节点序列})。

如果能够解决这些循环以获得有效的树状图，则问题将得到解决。

关于如何解决这个问题的任何提示？

我熟悉 Java、C++ 和 C，因此首选这些语言的建议。

Answer 1

问题澄清

输入数据是一组 m 行 n 列概率，本质上是一个 m × n 矩阵，其中 m = n = 有向图上的顶点数。行是边缘起点，列是边缘目的地。我们将根据问题中提到的循环，该图是循环的，图中至少存在一个循环。

让我们将起始顶点定义为 s。让我们还将终端顶点定义为没有退出边的顶点，并将它们的集合定义为大小为 z 的集合 T。因此，我们有 z 组从 s 到 T 中的顶点的路线，并且由于循环 1，路线集的大小可能是无限的。在这种情况下，我们不能得出结论会在任意多的步骤中到达终端顶点。

在输入数据中，与不在 T 中的顶点对应的行的概率归一化为总计为 1.0。我们将假设马尔可夫性质，即每个顶点的概率不随时间变化。这排除了在图搜索 2 中使用概率来确定路线优先级的可能性。

有限的数学课本有时将与此问题类似的示例问题命名为醉酒随机游走，以强调步行者忘记过去的事实，
指的是马尔可夫链的无内存特性。

将概率应用于路由

到达终端顶点的概率可以表示为乘积的无穷级数和。

P_t = lim _{s -> ∞} Σ ∏ P_{i, j},

where s is the step index, t is a terminal vertex index, i ∈ [1 .. m] and j ∈ [1 .. n]

减价

当两个或多个循环相交(共享一个或多个顶点)时，分析会因涉及它们的无限模式集而变得复杂。经过对 relevant academic work的一些分析和审查后，它出现了，使用当今的数学工具获得一组准确的终端顶点到达概率可能最好使用收敛算法来完成。

一些初步的减少是可能的。

第一个考虑是枚举目标顶点，这很容易，因为相应的行的概率为零。

下一个考虑是将任何进一步的减少与学术文献所说的不可约子图区分开来。下面的深度优先算法在构建潜在路线时记住哪些顶点已经被访问过，因此可以轻松地进行改造以识别哪些顶点涉及循环。然而，建议使用现有的经过良好测试、同行评审的图库来识别和表征子图是不可约的。

图中不可约部分的数学归约可能合理，也可能不合理。考虑图中的起始顶点 A 和唯一终止顶点 B，表示为 {A->C, C->A, A->D, D->A, C->D, D->C, C->B, D->B}。

尽管可以将图简化为不存在通过顶点 A 的循环的概率关系，但如果不修改退出 C 和 D 的顶点的概率或允许退出 C 和 D 的边的概率总和更小，则无法移除顶点 A 以进一步简化比 1.0。

收敛广度优先遍历

忽略重访并允许循环的广度优先遍历可以迭代步骤索引 s，不是某个固定的 smax，而是收敛趋势中某个足够稳定和准确的点。如果循环重叠在由单个循环引起的更简单的周期性中产生 fork ，则特别需要这种方法。

Σ P_s^{Δ s}.

为了在 s 增加时建立合理的收敛，必须通过查看所有终端顶点的结果的长期趋势来确定所需的精度，作为完成收敛算法的标准和衡量精度的度量。提供一个标准可能很重要，其中终端顶点概率的总和与趋势收敛度量相结合，作为完整性检查和准确性标准。实际上，可能需要四个收敛标准 3.

每终端顶点概率趋势收敛delta

平均概率趋势收敛delta

统一的总概率收敛

总步数(出于实际计算原因限制深度)

甚至超过这四个，程序可能需要包含一个中断陷阱，允许在长时间等待后写入和随后检查输出，而不满足所有上述四个标准。

循环抗性深度优先算法示例

有比以下算法更有效的算法，但它相当容易理解，它使用 C++ -Wall 编译时没有警告，并且它为所有有限和合法的有向图以及可能的起始和目标顶点生成所需的输出 4. 很容易使用 addEdge 方法 5 以问题中给出的形式加载矩阵。

#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 route[], int index,
               std::list<std::list<int> *> * pnai) {

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

            if (iCurrent == iDestination) {
                auto pni = new std::list<int>;
                for (int i = 0; i < index; ++ i)
                    pni->push_back(route[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,
                                route, 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> *> * findRoutes(int iStart,
                int iDestination) {
            initAlreadyVisited();
            auto route = new int[miNodes];
            auto pnpi = new std::list<std::list<int> *>();
            recurse(iStart, iDestination, route, 0, pnpi);
            delete route;
            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 = 2;
    int destinationNode = 3;

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

    std::cout
            << "Unique routes 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;
}

备注

[1] 有向图算法中处理不当的循环将陷入无限循环。 (注意一个简单的情况，即 {A->B, B->A} 表示的有向图从 A 到 B 的路由数量是无穷大。)

[2] 概率有时用于减少搜索的 CPU 周期成本。在该策略中，概率是优先级队列中元规则的输入值，以减少非常繁琐的搜索(即使对于计算机)的计算挑战。生产系统中的早期文献将无导向大型搜索的指数特征称为组合爆炸。

[3] 实际上可能需要检测每个顶点的广度优先概率趋势并根据四个标准指定令人满意的收敛性

Δ(Σ∏P)t <= Δmax ∀ t

Σt=0T Δ(Σ∏P)t/T <= Δave

|ΣΣ∏P - 1| <= umax，其中 u 是最终概率总和的最大允许偏差

s < Smax

[4] 前提是有足够的计算资源来支持数据结构，并且有足够的时间来针对给定的计算系统速度得出答案。

[5] 您可以使用嵌套的两个循环来使用输入数据加载 DirectedGraph dg(7)，以遍历问题中列举的行和列。内循环的主体只是一个有条件的边添加。

if (prob != 0) dg.addEdge(i, j);

变量概率是 电话 m，n。路由存在仅与零/非零状态有关。