如何在有向图中找到路径的概率？

Question

我有一个有向带权图G=(V,E)。

在这个图中，边(v[i],v[j])的权重是v[i]和v[j]之间转换的次数。

我正在尝试确定完成任务的最佳方法：如何找到从节点A到节点B的概率P

所有权重都是正整数。

例如，

weight(A,B)=count of transition from A to B
weight(B,C)=count of transition from B to C
weight(B,D)=count of transition from B to D
weight(D,C)=count of transition from D to C

我们有几条路径可选：

A->B->C 
A->B->D->C

那么，如何计算这些路径的概率P并选择最优路径呢？

- Andrei

---

这里并不清楚概率应该从哪里来。你所说的“转换次数”是什么意思？又是什么让一条路径成为最佳路径？你没有给出足够清晰的问题陈述，以便我们回答这个问题。 - user2357112

例如，转移计数-从A到B的转移次数。最佳路径是具有最高概率的路径。我尝试解决这个问题：P=属于此路径的边缘权重之和。但是我有一个问题，即具有最大长度的路径将具有最大概率，但这是错误的。 - Andrei

Answer 1

这个问题可以通过将问题简化为最短路径问题来解决，假设我们确实在讨论概率（也就是说每个权重都在[0,1]范围内）。让图形为G=(V,E)，两个顶点之间的概率表示为w(u,v)。定义：w'(u,v) =-log(w(u,v))。从某个节点s到某个节点t的最短路径是使用w'作为权重函数时图中的最短路径。您可以使用Dijkstra算法或Bellman-Ford算法找到最短路径。证明如下：对于路径v1->v2->...->vn，它的概率是w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)。当使用w'作为权重时，使用任何最短路径算法计算这条路径的成本为：

d(v1,vn) = w'(v1,v2) + w'(v2,v3) + ... + w'(vn-1,vn) = 
d(v1,vn) = -log(w(v1,v2)) + -log(w(v2,v3) + ... + -log(w(vn-1,vn)) = 
d(v1,vn) = -1* [ log(w(v1,v2)) + log(w(v2,v3)) + ... + log(w(vn-1,vn)) =
d(v1,vn) = -1* log(w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)) 

这显然也适用于从s到t找到的最小路径。
这意味着该路径具有最小值:

s(s,t) = -1* log(w(s,v2) * w(v2,v3) * ... * w(vn-1,t)) 

由于对数是单调函数，因此它也是-1 * w(s,v2) * w(v2,v3) * ... * w(vn-1,t)的最小值，即w(s,v2) * w(v2,v3) * ... * w(vn-1,t)的最大值，而这正是概率。

- amit

---

这看起来相当复杂。我建议您使用数组表示法v[i]，而不是vi（实际上是v_i，这是在OP中的）。我建议添加对“对数”技巧的引用。我建议删除过度解释的行，因为它使答案看起来比实际更难。此外，我猜您假设某种独立性，这应该明确说明。 - Matsmath

@amit w'(u,v) 的值在范围[0;1]内吗？如果我有w(u,v) = 从节点u到节点v的转换计数，如何获得w'(u,v)？ - Andrei

@Andrei -log(u到v的转移次数), 此处适用于一般的 w(.,.)。 - amit

@amit，我有一个误解，现在权重如何在 [0;1] 范围内？ - Andrei

@Andrei 抱歉，自你提问以来已经过去了3个星期。你是正确的，在这种情况下，你需要将其规范化为[0,1]。一种方法是定义 w(u,v) = #从u到v的转换次数 / #从u到任何节点的转换次数，或者任何其他你能想到的标准化方法。如果没有 [0,1] 范围，这将是一个相当困难的问题，如果我没记错的话，与最长路径问题等价（NP完全问题）。 - amit