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

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

(每个路径的符号是{概率,访问的节点序列})

并且有五个不同的循环:

{{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 中的顶点的路径，并且由于循环¹，集合大小可能是无限的。在这种情况下，我们不能得出结论：在任意多的步骤中都会到达终端顶点。

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

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

将概率应用于路由

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

P _t = lim _{s -> ∞} Σ ∏ P _{i, j} ,

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

减少

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

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

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

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

图中不可约部分的数学归约可能合理，也可能不合理。考虑图中的起始顶点 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，不是某个固定的 s_最大值，而是收敛趋势中某个足够稳定和准确的点。如果循环重叠在由单个循环引起的更简单的周期性中产生分叉，则特别需要这种方法。

Σ P _s ^{Δ s}。

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

1. 每终端顶点概率趋势收敛delta
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 <= Δ _max ∀ 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);

变量 prob 是P _m,n。路由存在仅与零/非零状态有关。

Answer 2

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

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

1. 模拟。

通过以 100% 的概率从处于状态 1 的系统开始，并执行多次迭代，在其中应用转移概率来计算采取步骤后获得的状态的概率，从而检查系统的状态如何随时间演变。如果可以从每个节点（以非零概率）到达至少一个最终（“吸收”）节点，那么经过足够多的步骤，系统处于最终状态以外的任何其他状态的概率将逐渐减少到零。您可以将系统以最终状态 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 ) 中的路径重访节点的次数我。特别是，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)。也就是说，Ç是路径在节点开始我并且在节点两端我，通过我 Ñ -1之间的时间，并且吨是从路径我到˚F不通过我再次。我们可以用它来重写我们的概率公式：

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) ^{n +1}，所以我们得到

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 )相关的概率。

PR（Ç_如果（0）| G）=萨姆在小号在小号（我，G）的p_是* PR（˚F | s ^，X（G，我））

换言之，在到达的概率˚F从我至G而不重新访问我在之间是求和的所有后继我到达的概率的乘积的小号从我在一个步骤中与到达的概率˚F从小号至G无需遍历从i出站的任何边。这适用于 G 中的所有f，包括i。

现在观察到小号（我，G）和所有p _IS是的已知，以及在计算PR（问题˚F | s ^，X（G，我））是原问题的一个新的，严格较小的实例。因此，该计算可以递归执行，并且保证这样的递归终止。然而，如果您的图很复杂，它可能需要很长时间，而且这种递归方法的简单实现看起来会在节点数量上呈指数级增长。有一些方法可以加速计算以换取更高的内存使用率（即记忆）。

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