知识卡片

普通读书笔记卡 · 3661

按高位渐进细化权重叫缩放

理解等级:中级

缩放算法先只看非负整数边权的高位,求粗略子问题,再逐步揭示更多低位并修正结果;全部位处理完才得到原权重下的正确解。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第22章 单源最短路径 · 查看原书依据

      A scaling algorithm solves a problem by initially considering only the highest-order bit of each relevant input value, such as an edge weight, assuming that these values are nonnegative integers. The algorithm then refines

    参考来源

    - 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[75000,80000))。 - 结论依据:问题22-4解释按位精化的缩放方法,并构造单源最短路实例。 - 原始内容:A scaling algorithm solves a problem by initially considering only the highest-order bit of each relevant input value, such as an edge weight, assuming that these values are nonnegative integers. The algorithm then refines