区间调度问题

600*600

所选择的贪心算法：选择的基准——每一个任务的结束时间。 伪代码：

sort jobs by their finish time so that f1 <= f2 <= ... <= fn
set A = none
for j = 1 to n:
   if j compatible with A:
      A = A union j
end for
return A

时间复杂度分析：

排序步骤——O(NlogN)
for循环中只需要比较j与最后加入A的 $j^{*}$ 是否相容即可——”开始时间>=上一个区间的结束时间“ 故for循环的时间复杂度——O(N)。
故整体复杂度为O(NlogN)

最优性的证明：

假设这个策略找到的解不是最优的。
设这个策略找到的解是 $i_{1}, i_{2}, i_{3}, ...i_{n}$ ，最优解是 $j_{1},j_{2},..,j_{m}$ 。同时有 $i_{1}=j_{1},i_{2}=j_{2},...i_{r}=j_{r}$ ,其中r为最大相同作业数。
由于 $i_{r+1}$ 是与前面r个相容，同时结束时间最早的。此时将 $j_{r+1}$ 替换为 $i_{r+1}$ 不会产生任何冲突。但此时两者重复的最大相同作业数是r+1.与之前所说的相矛盾。

区间划分问题

每个讲座开始于 $s_{j}$ ，结束于 $f_{j}$
目标：在保证没有冲突的前提下，安排最小数目的教室来安排每一个讲座。

设区间的深度：depth = 在任意给定的时间内所包括的最大间隔数目。

贪心算法： ——根据lecture的开始时间进行排序。

伪代码如下：

sort intervals by starting time so that s1 <= s2 <= ... <= sn
set d = none
for j = 1 to n:
    if (lecture j compatible to some classroom k):
       schedule j to k
    else
        allocate a new classroom d + 1
        schedule j to d + 1
        d = d + 1
end for

如何判断是否有相容教室: 对于一个新区间，需要找到最早结束的教室——堆顶元素。 1，若当前区间开始时间 >= 堆顶元素结束时间 $\rightarrow$ 复用该教室

弹出堆顶元素——O(logD)
插入新元素——O(logD) 2，若不相容，则分配新教室，插入堆中——O(logD)

每个区间最多触发两次堆的更新操作——2O(logD) = O(logD) <= O(logN)。故for循环整体的时间复杂度为O(NlogN)。 故整体算法的时间复杂度为O(NlogN).

最优性检验：

第d间教室新开的原因——前面d-1个教室都正在被占用。
前面d-1间教室中的课程，其开始时间都早于当前课程。故在其开始时间的极小区间附近，有d个课程重叠。
贪心算法的结果不超过depth d，同时最优解又必须大于等于d，故贪心为最优解。

最小延迟调度问题

贪心算法： ——排序标准：最早结束的ddl优先。

伪代码：

sort n jobs by ddl
set t = 0
for j = 1 to n :
    assign j to interval [t, t + t_j]
    s_j = t, f_j = t+ t_j
    t = t + t_j
output interval [s_j, f_j]

最优性检验：

判断——若存在一个最优方案，则其中间一定没有间隔： 若有间隔时间，则一定可以对其进行”压缩“ 贪心法得到的方案没有空闲时间。

若贪心不是最优解：则在最优解中一定存在相邻逆序对—— $d_{i} < d_{j}$ ，但j安排在i前面。

交换两者的顺序：首先i的延迟只会减小；对于j—— $lateness_{j'} = f_{j}' - d_{j} = f_{i} - d_{j} <= f_{i} - d_{i} = lateness_{i}$

贪心法最优性的证明策略

结构性证明法： 找到所有可行解都必须满足的上/下界，并证明贪心法能够正好达到这个界，因此贪心法为最优解。例如：区间划分问题——分析下界必须满足同时最多有多少门课在上。
交换论证法：
- 假设存在一个与贪心不同的最优解。
- 找到两者的差异点
- 通过交换元素的顺序，将这一方法改造为贪心法，并证明结果并没有变差
- 证明贪心解至少也和最优解一样好。
局部领先法： 贪心算法在每一步都能够执行局部最优的算法，那么最终结果一定是最优解。

最优离线缓存策略——最远将来法

离线算法： 知道未来所有访问页面的序列。

603 策略： 当缓存满且发生miss项时，驱逐缓存中“未来最晚被再次访问的元素”

降低缺失率的策略：

只在请求某个数据项时才将其加载进缓存（不会在没有请求的时候，主动把数据提前加载到缓存）

证明： 假设S在时间他将页面d加载如缓存，但此时没有对于d的请求。当加载d时，S需要淘汰某个页面c。存在两种情况：

d在下次请求前就被淘汰了：这种提前加载无意义，可以直接删除此次操作
d在下次请求前没有被淘汰： d在t’被请求，并且此期间已知留在缓存中。此时可以推迟d的加载时间，知道t‘请求发生时再加载。那么可以消除一次不必要提前加载，同时维持某些淘汰页面。

$S_{FF}$ 的最优性证明：(交换论证法)

假设在0-j时间段，S和 $S_{FF}$ 的命中和驱逐情况都相同，即缓存完全相同。
假设在j+1时刻，两者第一次发生分歧，则存在S驱逐数据e， $S_{FF}$ 驱逐数据f $\ne e$ （同时由 $S_{FF}$ 的性质可知：未来一定先访问e）
找到最小时刻j’ > j+1，两者第二次发生分歧（此时两者访问g）： (1)两者有一个命中g，另一个miss； (2)两者均miss
对于g： (1)有g = f或e：又一定先访问e，故g = e。此时可将S改造为S’，在j+1时刻驱逐e的动作改为驱逐f，此时在0j’，S‘和 $S_{FF}$ 均相同，且miss数比S少一个(访问e) (2)若g $\ne e$ 或f：依然将S改造为S’——在j+1时刻驱逐f，并在j‘时刻做出与 $S_{FF}$ 相同的动作。故S’与S的miss数一致，且S‘与 $S_{FF}$ 在0j’时刻均一致。
得到： $S_{FF}$ 的miss数不超过最优解S，因此 $S_{FF}$ 是最优的。

硬币找零问题

目标：

贪心法的最优性证明： 先设定若干变量：P——1美分；N——5美分；D——10美分；Q——25美分。可以得到，对于最优方案，存在如下的数量限制：

\begin{aligned} P <= 4\\ N <= 1\\ N+D <= 2\\ Q <= 3 \end{aligned}

考虑在区间 $c_{k} <= x < c_{k+1}$ 内进行找零，设贪心法会选择面值为 $c_{k}$ 的硬币。若任何最优解也必须选择面值为 $c_{k}$ 的硬币。若不选择，其必须用若干个面值为 $c_{1},c_{2},...,c_{k-1}$ 的硬币来凑出x

选择断点问题

从A地到B地，中间有若干个加油站，加满油能开C的距离。目标：在完成行程的前提下，加油次数越短越好。

贪心目标：在油箱耗尽之前，行驶得越远越好。

最优性证明： 设 $0 = g_{0} <g_{1}...<g_{p} = L$ 表示贪心策略选择的停靠点。设 $0 = f_{1} < f_{2} ... <f_{q}$ 表示最优方法选择的停靠点。设有 $f_{0} = g_{0},f_{1}=g_{1},...,f_{r}=g_{r}$ 。那么在贪心策略的要求下，一定有 $g_{r+1} > f_{r+1}$ . 先将 $f_{r+1}$ 换为 $g_{r+1}$ ，则后续的加油次数也不会增加，则最大相同数目变为r+1。以此类推，可以逐步将每一步都置换为贪心算法的停靠点。

聚类问题

目标：给定一个整数k，找到一个k聚类，使得簇间间距最大。

single-link-k-聚类算法： 1，初始时，将每个店看做一个独立的簇。 2，在所有属于不同簇的点对中，找到距离最近的一对点，在之间连接一条边。 3，重复上述操作n-k次。

其就等价于使用Kruskal算法，按边权从小到大加入边，生成最小生成树后，再删除最后加入的k-1条最大权重边。

最优性证明： 定义：设 $C^{*}$ 为删除MST最大k-1条边得到的聚类。 $d^{*}$ 为 $C^{*}$ 的最小间距（即被删除的第k-1大边的权值）

假设存在聚类C，其最小间距 > $d^{*}$ : 由于两者为不同的聚类，则必然存在点对(u, v)，满足：在 $c^{*}$ 中同簇，在c中异簇。由于边(u, v)没有被删除，则说明其权值 < $d^{*}$ . 则说明C的最小间距 $<= W(u, v) <= d^{*}$ 。这就与假设相矛盾。