知识卡片

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

缓存子问题含状态与位置

理解等级:中级

离线缓存子问题由当前缓存内容 C 和下一次请求位置 i 共同确定。

相同后续序列若起始缓存不同,最少未命中数可能不同;最优策略处理本次请求后,剩余决策仍应是新缓存状态下的最优解。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第15章《贪心算法》(OEBPS/chapter015.xhtml,文本字符[55000,60000))。 - 结论依据:15.4 节把子问题写成 (C,i):从位置 i 处理后续请求且起始缓存为 C、|C|≤k;最优子结构比较本次动作后的新状态。 - 原始内容:let’s define the subproblem ( C , i ) as processing requests for blocks b i , b i +1 , … , b n with cache configuration C at the time that the request for block b i occurs