有向概率图 - 减少周期的算法？

Question

考虑一个有向图，它从第一个节点 1 遍历到一些最终节点（没有更多的出边）。图中的每条边都有一个与之相关的概率。将每条可能的路径通向所有可能的最终节点的概率相加 returns 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}}}

(每条路径的符号是{概率，访问节点的顺序})

并且有五个不同的循环：

{{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

我理解为以下问题：

给定每个节点上的初始分布作为向量 b 和矩阵 A，矩阵 A 存储在每个时间步长中从节点 i 跳到节点 j 的概率，有点像邻接矩阵。

那么一个时间步后的分布b_1就是A x b。两个时间步后的分布b_2为A x b_1。同样，分布 b_n 是 A^n x b.

对于 b_infinite 的近似值，我们可以执行以下操作：

Vector final_probability(Matrix A, Vector b,
    Function Vector x Vector -> Scalar distance, Scalar threshold){
    b_old = b
    b_current = A x b
    while(distance(b_old,b_current) < threshold){
        b_old = b_current
        b_current = A x b_current
    }
    return b_current
}

（为了方便，我使用了数学变量名）

换句话说，我们假设分布序列在给定阈值后很好地收敛。可能不成立，但通常会起作用。

您可能希望为其添加最大数量的迭代。

欧氏距离应该和距离一样有效。

（这使用了 Markov Chain 的概念，但更实用的解决方案）

Answer 2

我不是马尔可夫链领域的专家，虽然我认为算法可能因您提出的问题而为人所知，但我很难找到它们。

如果那个方向没有帮助，那么你可以考虑自己动手。我在这里看到至少两种不同的方法：

模拟。

检查系统状态如何随时间演变，方法是从系统处于 100% 概率的状态 1 开始，并执行多次迭代，在迭代中应用转移概率来计算在采取步。如果至少可以从每个节点（以 non-zero 概率）到达一个最终（"absorbing"）节点，那么经过足够多的步骤后，系统处于非最终状态的概率将逐渐降低趋向于零。您可以估计系统以最终状态 S 结束的概率作为它在 n 步骤后处于状态 S 的概率，该估计的误差上限由概率给出在 n 步后系统处于 non-final 状态。

作为实际问题，这与计算 Trⁿ 相同，其中Tr 是您的转移概率矩阵，用 self-edges 对所有最终状态以 100% 的概率进行扩充。

精确计算。

考虑一个图 G，如您所描述的。给定两个顶点 i 和 f，这样至少有一条路径从 i 到 f，而f除self-edges外没有出边，我们可以从i[=241=分割路径] 到 f 到类的特征是他们在到达 f[=241 之前重访 i 的次数=].这样的类可能有无数个，我将其指定为C_if (n)，其中n表示路径在C中的次数_if(n) 重新访问节点 i。特别地，C_ii(0) 包含 G 中包含 i（澄清：以及其他路径）。

给定系统从节点 i 开始遍历图 G，在节点 f 结束的总概率由

Pr(f|i, G) = Pr(C_if(0)|G) + Pr(C_if(1)|G) + Pr(C_if (2)|G) ...

现在观察如果 n > 0 那么 C_{if[= 中的每个路径259=]}(n) 具有两条路径 c 和 t[= 并集的形式243=]，其中c属于C_ii (n-1)和t属于C_如果(0)。即c是一条从节点i开始，到节点i结束的路径，经过i n-1次之间，而t是从i 到 f 不会再次通过 i。我们可以用它来重写我们的概率公式：

Pr(f|i,G) = Pr(C_if(0)|G) + Pr(C_ii(0)|G) * Pr(C_if (0)|G) + Pr(C_ii(1)|G) * Pr( C_if(0)|G) + ...

但是请注意C_ii(n中的每条路径)是属于C_{ii[=的n+1条路径的组合259=]}(0)。由此得出 Pr(C_ii(n) |G) = Pr(C_ii(0)|G)ⁿ⁺¹,所以我们得到

Pr(f|i) = Pr(C _if(0)|G) + Pr(C_ii(0)|G) * Pr(C_if(0 )|G) + Pr(C_ii(0)|G)² * Pr(C_if(0)|G) + .. .

现在，一点点代数给了我们

Pr(f|i,G) - Pr(C_if(0)|G) = Pr(C_ii(0)|G) * Pr(f|i,G)

，我们可以求解Pr(f|i,G)得到

Pr(f|i,G) = Pr(C_if(0)|G) / (1 - Pr(C_一世(0)|G))

因此，我们已经将问题减少到一个问题，即不 return 到起始节点的路径，除了可能作为它们的结束节点。这些并不排除具有不包含起始节点的循环的路径，但是我们仍然可以根据原始问题的几个实例重写这个问题，在原始图的子图上计算。

特别地，让 S(i, G) 是顶点 i[= 的后继集合图 G 中的 241=] -- 即顶点集 s 使得存在从 i 到 的边G中的s，设X(G,i)为G的子图，去掉所有从i[=241=开始的边形成的子图].此外，让 p_is 是与边缘相关的概率 (i, s ) 在 G.

Pr(C_if(0)|G) = 求和 s S(i, G) p_是 * Pr(f|s,X(G,i))

换句话说，从i通过G到达f的概率，而不需要重新访问i 中间是i的所有后继者从i[=241=达到s的概率乘积的总和=] 在一步中有概率从 s 通过 G 到达 f 而无需从 i[=241 出站遍历任何边缘=].这适用于 G 中的所有 f，包括 i.

现在观察 S(i, G) 和所有 p_是是已知的，计算Pr(f|s,X(G,i)) 是原始问题的一个新的、更小的实例。因此，可以递归地执行此计算，并且保证这样的递归终止。如果你的图很复杂，它可能仍然需要很长时间，而且看起来这种递归方法的简单实现会在节点数量上呈指数级增长。有一些方法可以加快计算速度以换取更高的内存使用量（即记忆）。

可能还有其他可能性。例如，我怀疑可能存在 bottom-up 动态编程方法来解决问题，但我无法说服自己图中的循环不会在那里出现无法解决的问题。

Answer 3

问题说明

输入数据是一组 m 行 n 列概率，本质上是一个 m x n 矩阵，其中 m = n = 有向图上的顶点数。行是边的起点，列是边的终点。我们会根据题中提到的循环，判断图是循环的，图中至少存在一个循环。

让我们将起始顶点定义为s。我们也将终端顶点定义为没有退出边的顶点，并将它们的集合定义为大小为 z 的集合 T。因此我们有 z 组从 s 到 T 中的顶点的路径，并且由于循环 ¹，集合大小可能是无限的。在这种情况下，无法断定将以任意多的步数到达终端顶点。

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

有限数学教科书有时将类似于此问题的示例问题命名为 醉酒随机游走 以强调步行者忘记过去的事实，指的是马尔可夫链的 memory-free 性质。

将概率应用于路线

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

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 进行一些分析和审查之后，使用当今的数学工具得出一组准确的终端顶点到达概率最好使用收敛算法来完成。

初步减少一些是可能的。

首先考虑的是枚举目标顶点，这很容易，因为对应的行的概率为零。
下一个考虑是将任何进一步的减少与学术文献中所谓的不可减少的东西区分开来 sub-graphs。下面的深度优先算法在构建潜在路径时会记住哪些顶点已经被访问过，因此可以很容易地对其进行改造以识别循环中涉及的顶点。然而，建议使用现有的经过良好测试、同行评审的图形库来识别和表征 sub-graphs 不可约。

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

虽然可以将图简化为不存在通过顶点 A 的循环的概率关系，但是如果不修改顶点退出 C 和 D 的概率或允许边退出 C 的概率的总和，则无法删除顶点 A 以进一步简化D 小于 1.0.

收敛广度优先遍历

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

Σ P_s^{Δ s}.

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

每个终端顶点概率趋势收敛增量
平均概率趋势收敛增量
总概率收敛于 1
总步数（出于实际计算原因限制深度）

即使超出这四个条件，程序也可能需要包含一个中断陷阱，允许在长时间等待后不满足上述所有四个条件的情况下写入和随后检查输出。

抗循环深度优先算法示例

有比以下算法更有效的算法，但它相当容易理解，它可以在没有警告的情况下使用 C++ -Wall 进行编译，并为所有有限和合法生成所需的输出吃了有向图和可能的起点和终点顶点 ⁴。使用 addEdge 方法 ⁵.

很容易以问题中给出的形式加载矩阵

#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=0^T Δ(Σ∞P)_t / T < = Δ_平均
|Σ Σ‖P - 1| <= u_max，其中 u 是最终概率之和的最大允许偏差
s < S_max

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

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

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

可变概率为 P _m,n。路由存在只与zero/nonzero状态有关。

Answer 4

我在研究有向循环图时发现了这个问题。可以使用吸收马尔可夫链.

计算到达每个最终节点的概率

视频 Markov Chains - Part 7（+ 第 8 和第 9 部分）解释了马尔可夫链中的吸收状态及其背后的数学原理。

有向概率图 - 减少周期的算法？

Directed probability graph - algorithm to reduce cycles?

c

c++

java

directed-graph

markov-chains