知识卡片
等待阈值对冲两端最坏情形
电梯未知何时到达时,先等爬楼所需的k分钟,仍未到就走楼梯。
书中示例k=10、B=300时,该策略竞争比为2,优于始终走的10与始终等的30。
优势依赖参数;如k=1,始终走的竞争比已是1。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.