这一周的内容主要介绍了贪心算法

Course 3 Week 1

贪心算法的思路是总是选择“最优”的选择，“最优”可以人为定义，来看两个例子。

A Scheduling Application

问题的背景是我们有一些共享的资源（例如处理器）以及很多工作去做，每个工作有权重$w_j$以及长度$l_j$，定义任务$j$的完成时间$C_j = \sum_{i\le j} l_i$，我们的目标是最小化$\sum_{j=1}^n w_j C_j$

关于$C_j$来看一个Quiz

Quiz 1

$3$个工作，$l_1=1,l_2 =2 ,l_3=3$，按如下方式安排

$C_1, C_2,C_3$分别为多少？

利用定义即可，$C_1= 1,C_2= 3, C_3=6$

继续回到问题本身，考虑特殊情形：如果两个工作长度一样，那么权重大的显然要优先安排；如果两个工作权重一样，那么长度小的要优先安排。现在的问题是如果长度权重都不一样则如何处理，我们有如下贪心算法：

下面来证明这个算法可以得到最优解。

Proof

贪心算法的安排顺序为$\sigma=1,2,…,n$，假设最优解$\sigma^*$不同于$\sigma$，那么必然存在相邻的两个工作，使得$\frac {w_i}{l_i} < \frac {w_j}{l_j}$，但是$i$排在$j$之前，我们现在交换$i,j$的位置：

这样交换之后会改变$\sum_{j=1}^n w_j C_j$，但是注意，对于$k\neq i,j,w_kC_k$是不会改变的，只有$w_jC_j$和$w_iC_i$会改变，从上图中不难看出，$i$对应的价值增加了$w_i l_j$，$j$对应的价值减少了$w_jl_i$，从而差值为

注意

所以

这说明交换之后的$\sum_{j=1}^n w_j C_j$减少了，与$\sigma^$为最优解矛盾，这就说明$\sigma^= \sigma$为最优解。

最后考虑如何获得最优解，我们定义$\frac {w_i}{l_i} < \frac {w_j}{l_j}$但是$i$排在$j$之前为一个逆序，那么$n$个元素最多有$C_n^2$个逆序，一次交换可以减少一个逆序，从而最多经过$C_n^2$次交换可以将任意一个安排调整为最优解。

Minimum Spanning Trees

接下来介绍最小生成树的Prim算法：

  • Input: 无向图$G=(V,E)$，每条边$e\in E$有权值$c_e$，节点数为$n$，边的数量为$m$（这里假设图使用邻接表表示，每条边可以是负数）
  • Output: 包含全部顶点的总权值最小的树$T\subseteq E$（即$T$没有循环且子图$(V,T)$联通的）

这里有两个假设：

  • 图是联通的（否则没有最小生成树）
  • 每条边的权重不同（简化讨论）

接下来给出Prim算法

Prim 算法

这个算法本身还是挺简单的，但是我们要证明其正确性，显然这样产生的是包含全部节点的树，下面证明其为最小生成树，首先给出一个引理：

The Cut Property

证明之前首先给出Cut的定义：

接下来利用反证法证明这个引理。

假设存在一个cut $(A,B)$使得一条边$e$穿过这个cut，但是$e$不属于最小生成树$T^$，那么把$e$加入$T^$，这样就会形成一个环，如下图：

由最小生成树的定义，之前有$e’$穿过该cut，那么$T=T\bigcup \{e\}- e’$依旧是一个棵最小生成树，但是总权值更小，这就产生了矛盾。

现在利用引理证明Prim算法得到的树$T$是最小生成树，由引理可知，$T$中每条边都属于最小生成树，所以$T$是最小生成树的子集，而$T$本身就是生成树，所以$T$就是最小生成树。

Fast Implementation of Prim’s Algorithm

由Prim算法的伪代码可知一共要$O(n)$轮循环，每轮需要$O(m)$次操作，所以总共时间复杂度为$O(mn)$，接下来介绍如何加速算法，方法是使用Heap，假设$X$是已在树中的元素，将$V - X$中元素存在堆中，对$v\in V - X$，$\text{key}[v]$为$v$到$V$中元素的最短边长，这样算法可以按如下描述更新Heap：

最后分析下时间复杂度：