知识卡片

普通读书笔记卡 · 3676.a.1.a

等待阈值对冲两端最坏情形

理解等级:高级

电梯未知何时到达时,先等爬楼所需的k分钟,仍未到就走楼梯。

书中示例k=10、B=300时,该策略竞争比为2,优于始终走的10与始终等的30。

优势依赖参数;如k=1,始终走的竞争比已是1。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第27章 在线算法 · 查看原书依据

      Hence, the algorithm “always take the stairs” has competitive ratio k, and the algorithm “always take the elevator” has competitive ratio B/k. Because we prefer the algorithm with smaller competitive ratio, if k = 10 and B = 300, we prefer “always take the stairs,” with competitive ratio 10, over “always take the elevator,” with competitive ratio 30.

    参考来源

    - 位置:《算法导论(第4版)》第27章《在线算法》(OEBPS/chapter027.xhtml,文本字符[5000,10000))。 - 结论依据:第27章电梯示例明确给出始终走的竞争比 k、始终等的 B/k,以及 k=10、B=300 的比较;图 `OEBPS/images/Art_P846.jpg` 给出等待阈值策略耗时,`Art_P847.jpg` 给出竞争比 2。k=1 的比较由原文竞争比式直接得到。 - 公式图核读:h(m)=m+1(m≤k),否则 h(m)=2k;本书示例中阈值策略竞争比为2。 - 原始内容:Hence, the algorithm “always take the stairs” has competitive ratio k , and the algorithm “always take the elevator” has competitive ratio B / k . Because we prefer the algorithm with smaller competitive ratio, if k = 10 and B = 300, we prefer “always take the stairs,” with competitive ratio 10, over “always take the elevator,” with competitive ratio 30.