使用Python查找最大概率路径的程序

假设我们有一个具有n个节点的无向加权图（节点编号从0开始）。此图使用边列表作为输入给出，对于每条边e，它都有一个遍历该边的成功概率probability[e]。我们还有起始节点和结束节点，我们必须找到从起始节点到结束节点的成功概率最大的路径，并返回其成功概率。如果找不到任何路径，则返回0。

因此，如果输入类似于：

则输出将为0.24，因为从节点0到2有两条路径，一条概率为0.2，另一条通过节点1，概率为0.4*0.6 = 0.24，这是最大值。

为了解决这个问题，我们将遵循以下步骤：

  • g := 从给定的边列表创建图，并使用概率值作为权重

  • q := 一个队列数据结构

  • 将(start, 1)插入q

  • visited := 一个映射，用于保存已访问的节点

  • 当q不为空时，执行以下操作：

    • (node, prob) := q的第一个项目，并将其从q中删除

    • 如果visited[node] > prob，则

      • 进入下一次迭代

    • 否则，

      • visited[node] := prob

    • 对于g[node]中的每个相邻节点adj和概率nextProb，执行以下操作：

      • 如果visited[adj] < prob * nextProb，则

        • 将(adj, prob * nextProb)插入q的末尾

  • 返回visited[end]

让我们看看下面的实现，以便更好地理解：

示例

 在线演示

from collections import defaultdict, deque
def solve(edges, probability, start, end):
   g = defaultdict(list)
   for i in range(len(edges)):
      src, dst = edges[i][0], edges[i][1]
      prob = probability[i]
      g[src].append((dst, prob))
      g[dst].append((src, prob))
   q = deque()
   q.append((start, 1))
   visited = defaultdict(int)
   while q:
      node, prob = q.popleft()
      if visited[node] > prob:
         continue
      else:
         visited[node] = prob
      for adj, nextProb in g[node]:
         if visited[adj] < prob * nextProb:
            q.append((adj, prob * nextProb))
   return visited[end]
edges = [[0,1],[1,2],[0,2]]
probability = [0.5,0.5,0.2]
start = 0
end = 2
print(solve(edges, probability, start, end))

输入

[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2

输出

0.25

更新于：2021年5月29日

428 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告