贪心算法总结 Greedy Algorithms

2021-03-03 本文已影响0人葵sunshine

贪心算法在每步取得局部最优解

1. Interval scheduling

1.1 问题描述

Interval scheduling 问题描述

目标：在没有工作冲突的情况下兼容最多的工作数;
工作 $j$ 的起始时间为 $s_j$ ，结束时间为 $f_j$ .

1.2 问题分析

Greedy template: 1. 对任务按某种规则排序；2. 根据已排好序的任务列表选择排序位置最靠前且不冲突的任务。
可以有如下4种排序方法：

起始时间增序

Counterexample for earliest start time

有如上反例，若按start time，最多工作数为1，但实际情况为4，故不可行；
结束时间增序；
interval length工作时长 $f_j - s_j$ 增序；
Counterexample for shortest interval
有如上反例，最多工作数为1，但实际为2，故不可行；
最少冲突工作数增序
Counterexample for fewest conflicts
有如上反例，深灰色工作冲突数为2，第一排浅灰色冲突数为3，最多工作数为3，但实际为4，故不可行。
$\therefore$ 将工作按结束时间排序，依次选取与前面不冲突的工作。
Interval scheduling pseudocode
时间复杂度：排序是O(logn)，for循环O(n), $\therefore$ O(nlogn)

1.3 证明最优

Proof of optimality

反证法：
假设贪心不是最优解：

令 $i_1,i_2,..i_k$ 是按贪心算法选择的工作序列；
令 $j_1,j_2,...,j_m$ 是最优解序列且前 $r$ 项工作与贪心序列相同；
因为贪心序列是按结束时间排序的，现假设最优解O与贪心解A不同，故有 $f_{i_{r+1}} \leq f_{j_{r+1}}$ ；
将 $j_{r+1}$ 替换为 $i_{r+1}$ ,构造最优解O'，即将第 $i+1$ 个工作提前了，与前后工作都没有重叠，它也是最优解，因为最大工作数没变；
至此，我们证明了一个与A更接近的最优解O‘，它在前 $r+1$ 个工作上都与A一样，与前提最多只有前 $r$ 项相同矛盾，故A是最优解。

2. Scheduling to Minimize Lateness

2.1 问题描述

Scheduling to Minimize Lateness 问题描述

目标：每项任务有需要的时间 $t_j$ 和ddl $d_j$ ，记所有任务中迟交最长的时间为 $l_j = max{0, f_j - d_j}$ ，最小化 $L = max l_j$ 。
e.g. 上图中return结果为6

2.2 问题分析

先考虑如何排序

所需时间 $t_j$ 增序
counterexample for short processing time first
有如上反例，job1无迟交，job2迟交1， $\therefore$ return 1;实际上若交换两个工作位置，return 0；
ddl时间 $d_j$ 增序
最迟开始时间 $d_j-t_j$ 增序
counterexample for smallest slack
$\therefore$ 将工作按ddl时间增序
Sort jobs by deadline

2.3 证明最优

Exchange argument:通过交换元素将最优解转换为贪心解，但还保持最优性

Minimizing Lateness: Inversions

一个inversion定义为一对工作 $i$ 和 $j$ ， $d_i<d_j$ 但 $j$ 却排在 $i$ 之前；
Observation1:因为贪心解按ddl时间点排序，所以贪心解不存在inversion;
Observation3:如果存在inversion,必然存在相邻的两个工作存在inversion.

有结论：交换相邻的一对inverted jobs，并不会增大最大迟交时间。
证明：
交换后，若最大迟交时间增大，只可能是因为 $j$ ，因为 $job_i$ 提前了， $job_j$ 延后了。
令 $l$ 为交换前的最大迟交之间， $l'$ 为交换后的
$l'_k = l_k （k \neq i, j）$
$l^{'}_i \leq l_i$
如果 $job_j$ 迟交了，有
Proof of inversions
$\therefore$ $l^{'}_j \leq l_i \leq l$ ，即最大迟交时间不变
下面证明贪心法最优：
反证法：
假设S*是最优解，且有最少的inversions (即构造了和贪心解最像的最优解）
若S* 没有inversions,S* = A;
若S*有inversions, 令{i, j} 是这对相邻的inversion：交换i,j 最大迟交没有增加，且更像贪心解A；
与假设的定义矛盾，故A是最优解。
时间复杂度： Θ(N log N) （due to sorting）

3. Optimal Caching

3.1 问题描述

Optimal Caching 问题描述

当cache中不存在所需元素时，需要访问cache交换元素。
目标：cache misses的次数最少

3.2 问题分析

Optimal Offine Caching: Farthest-In-Future

最优算法：cache miss时替换当前future queries中最远访问的元素。
e.g. future queries中第一个元素g出现cache miss, 需要exchange，判断current cache中需要替换哪个元素。
在future queries中

a：第2个出现；
b：第3个出现；
c：第4个出现；
d：第6个出现；
e：第5个出现；
f：第15个出现；
$\therefore$ Exchange f and g

3.3 证明最优

思路：构造最优规划 $S$ ，它有最小的cache misses次数；Farthest-In-Future规划 $S_{FF}$ ,两者在前 $j$ 个请求的序列是相同的，如果能证明在第 $j+1$ 步时， $S$ 可以转化为 $S_{FF}$ 并且没有增加cache misses的次数，则可以说明 $S_{FF}$ 是最优解。
最开始，假设 $S$ 和 $S_{FF}$ 中元素如下：


$S$	abcd
$S_{FF}$	abcd

Case 1: 元素已经在Cache中
假设下一个请求的元素是d显然两者都不会发生cache miss，故两者总的cache misses次数还是相同；


$S$	abcd
$S_{FF}$	abcd

Case 2: 元素不在Cache中， $S$ 和 $S_{FF}$ 与外界交换相同的元素
假设下一个请求的元素是e,两者都用a与其交换，有


$S$	ebcd
$S_{FF}$	ebcd

$S$ 和 $S_{FF}$ 都增加了一次cache misses，故总cache misses次数还是相同；
Case 3: 元素不在Cache中， $S$ 和 $S_{FF}$ 与外界交换不同的元素
假设下一个请求的元素是e, $S_{FF}$ 交换a, $S$ 交换b,有


$S$	aecd
$S_{FF}$	ebcd

之后，下一个请求的元素有四种情况：
Case 3a: 元素在 $S_{FF}$ 中, 不在 $S$ 中; S交换a
也就是请求b,这时S用a交换b,有


$S$	ebcd
$S_{FF}$	ebcd

$S$ 有两次cache misses，而 $S_{FF}$ 只有一次，之后 $S$ 和 $S_{FF}$ 序列又保持一致；
Case 3b: 元素在 $S_{FF}$ 中, 不在 $S$ 中; S不交换a
也就是请求b，S用c交换b，有


$S$	abde
$S_{FF}$	ebcd

$S_{FF}$ 用a交换c，有


$S$	abde
$S_{FF}$	abde

两者cache misses次数相同，之后 $S$ 和 $S_{FF}$ 序列又保持一致
Case 3c: 元素在 $S$ 中, 不在 $S_{FF}$ 中
即请求a，这种情况不可能发生，因为S_{FF}移出的是最远需要的元素，即request中a会排在b之后；
Case 3d: 元素不在 $S$ 和 $S_{FF}$ 中
假设请求f, $S$ 用a交换f, $S_{FF}$ 用b交换f,有


$S$	cdef
$S_{FF}$	cdef

两者cache misses次数相同，之后 $S$ 和 $S_{FF}$ 序列又保持一致
$\therefore S_{FF}$ 的cache misses次数不会多于最优解 $S$ , 即 $S_{FF}$ 是最优解。

4. Clustering of Maximum Spacing

4.1 问题描述

Clustering of Maximum Spacing 问题描述
Cluster间的距离（Spacing）：两个clsuter中距离最近的两个点之间的距离；
目标：给定cluster数量k，找到有最大spacing的k个聚类。

4.2 问题分析

Clustering of Maximum Spacing 问题分析

Single-link k-clustering 算法：

现有含n个cluster的一张图；
找到在不同集合中距离最近的一对点，在它们之间连线，
重复n-k次，就会得到k个clusters
这个过程相当于删掉最小生成树中k-1条最长的边；

4.3 证明最优

假设 $C^*$ 是从最小生成树中删去k-1条最长边后形成的k个clusters集合（ $C^*_1,C^*_2,...,C^*_k$ ）, $C^*$ 有最大的max spacing
假设 $C$ 是其它的clustering集合： $C_1,C_2,...,C_k$
$C^*$ 的spacing定义为第k-1条最长边的长度 $d^*$ ；
$p_i,p_j$ 是两点，它们在 $C^*$ 中在同一个集合 $C^*_r$ ，但是在 $C$ 的不同集合 $C_s$ 和 $C_t$ 中;
假设（ $p_i,p_j$ )路径中的两点定义了 $C_s$ 和 $C_t$ 之间的spacing，这个spacing $\leq$ $d^*$ ,所以 $C^*$ 最优。