知识卡片

普通读书笔记卡 · 5654.d.1.f.4.j · 生成模型:未记录

可靠路径可用负对数转最短路

理解等级:中级

若各边成功事件相互独立且 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所示)可以在不存在负值环的