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

我不是马尔可夫链领域的专家，尽管我认为算法很可能以你提出的那种问题而闻名，但我很难找到它们。

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

1. 模拟。

检查系统的状态如何随时间演变，方法是从状态 1 的系统开始，以 100% 的概率运行，然后执行多次迭代，在其中应用转换概率来计算执行步骤后获得的状态的概率。如果每个节点都可以到达至少一个最终（“吸收”）节点（非零概率），那么经过足够的步骤，系统处于最终状态以外的任何状态的概率将逐渐降低到零。您可以将系统以最终状态 S 结束的概率估计为它在 n 个步骤后处于状态 S 的概率，该估计值中的误差上限由系统在 n 步后处于非最终状态的概率给出。

实际上，计算Trⁿ也是如此，其中Tr是您的转移概率矩阵，在所有最终状态下以100%的概率增强了自边缘。

2. 精确计算。

考虑一个图表，G，如你所描述的。给定两个顶点 i 和 f，使得从 i 到 f 至少有一条路径，并且 f 除了自边缘之外没有其他传出边缘，我们可以将从 i 到 f 的路径划分为类，其特征是它们在到达 f 之前重新访问 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（n） 中的每个路径都具有两条路径 c 和 t 的并集形式，其中 c 属于 C_ii（n-1），t 属于 C_if（0）。也就是说，c 是从节点 i 开始到节点 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（0） 的 n+1 个路径的组合。因此，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_ii（0）|G))

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

特别是，设 S（i， G） 是图 G 中顶点 i 的后继集合 -- 即顶点集 s 使得在 G 中有一条从 i 到 s 的边，并设 X（G，i） 是 G 的子图，通过移除所有从 i 开始的边而形成的。此外，设 p_是与 G 中边缘 （i， s） 相关的概率。

丙（_如果（0）|G） = p 的 S（i， G） 中 s 的总和_为 * Pr（f|s，X（G，i))

换句话说，从 i 到 G 而不在两者之间重新访问 i 的情况下到达 f 的概率是 i 的所有后继者的总和，即在一个步骤中从 i 到达 s 的概率的乘积的乘积的总和，以及从 s 到 G 到达 f 而不从 i 向外遍历任何边的概率的总和。这适用于 G 中的所有 f，包括 i。

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

可能还有其他可能性。例如，我怀疑可能有一种自下而上的动态规划方法来解决问题，但我无法说服自己，图中的循环不会在那里出现不可逾越的问题。

问题澄清

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

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

在输入数据中，与不在 T 中的顶点对应的行的概率被规范化为总计 1.0。我们假设马尔可夫性质，每个顶点的概率不随时间而变化。这排除了使用概率在图形搜索 ² 中对路由进行优先级排序的可能性。

有限数学文本有时会将与这个问题类似的示例问题命名为醉酒随机行走，以强调步行者忘记过去的事实，指的是马尔可夫链的无记忆性质。

将概率应用于路由

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

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

其中 s 是步长索引，t 是终端顶点索引，i ∈ [1 .. m] 和 j ∈ [1 .. n]

减少

当两个或多个周期相交（共享一个或多个顶点）时，分析因涉及它们的无限模式集而变得复杂。在对相关学术工作进行一些分析和回顾之后，似乎使用当今的数学工具得出一组准确的终端顶点到达概率可能最好通过收敛算法来完成。

一些初始减少是可能的。

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

2. 下一个考虑因素是将任何进一步的简化与学术文献中所谓的不可约子图区分开来。以下深度优先算法会记住在构建潜在路径时已经访问过哪些顶点，因此可以轻松对其进行改造以识别循环中涉及哪些顶点。但是，建议使用现有的经过良好测试、同行评审的图库来识别和表征不可约的子图。

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

虽然可以将图简化为没有通过顶点 A 的周期的概率关系，但如果不修改顶点退出 C 和 D 的概率或允许离开 C 和 D 的边的概率总和小于 1.0，则无法删除顶点 A 以进一步减少。

收敛宽度第一遍历

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

Σ P_s^{Δ s}.

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

1. 每终端顶点概率趋势收敛增量
2. 平均概率趋势收敛增量
3. 总概率在单位上的收敛
4. 总步数（出于实际计算原因限制深度）

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

抗周期深度优先算法示例

有比以下算法更有效的算法，但它是相当容易理解的，它使用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] 实际上可能需要检测每个顶点的广度优先概率趋势，并根据四个标准指定令人满意的收敛性。

1. Δ（Σ∏P）_t <= Δ_最大值 ∀ t
2. Σ_t=0^T Δ（Σ∏P）_t / T <= Δ_ave
3. |ΣΣ∏P - 1|<= u_max，其中 u 是最终概率之和与单位的最大允许偏差
4. s < S_最大值

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

[5] 你可以使用两个嵌套的循环来加载 DirectedGraph dg（7） 和输入数据，以循环访问问题中枚举的行和列。内部循环的主体只是一个有条件的边缘加法。

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

变量概率为 P _m，n。路由存在仅与零/非零状态有关。