知识卡片
可靠路径可用负对数转最短路
若各边成功事件相互独立且 0≤1,路径成功概率为各边概率的乘积;将每条边权设为 −log(p),最大化概率等价于最小化非负权和,可使用Dijkstra。p=0的边代表无法成功,可视为不可用或无限成本。
若故障存在相关性,边概率之积可能不成立,应使用能够反映联合概率的模型。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
最可靠的路径很有必要。路径正确传递数据包的概率是每条边的概率之积。我们创建一个新图,每条边的概率将原图中的概率取负对数。这样,在这个新图中,最短路径就是原图中的最可靠路径。 Dijkstra算法不能够应用于有负权边的图。但是,Bellman-Ford(如图6-16和例6-6所示)可以在不存在负值环的
参考来源
- 位置:《算法技术手册》第6章《变种》(spine1578;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1541.html;u164-ch06-011)。
- 结论依据:164全文实读;独立性和零概率为使用条件补充。
- 原始内容:最可靠的路径很有必要。路径正确传递数据包的概率是每条边的概率之积。我们创建一个新图,每条边的概率将原图中的概率取负对数。这样,在这个新图中,最短路径就是原图中的最可靠路径。 Dijkstra算法不能够应用于有负权边的图。但是,Bellman-Ford(如图6-16和例6-6所示)可以在不存在负值环的