《算法设计与分析基础》（Python语言描述） 课件 第7章贪心法

第7章每一步局部最优—贪心法7.1贪心法概述7.2求解组合问题7.3求解图问题7.4求解调度问题7.5哈夫曼编码CONTENTS提纲1/867.1.1什么是贪心法7.1贪心法概述每一步总是做出在当前看来是最好的选择，也就是说贪心法不从整体最优上考虑，所做出的仅是在某种意义上的局部最优解。解向量x=（x0，x1，…，xn-1）sn-1s0s1s2x0x1起始状态…x2snxn-1目标状态2/86每一步的局部最优选择仅依赖以前的决策，且不依赖于以后的决策。所有局部最优解合起来不一定构成整体最优解。所以贪心法不能保证对所有问题都得到整体最优解。因此采用贪心法求最优解时，必须证明该算法的每一步上做出的选择都必然得到整体最优解。3/867.1.2贪心法求解问题具有的性质1.最优子结构性质如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。证明方法：采用反证法，先假设由问题的最优解导出的子问题的解不是最优的，然后证明在这个假设下可以构造出比原问题的最优解更好的解，从而导致矛盾。4/862.贪心选择性质指整体最优解可以通过一系列局部最优选择（即贪心选择）来得到。证明方法：采用数学归纳法证明，即证明每一步所做的贪心选择最终得到问题的整体最优解。5/86问题描述：假设有n（1≤n≤30000）个孩子，现在给孩子们发一些小饼干，每个孩子最多只能给一块饼干。每个孩子i有一个胃口值g[i]（1≤g[i]≤2^31-1），这是能满足胃口的最小饼干尺寸，共有m块饼干，每块饼干j有一个尺寸s[j]。如果g[i]≤s[j]，那么将饼干j分发给孩子i时该孩子会得到满足。

分发的目标是尽可能满足越多数量的孩子，设计一个算法求这个最大数值。

例如，g={1，2，3},s={1，1}，尽管有两块小饼干，由于尺寸都是1，只能让胃口值是1的孩子满足，所以结果是1。

要求设计如下方法： def

findContentChildren(self,

g,s)

->

int:7.1.3实战—分发饼干（LeetCode455★）6/86解题目是求得到满足的最多孩子数量，所以是一个求最优解问题。很容易想到对于胃口为g[i]的孩子i，为其分发恰好满足的最小尺寸的饼干j即min{j|g[i]≤s[j]}，不妨分发过程从最小胃口的孩子开始，为此将g递增排序。对于每个s[i]，先在g查找刚好满足g[i]≤s[j]的j，再将饼干j分发该孩子i。为了提高g中的查找性能，将s也递增排序。7/86用ans表示得到满足的最多孩子数量（初始为0）即最优解，i从0开始遍历g，j从0开始在s中查找：g[i]≤s[j]，说明为孩子i分发饼干j得到满足，则将饼干j分发给孩子i，执行ans++，同时执行i++，j++继续为下一个孩子分发合适的饼干。否则，孩子i得不到满足，执行j++继续为其查找更大尺寸的饼干。最后的ans就是答案。8/86例如，g={3，1，5，3，8}，s={6，1，3，2}，排序后g={1，3，3，5，8}，s={1，2，3，6}，分发饼干的过程如下图所示，结果ans=3。饼干s胃口g133581236ij找到最优解9/861 class

Solution:2

def

findContentChildren(self,

g,s)

->

int:3

g.sort()

#默认为递增排序4

s.sort()5

ans=06

i,j=0,07

while

i<len(g)

and

j<len(s):8

if

g[i]<=s[j]:i,ans=i+1,ans+1 #i只有在满足时增19

j+=1 #每次循环j增110

return

ans10/86如果将贪心选择策略改为每个孩子i分发得到满足的饼干j（不一定是最小尺寸的饼干），结果是否正确呢？11/867.1.4贪心法的一般求解过程①建立数学模型来描述问题。②把求解的问题分成若干个子问题。③对每一子问题求解，得到子问题的局部最优解。④把子问题的解局部最优解合成原问题的一个最优解。12/861 defgreedy(a,n): #贪心算法框架2 x=[] #初始时，解向量为空3 foriinrange(0,n): #执行n步操作4 xi=Select(a) #从输入a中选择一个当前最好的分量5 ifFeasiable(xi): #判断xi是否包含在当前解中6 x=Union(xi) #将xi分量合并形成x7 returnx #返回生成的最优解贪心法求解问题的算法框架13/86假设有n个活动S=（1，2，…，n），有一个资源，每个活动执行时都要占用该资源，并且该资源任何时刻只能被一个活动所占用，一旦某个活动开始执行，中间不能被打断，直到其执行完毕。每个活动i有一个开始时间bi和结束时间ei（bi<ei），它是一个半开半闭时间区间[bi，ei），假设最早活动执行时间为0。求一种最优活动安排方案，使得安排的活动个数最多。7.2.1活动安排问题Ⅰ7.2求解组合问题14/86ejbj解biei(b)bi≥ejbj(a)bj≥eiejbiei对于两个活动i和j，若满足bj≥ei或bi≥ej，则它们是不重叠的，称为两个兼容活动。本问题就是在n个活动中选择最多的兼容活动即求最多兼容活动的个数。15/86用数组A存放所有的活动，A[i].b（1≤i≤n）存放活动起始时间，A[i].e存放活动结束时间。贪心策略：每一步总是选择执行这样的一个活动，它能够使得余下的活动的时间最大化即余下活动中兼容活动尽可能多。为此先按活动结束时间递增排序，再从头开始依次选择兼容活动（用B集合表示），从而得到最大兼容活动子集即包含兼容活动个数最多的子集。16/86i1234567891011开始时间b130535688212结束时间e4567891011121315求最大兼容活动集B的过程i=1：preend=0，活动1[1，4)的开始时间大于0，选择它，preend=活动1的结束时间=4，B={1}。i=2：活动2[3，5)的开始时间小于preend，不选取。i=3：活动3[0，6)的开始时间小于preend，不选取。i=4：活动4[5，7)的开始时间大于preend，选择它，preend=7，B={1，4}。i=5：活动5[3，8)的开始时间小于preend，不选取。17/86i1234567891011开始时间b130535688212结束时间e4567891011121315i=6：活动6[5，9)的开始时间小于preend，不选取。i=7：活动7[6，10)的开始时间小于preend，不选取。i=8：活动8[8，11)的开始时间大于preend，选择它，preend=11，B={1，4，8}。i=9：活动9[8，12)的开始时间小于preend，不选取。i=10：活动10[2，13)的开始时间小于preend，不选取。i=11：活动11[12，14)的开始时间大于preend，选择它，preend=14，B={1，4，8，11}。18/8601234567891011112131415234567891011i1234567891011开始时间b130535688212结束时间e456789101112131519/861 classAction: #活动类2 def__init__(self,b,e):3 self.b=b #活动起始时间4 self.e=e #活动结束时间5 def__lt__(self,other):

#用于按e递增排序6 ifself.e<other.e:returnTrue7 else:returnFalse820/869 defgreedly(A): #贪心算法10 globalflag11 n=len(A)12 flag=[False]*n #初始化为False13 A.sort() #按e递增排序14 preend=0; #前一个兼容活动的结束时间15 foriinrange(0,n):16 ifA[i].b>=preend:17 flag[i]=True #选择A[i]活动18 preend=A[i].e1921/8620 defaction(A): #求解活动安排问题Ⅰ22 greedly(A)23 print("求解结果");24 print("选取的活动:",end='')25 cnt=026 foriinrange(0,len(A)):27 ifflag[i]:28 print("[%d,%d]"%(A[i].b,A[i].e),end='')29 cnt+=130 print("\n共%d个活动"%(cnt))22/86程序验证A=[Action(1,4),Action(3,5),Action(0,6),Action(5,7),\ Action(3,8),Action(5,9),Action(6,10),Action(8,11),\ Action(8,12),Action(2,13),Action(12,15)]action(A)23/86算法的主要时间花费在排序上，排序时间为O(nlog2n)。所以整个算法的时间复杂度为O(nlog2n)。算法分析24/86算法证明所有活动按结束时间递增排序，这里就是要证明若X是A的最优解，X=X'∪{1}，则X'是A'={i∈A：ei≥b1}的最优解。那么A是不是总存在一个以活动1开始的最优解。如果第一个选择的活动为k（k≠1），可以构造另一个最优解Y，Y与X的活动数相同。那么在Y中用活动1取代活动k得到Y'，因为e1≤ek，所以Y'中活动也是兼容的，即Y'也是最优解，这就说明A总存在一个以活动1开始的最优解。最优子结构性质25/86当选择活动1后，原问题就变成了在A'中找兼容活动的子问题。如果X为原问题的一个最优解，而X'=X-{1}不是A'的一个最优解，说明A'能够找到的一个更优解Y'，Y'中的兼容活动个数多于X'，这样将活动1加入Y'后就得到A的一个更有解Y，Y中兼容活动个数多于X，这就与X是最优解的假设相矛盾。26/86贪心选择性质从前面最优子结构性质证明可以看出，每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题，可以对贪心选择次数用数学归纳法证明，这里不再详述。27/86问题描述：给定一个含n个区间的集合intervals，每个区间的终点总是大于它的起点，找到需要移除区间的最小数量，使剩余区间互不重叠，如区间{1，2}和{2，3}的边界相互接触，但没有相互重叠。

例如，intervals={{1，2}，{2，3}，{3，4}，{1，3}}，移除区间{1，3}后剩下的区间没有重叠，所以答案为1。

要求设计如下方法：def

eraseOverlapIntervals(self,intervals):7.2.2实战—无重叠区间（LeetCode435★★）28/86解法1两个相互不相交的区间就是兼容区间，采用前面活动安排问题Ⅰ的贪心方法求出intervals中最多兼容区间的个数ans，那么n-ans就是使剩余区间互不重叠需要移除区间的最小数量。稍有不同的是这里的区间起点和终点可能为负数，所以表示终点的preend初始值应该设置为-∞而不是0。29/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals):3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按区间终点递增排序7

ans=0

#表示兼容区间的个数8

preend=-INF #初始化为-∞9

for

i

in

range(0,n):10

if

intervals[i][0]>=preend:11

ans+=1 #兼容区间的个数增112

preend=intervals[i][1]13

return

n-ans30/86解法2同样两个相互不相交的区间就是保留的区间，为了使保留的区间最多，每次选择的区间结尾越小，留给其他区间的空间就越大，就越能保留更多的区间，这样采用的贪心选择策略是优先保留结尾小且不相交的区间。为此先将intervals按区间终点递增排序，ans表示最少相交区间的个数（初始为0），每次选择结尾最小且和前一个选择的区间不相交的区间，一旦找不到这样的区间时ans增1，最后返回ans。31/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals)->int:3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按区间终点递增排序7

ans=0

#表示兼容区间的个数8

preend=-INF #初始化为-∞9

for

i

in

range(0,n):10

if

intervals[i][0]<preend:

#找到一个相交区间11

ans+=1 #移除该区间12

else:13

preend=intervals[i][1]

#重置preend14

return

ans32/86解法1：通过，执行用时为168ms，内存消耗为44.9MB。解法2：通过，执行用时为176ms，内存消耗为44.8MB。33/86有n个编号为0～n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，找到选中物品不仅能够放到背包中而且价值最大的方案。与0/1背包问题的区别是这里的每个物品可以取一部分装入背包。物品编号no01234w1020304050v2030664060W=1007.2.3求解背包问题34/86贪心策略：每次选择单位重量价值最大的物品。序号i01234物品编号no31254w3010205040v6620306040v/w2.22.01.51.21.0x[0]=1bestv=66rw=rw-w[0]=70x[1]=1bestv=66+20=86rw=rw-w[1]=60x[2]=1bestv=86+30=116rw=rw-w[2]=40x[3]=0.8bestv=116+0.8*60=16435/861 defgreedly(g,W): #贪心算法2 globalx,bestv3 n=len(g)4 g.sort() #按v/w递减排序5 x=[0]*n #存放最优解向量6 bestv=0 #存放最大价值,初始为07 rw=W #背包中能装入的余下重量36/868 i=09 whilei<nandg[i].w<rw: #物品i能够全部装入时循环10 x[i]=1 #装入物品i11 rw-=g[i].w #减少背包中能装入的余下重量12 bestv+=g[i].v #累计总价值13 i+=1 #继续循环14 ifi<nandrw>0: #当余下重量大于015 x[i]=rw/g[i].w #将物品i的一部分装入16 bestv+=x[i]*g[i].v #累计总价值1737/8618 defknap(g,W): #求解背包问题19 greedly(g,W)20 print("求解结果") #输出结果21 forjinrange(0,len(g)):22 ifx[j]==1:print("选择%d[%d,%d]物品的比例是1" %(g[j].no,g[j].w,g[j].v))23 elifx[j]>0:print("选择%d[%d,%d]物品的比例是%.1f" %(g[j].no,g[j].w,g[j].v,x[j]))24 print("总价值=%d"%(bestv))38/86程序验证物品编号no01234w1020304050v203066406039/86排序算法sort()的时间复杂性为O(nlog2n)，while循环的时间为O(n)。所以算法的时间复杂度为O(nlog2n)。算法分析40/867.2.4实战—雪糕的最大数量（LeetCode1833★★）问题描述：商店中新到n支雪糕，用数组costs表示雪糕的价格，Tony一共有coins的现金，他想要买尽可能多的雪糕。

设计一个算法求Tony用coins现金能够买到的雪糕的最大数量，可以按任意顺序购买雪糕。

例如，costs={1，3，2，4，1}，coins=7，可以买下标为0、1、2、4的雪糕，总价为1+3+2+1=7，答案为4。

要求设计如下方法：public

int

maxIceCream(int[]

costs,

int

coins)

{}41/86解类似背包问题，采用的贪心策略是优先选择价格小的雪糕，这样使得剩余金额尽可能的多，将来能够做的决策方案也就相应变多。为此先将costs递增排序，然后从前向后处理，能够买的雪糕则买下。42/861 class

Solution:2

def

maxIceCream(self,

costs,

coins)

->

int:3

costs.sort()

#默认递增排序4

ans=05

rc=coins

#剩余的金额（从coins开始）6

for

i

in

range(0,len(costs)):7

if

costs[i]<=rc:

#可以买则买该雪糕8

ans+=19

rc-=costs[i]10

return

ans43/86问题描述：给定一组非负整数nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。由于输出结果可能非常大，所以需要返回一个字符串而不是整数。

例如，nums={3，30，34，5，9}，输出结果为"9534330"。

7.2.5实战—最大数（LeetCode179★★）44/86解采用的贪心策略是将数字位越大的数字越排在前面，然后从前向后进行合并即可。那么是不是直接将整数序列nums递减排序后再从前向后合并呢？答案是错误的，例如nums=（50，2，1，9）递减排序后为（50，9，2，1），合并后的结果是"50921"而不是正确的"95021"。为此改为这样的排序方式，对于两个整数a和b，将它们转换为字符串s和t，若s+t>t+s，则a排在b的前面，例如，对于50和9两个整数，转换为字符串"50"和"9"，由于"950">"509"，所以"9">"50"。按照这种方式排序后，依次合并起来得到字符串ans。如果ans的首字符为'0'，说明后面的元素均为0，则可直接返回"0"。45/861 import

functools2 class

Solution:3

def

largestNumber(self,

nums:

List[int])

->

str:4

a=[]5

for

x

in

nums:

#将nums转换为字符串数组a6

a.append(str(x))7

def

cmp(s,t):

#按指定方式排序8

if

s+t<t+s:return

19

else:return

-146/8610

a.sort(key=functools.cmp_to_key(cmp))11

ans=""12

for

i

in

range(len(a)):ans+=a[i]

#依次合并得到ans13

if

ans[0]=='0':return

"0"

#处理特殊情况14

else:return

ans47/86问题描述：有面额分别是c0、c1、…、ck（c≥2，k为非负整数）的k+1种硬币，每种硬币个数可以看成无限多，求兑换A金额的最少硬币个数。7.2.6求解零钱兑换问题48/86解

采用贪心法，贪心策略是尽可能选择面额大的硬币进行兑换，例如，c=2，k=3，面额分别是{1，2，4，8}，A=23的兑换过程如下：选择面额为8的硬币，兑换的硬币个数=A/8=2，剩余金额=23-2×8=7。选择面额为4的硬币，兑换的硬币个数=A/4=1，剩余金额=7-4×1=3。选择面额为2的硬币，兑换的硬币个数=A/2=1，剩余金额=3-2×1=1。选择面额为1的硬币，兑换的硬币个数=A/1=1，剩余金额=1-1×1=0。总硬币个数=2+1+1+1=549/861 defgreedly(c,k,A): #贪心算法2 ans=03 curm=2**k4 whileA>0:5 curs=A//curm #求面额为curm的硬币个数6 ans+=curs #累计硬币个数7 print("面额为%d的硬币个数=%d"%(curm,curs))8 A-=curs*curm #剩余金额9 curm/=c;10 returnans1112 defsolve(c,k,A): #求解零钱兑换问题13 print("求解结果")14 print("兑换金额%d的最少硬币个数=%d"%(A,greedly(c,k,A)))50/86A=23c=2k=3solve(c,k,A)程序验证51/867.3.1Prim算法构造最小生成树7.3求解图问题Prim（普里姆）算法是一种构造性算法。假设G=（V，E）是一个具有n个顶点的带权连通图，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，由G构造从起始顶点v出发的最小生成树T。52/86386174265054126338617426505412633861742650541263386174265054126353/86386174265054126338617426505412633861742650541263③3⑥6①1④4⑤2②60541263一棵最小生成树54/86U={i|U[i]=1}V-U={j|U[j]=0}lowcost[j]closest[j]vkj算法中的符号：55/861 INF=0x3f3f3f3f2 defPrim(A,n,v): #Prim算法3 T=[] #存放最小生成树4 lowcost=[INF]*n5 U=[0]*n6 closest=[0]*n7 forjinrange(0,n): #初始化lowcost和closest数组8 lowcost[j]=A[v][j]9 closest[j]=v10 U[v]=1 #源点加入U56/8611 foriinrange(1,n): #找出(n-1)个顶点12 mincost,k=INF,-113 forjinrange(0,n): #在(V-U)中找离U最近的顶点k14 ifU[j]==0andlowcost[j]<mincost:15 mincost=lowcost[j]16 k=j #k记录最近顶点的编号17 T.append([closest[k],k,mincost]) #产生最小生成树的一条边18 U[k]=1 #顶点k加入U19 forjinrange(0,n): #修改数组lowcost和closest20 ifU[j]==0andA[k][j]<lowcost[j]:21 lowcost[j]=A[k][j]22 closest[j]=k23 returnT【算法分析】Prim()算法中有两重for循环，所以时间复杂度为O(n2)。57/86Prim算法是一种贪心算法，如何理解Prim算法的最优子结构性质呢？10332210312(a)一个带权连通图32210312(b)子问题58/86采用反证法证明Prim算法满足最优子结构性质。证明：如果采用Prim算法求出原问题的生成树T是最小生成树，选择第一条边(v，a)后得到相应的子问题，假设该子问题采用Prim算法求出的生成树T1（T=(v，a)∪T1）不是最小的，而是最小生成树为T2，则(v，a)∪T2得到原问题的一棵不同于T的更小的最小生成树，用T是原问题的最小生成树矛盾。最优子结构性质即证。32210312(b)子问题59/86贪心选择性质证明。证明：k=1时，由前面最优子结构性质证明可以得出命题是成立的。命题7.1对于任意正整数k<n，存在一棵最小生成树T包含Prim算法前k步选择的边。60/86ek=(il，ik)e'UV-Uilikxy假设算法进行了k-1步，生成树的边为e1，e2，…，ek-1，这些边的k个顶点构成集合U，并且存在G的一棵最小生成树T包含这些边。算法第k步选择了顶点ik，则ik到U中顶点的边的权值最小，设这条边为ek=(il，ik)。假设最小生成树T不含有边ek，将ek添加到T中形成一个回路，如下图所示，这个回路一定有连接U与V-U中顶点的边e'，用ek替换e'得到树T'，即T'=(T-{e'})∪{ek}。61/86则T'也是一棵生成树，包含边e1，e2，…，ek-1，ek，并且T'所有边权值和更小（除非e'与ek的权相同），与T为一棵最小生成树矛盾，命题7.1即证。ek=(il，ik)e'UV-Uilikxy62/86当命题7.1成立时，k=n-1即选择了n-1条边，此时U包含G中所有顶点，由Prim算法构造的T=（U，TE）就是G的最小生成树。命题7.1对于任意正整数k<n，存在一棵最小生成树T包含Prim算法前k步选择的边。63/867.3.2Kruskal算法构造最小生成树Kruskal（克鲁斯卡尔）算法按权值的递增次序选择合适的边来构造最小生成树。假设G=(V，E)是一个具有n个顶点e条边的带权连通无向图，T=(U，TE)是G的最小生成树。64/863861742650541263(a)一个带权连通图38617426505412633861742650541263386174265054126365/86386174265054126338617426505412633861742650541263③3⑥6①1④4②2⑤60541263一棵最小生成树66/86首先，U中包含全部顶点，TE为空，看成是由n个连通分量构成的图，每个连通分量中只有一个顶点，当考虑一条边(u，v)时，若u和v属于两个不同的连通分量，则加入该边不会出现回路，否则会出现回路。这里每个连通分量就是并查集中的子集树。用数组E存放图G中的所有边，按权值递增排序，再从头到尾依次考虑每一条边，若可以加入则选择该边作为最小生成树的一条边，否则舍弃该边。67/86#UFS并查集类参见第2章2.10.2节1～23的代码1 INF=0x3f3f3f3f2 defKruskal(A,n): #Kruskal算法3 T=[] #存放最小生成树4 E=[] #边集5 foriinrange(0,n): #由A下三角部分产生的边集E6 forjinrange(0,i):7 ifA[i][j]!=0andA[i][j]!=INF:8 E.append([i,j,A[i][j]])9 E.sort(key=itemgetter(2)) #按边权值递增排序10 ufs=UFS()

#定义并查集对象11 ufs.Init(n)

#初始化并查集12 k,j=0,0 #k表示当前构造生成树的边数68/8613 whilek<n-1: #生成的边数小于n-1时循环14 u1,v1=E[j][0],E[j][1] #取一条边(u1,v1)15 sn1,sn2=ufs.Find(u1),ufs.Find(v1) #两个顶点所属的集合编号16 ifsn1!=sn2: #添加该边不会构成回路17 T.append([u1,v1,E[j][2]]) #产生最小生成树的一条边18 k+=1 #生成边数增119 ufs.Union(sn1,sn2) #将sn1和sn2两个顶点合并20 j+=1 #遍历下一条边21 returnT69/86【算法分析】排序时间为O(elog2e)，while循环是在e条边中选取n-1条边，最坏情况下执行e次，Union的执行时间为O(log2n)，所以上述Kruskal算法构造最小生成树的时间复杂度为O(elog2e)。【Kruskal算法的正确性证明】和Prim算法一样都是贪心算法，其正确性证明与Prim算法类似，这里不再详述。70/86问题描述：给定一个points数组，表示二维平面上的一些点，其中

points[i]={xi，yi}。连接两个点{xi，yi}和{xj，yj}的费用为它们之间的曼哈顿距离即|xi-xj|+|yi-yj|。

求将所有点连接的最小总费用，只有任意两点之间有且仅有一条简单路径时才认为所有点都已连接。

例如，points={{0，0}，{2，2}，{3，10}，{5，2}，{7，0}}，答案为20。

7.3.3实战—连接所有点的最小费用（LeetCode1584★★）71/86解法1：Prim算法本题给定的n个点看成是一个完全无向图，边的权值为对应两个点的曼哈顿距离，问题转化为求最小生成树的长度（最小生成树中所有边的权值和）。解法2：Kruskal算法Prim：执行用时为704ms，内存消耗为15.3MB。Kruskal：执行用时为1172ms，内存消耗为96.9MB。？60%和15.8%72/867.3.4Dijkstra算法求单源最短路径设G=(V，E)是一个带权有向图，所有边的权值为正数，给定一个源点v，求v到图中其他顶点的最短路径长度。Dijkstra（狄克斯特拉）算法把图中顶点集合V分成两组，第1组为已求出最短路径的顶点集合（用S表示），初始时S中只有一个源点v，第2组为其余未求出最短路径的顶点集合（用U表示）。每求得一条最短路径v，…，u，就将u加入到集合S中（重复n-1次），直到全部顶点都加入到S中。73/86在向S中添加顶点u时，对于U中的每个顶点j，如果顶点u到顶点j有边（权值为wuj），且原来从顶点v到顶点j的路径长度（Dvj）大于从顶点v到顶点u的路径长度（Dvu）与wuj之和，Dvj>Dvu+wuj，则将v

…

u→j的路径作为v到j的新最短路径，即Dvj=min(Dvj，Dvu+wuj)。vjuDvuwujDvj有一条边有一条路径Dvj=min(Dvj，cvu+wuj)74/86vjuA[u][j]松驰操作：dist[j]=min(dist[j],dist[u]+A[u][j])dist[u]dist[j]带权有向图用邻接矩阵A表示dist[i]表示从源点v到顶点i的目前最短路径长度75/861 defDijkstra(A,n,v): #Dijkstra算法2 globaldist3 dist=[0]*n4 S=[False]*n5 foriinrange(0,n):6 dist[i]=A[v][i] #距离初始化7 S[v]=True #源点v放入S中76/868 foriinrange(0,n-1): #循环n-1次9 u,mindis=-1,INF10 forjinrange(0,n): #选取U中具有最小距离的顶点u11 ifnotS[j]anddist[j]<mindis:12 u=j13 mindis=dist[j]14 ifu==-1:break15 S[u]=True #顶点u加入S中16 forjinrange(0,n): #修改U中的顶点的距离17 ifnotS[j]andA[u][j]!=0andA[u][j]<INF:18 dist[j]=min(dist[j],dist[u]+A[u][j])【算法分析】Dijkstra()算法中时间复杂度为O(n2)77/86Dijkstra算法的正确性证明转换为证明以下命题成立。命题7.2Dijkstra算法中当顶点u添加的S中时，dist[u]等于从源点v到u的最短路径长度D[v，u]（D[i，j]表示图中从顶点i到j的真实最短路径长度）。证明：假设对于V中的某个顶点t，dist[t]>D[v,t]，并设u是算法中添加到S中的第一个满足dist[u]>D[v,u]的顶点。因为存在从源点v到u的最短路径P，考虑当u添加到S的时刻，令z是此时不在S中的P路径上的第一个顶点。令y是路径P中z的前一个顶点（可能有y=v）。78/86dist[u]>D[v,u]dist[z]=D[v,z]vuzPSyu是下一个选择，因此dist[u]≤dist[z]第一个“不正确”的顶点dist[y]=D[v,y]现在选择的是将u添加的S中而不是z，因此有dist[u]≤dist[z]（按照Dijkstra算法，越先添加到S中其dist越小）。显然任何一条最短路径的子路径也是最短路径，因此，由于z在从v到u的最短路径上，则有D[v，z]+D[z,u]=D[v,u]。此外，D[z,u]≥0（因为图中没有负权），因此：dist[u]≤dist[z]=D[v,s]≤D[v,z]+D[z,u]=D[v,u]这样与u的定义矛盾。因此这样的顶点u不存在。命题7.2即证。79/86问题描述：有n个网络结点，标记为1到n。给定一个列表times，表示信号经过有向边的传递时间，times[i]=（ui，vi，wi），其中ui是源结点，vi是目标结点，wi是一个信号从源结点传递到目标结点的时间。

现在从某个结点k（1≤k≤n）发出一个信号，设计一个算法求需要多久才能使所有结点都收到信号？如果不能使所有结点收到信号，返回-1

。

例如，times={{2，1，1}，{2，3，1}，{3，4，1}}，n=4，k=2，结果为2。

7.3.5实战—网络延迟时间（LeetCode743★★）80/86用邻接表adj存放带权有向图，先由边数组times创建adj（注意顶点编号从1～n改为0～n-1），采用Dijkstra算法的过程求出dist数组。解012531adj=[[[1,1],[2,3]], #adj[0][[2,5]], #adj[1][[]] #adj[2]]81/86用邻接表adj存放带权有向图，先由边数组times创建adj（注意顶点编号从1～n改为0～n-1），采用Dijkstra算法的过程求出dist数组。再在dist数组中求最大值ans，若ans=INF说明不能使所有结点收到信号，返回-1，否则返回ans。82/861 class

Solution:2

INF=0x3f3f3f3f3

def

networkDelayTime(self,

times,

n,

k)

->

int:4

adj=[[]

for

i

in

range(n)]

#图的邻接表5

for

x

in

times:

#遍历times建立邻接表6

adj[x[0]-1].append([x[1]-1,x[2]])7

dist=self.Dijkstra(adj,n,k-1)8

ans=dist[0]9

for

i

in

range(1,n):10

ans=max(ans,dist[i])11

if

ans==self.INF:return

-112

else:return

ans1383/8614

def

Dijkstra(self,adj,n,v):

#基于优先队列的Dijkstra算法15

dist=[self.INF]*n16

S=[False]*n17

minpq=[]

#定义一个小根堆18

dist[v]=019

heapq.heappush(minpq,[dist[v],v])84/8620

while

minpq:21

x=heapq.heappop(minpq)

#出队结点e22

u=x[1]23

S[u]=True24

for

e

in

adj[u]:25

v,w=e[0],e[1]26

if

not

S[v]

and

dist[u]+w<dist[v]:27

dist[v]=dist[u]+w28

heapq.heappush(minpq,[dist[v],v])29

return

distuvwdist[u]dist[v]源85/86上述程序提交时通过，执行时间为80ms，内存消耗为16.9MB。86/86第7章每一步局部最优—贪心法7.1贪心法概述7.2求解组合问题7.3求解图问题7.4求解调度问题7.5哈夫曼编码CONTENTS提纲87/197.4求解调度问题调度问题有许多形式，这里专指这样形式的调度问题，n个作业要在一台机器上加工，每个作业的加工时间可能不同，这样有些作业就需要等待，全部作业完工的时间为等待时间和加工时间之和，称为系统总时间。该调度问题通常有两种，一是不带惩罚，另外一种是带惩罚的。88/197.4.1不带惩罚的调度问题不带惩罚的调度问题的最优解是最小系统总时间，实际上n个作业的加工顺序不同对应的系统总时间也不相同，该问题就是求一个具有最小系统总时间的加工顺序。贪心策略是选择当前加工时间最小的作业优先加工，也就是按加工时间递增排序，再按排序后的顺序依次加工。89/19序号i作业编号no加工时间ti等待时间wi总时间si00505113582248123321214序号i作业编号no加工时间ti等待时间wi总时间si032021132522459305914按加工时间递增排序系统总时间T=2+5+9+14=3090/191 defgreedly(a): #贪心算法2 a.sort() #递增排序3 T,w=0,0 #当前系统总时间和当前作业的等待时间4 foriinrange(0,len(a)):#依次处理各个作业5 T+=a[i]+w6 w+=a[i]7 returnT【算法分析】算法的执行时间主要花费在排序上，对应的时间复杂度为O(nlog2n)。正确性证明：略。91/197.4.2带惩罚的调度问题带惩罚的调度问题中，通常假设n个作业加工时间均为一个时间单位，时间用0～maxd的连续整数表示，每个作业有一个截止时间（deadline用时间整数表示），当一个作业在其截止时间之后完成，对应有一个惩罚值（punish）。该问题的最优解是最小总惩罚值。92/19贪心策略：选择当前惩罚值最大的作业优先加工，按惩罚值递减排序，并且尽可能选择作业截止时间之前最晚的时间加工。按排序后的顺序依次加工。作业编号no截止时间di惩罚值pi0470126024503340413054206610days[i]表示时间i是否在加工,初始均为F选时间4，days[4]=T，不惩罚，ans=0选时间2，days[2]=T，不惩罚，ans=0选时间3，days[3]=T，不惩罚，ans=0选时间1，days[1]=T，不惩罚，ans=0时间1已占，不能加工，惩罚，ans=30时间1～4已占，不能加工，惩罚，ans=30+20=50选时间6，days[6]=T，不惩罚

ans=5093/191 defgreedly(a): #贪心算法2 n=len(a)3 maxd=04 foriinrange(0,n):maxd=max(maxd,a[i][0])5 days=[False]*(maxd+1)6 a.sort(key=itemgetter(1),reverse=True)#按惩罚值递减排序7 ans=094/198 foriinrange(0,n):9 j=a[i][0]10 while