斯坦福算法专项课程Course3 week1内容回顾

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

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:

最后分析下时间复杂度: