ch4 贪心算法

说明：与《数据结构》中重叠的部分并未做笔记。

1. 硬币找零问题

【目标】根据给定的硬币面额，用最少数量的硬币支付给定的数额。

【收银员算法】每一步支付当前可支付的最大面额的硬币。

【说明】当硬币面额发生变化时，收银员算法并不一定能够得到最优解。

2. 任务调度问题

【任务描述】每个任务有一个开始时间 \(s_i\) 和一个结束时间 \(f_i\)，如果两个任务的时间没有重叠部分，称这两个任务是相容的，目标是找到最大的相容任务的集合。

【最早结束时间优先算法】按照任务结束时间升序排序。

3. 区间划分问题

【任务描述】每个讲座有一个开始时间 \(s_i\) 和一个结束时间 \(f_i\)，目标是安排最少数量的教室，使得任一时刻不存在两个讲座在同一个教室举行。

【开区间深度】所有时刻中，包含某个时刻的区间最多的数量。容易发现，上述问题的解不小于给定区间的深度。

【问题】对于区间化分问题，是否一定可以得到目标值为区间深度的安排？采用最早开始时间优先算法可以得到目标值为区间深度的安排。

4. 最小延迟问题

【任务描述】有一台生产设备，一个时刻能够处理一个工件。工件 \(i\) 需要 \(t_i\) 的加工时间，交工时间为 \(d_i\)。如果工件 \(i\) 的开始时间为 \(s_i\) 的话，那么它的结束时间为 \(f_i = s_i + t_i\)。定义工件的延迟时间为 \(l_i = \max\{0, f_i - d_i\}\)。目标是合理安排工件的加工顺序，使得工件的最大延迟时间最小。

【最早交工时间优先算法】按照工件交工时间升序排序。

【发现一】一定存在没有空闲时间的最优顺序。上述贪心算法就是没有空闲时间的算法。

【发现二】上述贪心算法不存在逆序。如果一个排序存在逆序，那么一定存在相邻的两个工件构成逆序。交换相邻的逆序工件，会减少一个逆序，但是不会增加最大的延迟。

【证明】假设 \(l\) 为交换逆序之前的延迟时间，\(l'\) 为交换逆序之后的延迟时间。对于两个工件 \(i,j\)，假设 \(i<j\)，则

• 对于除 \(i,j\) 之外的工件，交换前后延迟时间不变。
• 对于工件 \(i\)，交换之后的延迟时间不大于交换之后的延迟时间，即 \(l'_i \le l_i\)。
• 对于工件 \(j\)，\(l'_j = f'_j - d_j = f_i - d_j \le f_i - d_i \le l_i\)。

5. 贪心算法分析策略

• 证明在算法执行的每一步，所得到的解不坏于其他任何的解。
• 采用交换的方法来证明可以一步一步把一个最优解转换为贪心算法所得到的解，而不影响解的质量。
• 通过对问题结构的分析，分析解的边界，并证明算法得到的解达到了这个边界，从而是最优的。

6. 最优缓存问题

【任务描述】缓存中可以存放 \(k\) 个元素，有 \(n\) 个要访问的要求依次到达，记为 \(d_i\)。如果缓存中存在当前要访问的元素，那么我们就称为缓存命中；如果访问的元素没有被存储于缓存中，称为缓存未命中，则必须剔除已存在的某个元素，加入要访问的元素。目标是制定一个更新缓存的计划，使得剔除操作次数最少。

【最远访问优先剔除算法】剔除缓存中下一次访问需求最远的元素。