《计算理论与算法12年CH4贪心课件.ppt》由会员分享，可在线阅读，更多相关《计算理论与算法12年CH4贪心课件.ppt（93页珍藏版）》请在三一办公上搜索。
1、贪心法（贪婪法）,2023/4/1,2 of 158,数钱一出纳员支付一定数量的现金。假设他手中有各种面值的纸币和硬币，要求他用最少的货币数支付规定的现金。例如，现有4种硬币：它们的面值分别为1分、2分、5分和1角。要支付2角5分。首先支付2个1角硬币，然后支付一个5分硬币，这就是贪心策略。,2023/4/1,3 of 158,贪心法不一定能产生正确的答案。例如，若引进一个1角1分的硬币，设从如下集合1,1,2,2,2,5,10,10,11,11中数出25分，按贪心法，共4个硬币。但最优解仅为3个硬币。这说明贪心法得到的解只是一个可行解。,2023/4/1,4 of 158,货郎担（TSP）问
2、题,设售货员要到五个城市去售货，最后再回到出发的城市。已知从一个城市到其他城市的费用，求总费用最少的路线,2023/4/1,5 of 158,权为13,从不同结点出发：1）结点a为起点：2）结点b为起点：3）结点c为起点：4）结点d为起点：,权为13,权为13,权为13,或者15,2023/4/1,6 of 158,而实际上图中最短哈密顿回路的长度为12。即abcda,2023/4/1,7 of 158,Huffman编码,某通讯系统只使用5种字符a、b、c、d、e，使用频率分别为0.1,0.14,0.2,0.26,0.3,利用二叉树设计不等长编码：1）构造以 a、b、c、d、e为叶子的二叉树
3、；2）将该二叉树所有左分枝标记0，所有右 分枝标记1；3）从根到叶子路径上标记作为叶子结点所 对应字符的编码；,2023/4/1,8 of 158,a:000 b:001c:01 d:10e:11,5种字符a、b、c、d、e，使用频率分别为0.1,0.14,0.2,0.26,0.3,30000-(1000+1400)*3-(2000+2600+3000)*2=7600,2023/4/1,9 of 158,Huffman编码:贪心选择性质,算法导论P234以及教材P112,2023/4/1,10 of 158,Huffman编码:贪心选择性质,2023/4/1,11 of 158,背包问题,已知
4、一个容量大小为M重量的背包和n种物品，物品i的重量为wi,假定物品i的一部分xi放入背包会得到vixi这么大的收益，这里，0 xi1，vi0。采用怎样的装包方法才会使装入背包的物品总效益最大？例：考虑以下情况下的背包问题n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),2023/4/1,12 of 158,n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),1)按效益值非增次序将物品依次放入背包(x1,x2,x3)wixi vixi2)按物品重量的非降次序将物品依次放入背包,(1,2/15
5、,0),20,28.2,(0,2/3,1),20,31,2023/4/1,13 of 158,n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),3)按vi/wi的非增次序将物品依次放入背包(x1,x2,x3)wixi vixi,(0,1,1/2),20,31.5,算法：背包问题的贪心算法,2023/4/1,14 of 158,void GreedyKnapsack(int n,float M,float v,float w,float x)Sort(n,v,w);/使v1/w1v2/w2vn/wn for(int i=1;ic)break;
6、xi=1;c-=wi;if(i=n)xi=c/wi;,2023/4/1,15 of 158,算法的时间复杂性为 O(nlogn)下面来证明使用此贪心算法所得到的贪心解是一个最优解。证明的基本思想是：把这个贪心解与任一个最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi，并证明在分量作了代换,2023/4/1,16 of 158,之后其总效益与代换之前无任何损失。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。定理：如果v1/w1 v2/w2 vn/wn,则此算法对于给定的背包问题实例生成一个最优解。,20
7、23/4/1,17 of 158,2023/4/1,18 of 158,j是使xj 1的最小下标,k是使 yk xk的最小下标。,X=(1,1,1/2,0)Y=(1,1,2/3,1/3)j=3,k=3,所以k=j,并且y3x3,(2)X=(1,1,1/2,0)Y=(1,1,1/2,1/2)j=3,k=4,所以kj,并且y4x4,从而证明了ykxk，并且k=j,2023/4/1,19 of 158,j是使xj 1的最小下标,k是使 yk xk的最小下标。,n=4,M=16,(v1,v2,v3,v4)=(20,12,6,6)(w1,w2,w3,w4)=(10,12,6,6)X=(1,1/2,0,0
8、)Y=(1,1/3,1/6,1/6)并且k=2,j=2,Z=(1,1/2,z3,z4),代换,w3(y3z3)+w4(y4z4)=w2(1/21/3),6(1/6z3)+6(1/6z4)=12*1/6,z3+z4=0,即推得Z=(1,1/2,0,0)X,2023/4/1,20 of 158,2023/4/1,21 of 158,有限期的任务安排问题,用贪心法求解有限期的任务安排问题：假设只能在同一台机器上加工n个任务，每个任务i完成时间均是一个单位时间。又设每个任务i都有一个完成期限di0,当且仅当任务i在它的期限截止以前被完成时，任务i才能获得pi的效益，每个任务的期限从整个工序的开工开始计
9、时，问应如何安排加工顺序，才能获得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2),2023/4/1,22 of 158,有限期的任务安排问题首先按效益非增次序进行排序，然后按照期限依次对此次序进行调整，排在后面的或提前或排除。算法的粗略描述void Greedy-Job(D,J,n)/*任务按 p1 p2 pn 的次序输入，它们的期限值Di 1,1in,n 1,J是可以在它们的期限截止前完成的任务的集合*/,2023/4/1,23 of 158,J 1;for(i=2;i=n;i
10、+)if（Ji 的所有任务都能在它 们的截止期限前完成）J Ji;定理：算法Greedy-Job对于有期限的任务安排问题得到一个最优解。证明：X Y Z 贪心解 最优解,2023/4/1,24 of 158,假设n个任务已按 p1 p2 pn 排序。首先将任务1存入解数组J中，然后处理任务2到任务n。假设已处理了i-1个任务,其中有k个任务已记入J(1),J(2),J(k)之中，并且有d(J(1)d(J(2)d(J(k)。现在处理任务i。为了判断Ji是否可行，只需看能否找出这样的位置：可以按期限的非降次序插入任务i，使得i在此处插入后，有 d(J(r)r,1 r k+1。,2023/4/1,2
11、5 of 158,找任务i可能的插入位置可如下进行：（a）若d(i)d(J(k),即任务i的期限比这k个任务的所有期限都长，则i可直接加入到k个任务的后面，即J(k+1)=i（b）将d(J(k),d(J(k-1),d(J(1)逐个与d(i)比较,直到找到位置q，它使得d(J(q)d(i)d(J(t)qtk,2023/4/1,26 of 158,此时若d(J(t)t qtk 这说明：第t个要加工的任务以及它以后加工的所有任务都可以向后移动一个单位时间。即这k-q个任务均可延迟一个单位时间加工。在以上条件成立的情况下，只要 d(i)q+1，就可将任务i插入到第q+1个位置上，从而得到一个按期限的非
12、降次序排列的含有k+1个任务的可行解。,2023/4/1,27 of 158,以上过程反复进行到对第n个任务处理完毕。所得到的贪心解就是一个最优解。任务 0 1 2 3 4 5 6 pi 0 30 25 20 15 10 5 di 0 3 5 2 2 3 1J(1)=3 J(2)=4 J(3)=1 J(4)=2 总效益：90,2023/4/1,28 of 158,void greedy-job(d,J,n,k)/*任务按 p1 p2 pn 的次序输入，它们的期限值d(i)1,1in,n 1,J(i)是最优解中的第i个任务，结束时d(J(i)d(J(i+1)*/,2023/4/1,29 of 1
13、58,d(0)0;J(0)0;k 1;J(1)1;for(i=2;id(i)if(d(J(q)d(i)&d(i)q),2023/4/1,30 of 158,for(t=k;t=q+1;t-)J(t+1)J(t);J(q+1)i;k k+1;,2023/4/1,31 of 158,活动安排:问题描述,有n个活动集E=1,2,n使用同一资源，而同一时间内同一资源只能由一个活动使用。每个活动的使用时间为si,fi)i=1,n，si为开始时间，fi为结束时间，若si,fi)与sj,fj)不相交称活动i和活动j是相容的。,问题：选出最大的相容活动子集合。,2023/4/1,32 of 158,贪心策略
14、将各活动按结束时间排序f1f2fn，先选出活动1，然后按活动编好从小到大的次序依次选择与当前活动相容的活动。,注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。证明：见算法导论P224,2023/4/1,33 of 158,2023/4/1,34 of 158,void ActivitySelection(int n,s,f,bool a)/f已排序，a记录选择的活动，即ai=true表示活动i已选择 a1=true;int j=1;for(int i=2;i=fj)ai=true;j=i;else ai=false;,T(n)=O(nlogn),2023/4/1,35 of
15、 158,活动安排:计算示例,11个活动已按结束时间排序，用贪心算法求解：i 1 2 3 4 5 6 7 8 9 10 11start_timei 1 3 0 5 3 5 6 8 8 2 12finish_timei 4 5 6 7 8 9 10 11 12 13 14,相容活动：a3,a9,a11,a1,a4,a8,a11,a2,a4,a9,a11,2023/4/1,36 of 158,最小生成树,最小生成树的定义Kruskal算法 Prim算法,2023/4/1,37 of 158,网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示
16、建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,最小生成树,2023/4/1,38 of 158,最小生成树,设G=(V,E)是一个无向连通带权图，如果G的一个子图T是一棵包含G的所有顶点的树(G的生成树)，生成树T上各边权的总和(生成树的耗费)最小，则T称为G的最小生成树(MST：minimum spanning tree),2023/4/1,39 of 158,Kruskal最小生成树算法 Kruskal 在1956年提出了1个最小生成树算法。设G=(V,E)是一个连通带权图，V=1,2,n。将图中的边按其权值由小到大排序，然后作如下的贪婪选择
17、，由小到大顺序选取各条边，若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。如此依次进行，到选够（n-1）条边即得到最小生成树。,最小生成树,2023/4/1,40 of 158,例如，对于下图中的带权图,各边按权值排序为：d13=1 d46=2 d25=3 d36c4 d14=5d34=5 d23=5 d12=6 d35=6 d56=6,2023/4/1,41 of 158,按Kruskal算法选取边的过程如下图所示。,2023/4/1,42 of 158,Kruskal最小生成树算法,最小生成树,/在一个具有n个顶点的网络中找棵最小生成树令E为
18、网络中边的集合令T为所选边的集合,初始化T为空集 while(E 不是空集 算法复杂度为O(n+eloge),2023/4/1,43 of 158,Prim最小生成树算法 Prim在1957年提出另一种算法，这种算法特别适用于边数相对较多，即比较接近于完全图的图。此算法是按逐个将顶点连通的步骤进行的，它只需采用一个顶点集合。这个集合开始时是空集，以后将已连通的顶点陆续加入到集合中去，到全部顶点都加入到集合中了，就得到所需的生成树。,最小生成树,2023/4/1,44 of 158,Prim最小生成树算法 设G=(V,E)是一个连通带权图，V=1,2,n。构造G的一棵最小生成树的Prim算法的过
19、程是：首先从图的任一顶点起进行，将它加入集合S中置，S=1，然后作如下的贪婪选择，从与之相关联的边中选出权值cij最小的一条作为生成树的一条边，此时满足条件iS，jV-S，并将该j加入集合中，表示连两个顶点已被所选出的边连通了。,最小生成树,2023/4/1,45 of 158,以后每次从一个端点在集合S中而另一个端点在集合S外的各条边中选取权值最小的一条作为生成树的一条边，并把其在集合外的那个顶点加入到集合S中。如此进行下去，直到全部顶点都加入到集合中S。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。由于Prim算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点，故这个边选取后
20、一定能将该未连通点连通而又保证不会形成回路。,最小生成树,2023/4/1,46 of 158,例如，对于下图(a)中的带权图，按Prim算法选取边的过程如下图(b)所示。,2023/4/1,47 of 158,Prim最小生成树算法,最小生成树,/在一个具有n个顶点的网络中找棵最小生成树令E为网络中边的集合令T为所选边的集合,初始化T为空集另S为已在树中节点的集合,置S=1;while(E 不是空集 算法复杂度为O(n2),2023/4/1,48 of 158,排序之车间作业计划模型,一：一台机器、n个零件的排序目的：使得各加工零件在车间里停留的平均时间最短。,若按此顺序：(1.8+3.8+
21、4.3+5.2+6.5+8)/6=4.9,实际上最短：3,4,5,6,1,2(0.5+1.4+2.7+4.2+6+8)/6=3.8,2023/4/1,49 of 158,排序之车间作业计划模型,二：两台机器、n个零件的排序目的：使得完成全部工作的总时间最短。,2023/4/1,50 of 158,某车间需要用一台车床和一台铣床加工A、B、C、D四个零件。每个零件都需要先用车床加工，再用铣床加工。车床与铣床加工每个零件所需的工时（包括加工前的准备时间以及加工后的处理时间）如表。,若以A、B、C、D零件顺序安排加工，则共需32小时。适当调整零件加工顺序，可产生不同实施方案，我们称可使所需总工时最短
22、的方案为最优方案。在最优方案中，零件A在车床上的加工顺序安排在第（1）位，四个零件加工共需（2）小时。（1）A.1 B.2 C.3 D.4（2）A.21 B.22 C.23 D.24,2023/4/1,51 of 158,以A、B、C、D零件顺序安排加工，则共需32小时。,8,14,20,32,基本方法：在第一台机器上加工时间越少的零件越早加工；在第二台机器上加工时间越少的零件越晚加工；,2023/4/1,52 of 158,(1)第一个：第二个：第三个：第四个:,(2)第一个：第二个：第三个：第四个:,(3)第一个：第二个：第三个：第四个:,(4)第一个：第二个：第三个：第四个:,B,B,C
23、,A,D,CDAB:22,2023/4/1,53 of 158,练习,某车间需要用一台车床和一台铣床加工 A、B、C、D 四个零件。每个零件都需要先用车床加工，再用铣床加工。车床和铣床加工每个零件所需的工时（包括加工前的准备时间以及加工后的处理时间）如下表。,若以 A、B、C、D 零件顺序安排加工，则共需 29 小时。适当调整零件加工顺序，可产生不同实施方案，在各种实施方案中，完成四个零件加工至少共需（1）小时。（1）A.25 B.26 C.27 D.28,B.26 BADC,2023/4/1,54 of 158,解:用网络图表示上述的工序进度表 网络图中的点表示一个事件,是一个或若干个工序的
24、开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权,统筹方法,2023/4/1,55 of 158,统筹方法,一、计划网络图：统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请画出其统筹方法网络图。,2023/4/1,56 of 158,a,b,c,d,e,60,13,8,38,15
25、,1,2,3,4,5,2023/4/1,57 of 158,将上例的工序进度表做一些扩充如下，请画出其统筹方法的网络图。,2023/4/1,58 of 158,f,10,2023/4/1,59 of 158,为此需要设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,10,f,2023/4/1,60 of 158,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。,2023/4/1,61 of 158,练习,2023/4/1,62 of 158,2023/4/1,63 of 158,二、网络时间与关键路线 在绘制出网络图之后，可以由网
26、络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。,2023/4/1,64 of 158,把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始,例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？,2023/4/1,65 of 158,定义AOE网(Activity On Edge)也叫边表
27、示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度路径上各活动持续时间之和关键路径路径长度最长的路径叫关键路径Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)-e(i)表示完成活动ai的时间余量关键活动关键路径上的活动叫关键活动，即l(i)=e(i)的活动,2023/4/1,66 of 158,问题分析如何找e(i)=l(i)的关键活动？,设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-d
28、ut(),如何求Ve(j)和Vl(j)？,(1)从Ve(源点)=0开始递推,(2)从Vl(汇点)=Ve(汇点)开始向回递推,2023/4/1,67 of 158,求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i),V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,0,0,0,2,6,6,4,6,5,8,7,7,7,7,7,10,16,16,14,14,0,3,2023/4/1,68 of 158,某工程包括 A、B、C、D、E、F、G 七个作业，各个作业的紧前作业、所需时间
29、、所需人数如下表：,该工程的计算工期为 周。,2023/4/1,69 of 158,答案：7周,2023/4/1,70 of 158,V1V2V3V4V5V6,011437,031457,ABCDEFG,0,2,0,0,1,1,1,3,4,4,3,5,1,3,2023/4/1,71 of 158,ABCDEFG,0,2,0,0,1,1,1,3,4,4,3,5,1,3,2023/4/1,72 of 158,4.2 贪心算法的基本要素,对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般
30、具有2个重要的性质：贪心选择性质和最优子结构性质。,2023/4/1,73 of 158,4.2 贪心算法的基本要素,1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。,2023/4/1,74 of 158,4.2 贪心算法的基本要素,2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题
31、具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,2023/4/1,75 of 158,4.2 贪心算法的基本要素,3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。,2023/4/1,76 of 158,4.2 贪心算法的基本要素,0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为
32、Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。,2023/4/1,77 of 158,4.2 贪心算法的基本要素,背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。,这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。P106,2023/4/1,78 of 158,4.2 贪心算法的基本要素,用贪心算法解背
33、包问题的基本步骤：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。,2023/4/1,79 of 158,4.2 贪心算法的基本要素,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多
34、互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。,2023/4/1,80 of 158,4.3 最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,2023/4/1,81 of 158,4.3 最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,假设n=8,w1,.,w8=100,200,50,90,150,50,2
35、0,80,c=400。,2023/4/1,82 of 158,4.3 最优装载,从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。,2023/4/1,83 of 158,w1,.,w8=100,200,50,90,150,50,20,80,c=400。,利用贪婪算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为3 9 0个单位且已被装载，剩下的装载能力为1 0个单位，小于剩下的任何一
36、个货箱。在这种贪婪解决算法中得到x1,.,x8=1,0,1,1,0,1,1,1 且xi=6。,2023/4/1,84 of 158,4.3 最优装载,void ContainerLoading(int x,float w,float c,int n)Sort(w,t,n);/此时,wiwi+1 for(int i=1;i=n;i+)/初始化x xi=0;for(i=1;i=n/剩余容量 T(n)=O(nlogn),2023/4/1,85 of 158,4.3 最优装载,2.贪心选择性质 最优装载问题具有贪心选择性质。3.最优子结构性质最优装载问题具有最优子结构性质。P108,2023/4/1,
37、86 of 158,4.5 单源最短路径,Dijkstra最短路：按路径长度递增的次序产生从源点v到其余各点的最短路径。,设S为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为x)，或者为有向边(v,x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。反证法：,假设此路径上有一个顶点y不在S中，则说明存在一条终点不在S而长度比此路径短的路径。,但这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的，故长度比此路径短的所有路径都已产生，它们的终点必在S中，即假设不成立。,2023/4/1,87 of 158,最短路例,10(v5)第1短,step1,50,30,10
38、0,10,20(v4)第2短,step2,50,30,20,30(v3)第3短,step3,40,30,35(v2)第4短,step4,35,50,45(v6)第5短,step5,45,/V1,/V5,/V1,/V3,/V2,2023/4/1,88 of 158,例,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。Dijkstra算法的迭代过程：,2023/4/1,89 of 158,例子(续),2023/4/1,90 of 158,例子(续),经过Dijstra算法计算后可得数组prev具有：Prev2=1;Prev3=4Prev4=1
39、;Prev5=3如果找出顶点1到顶点5的最短路径：从数组prev得到顶点5的前一个顶点是3，3的前一个顶点是4，4的前一个顶点是1。所以顶点1到顶点5的最短路径是1，4，3，5.,2023/4/1,91 of 158,算法的正确性和计算复杂性,Dijkstra算法的正确性：(1)贪心选择性质(2)最优子结构性质计算复杂性：对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。,2023/4/1,92 of 158,小张被借调到一个新单位，图中a点是小张的住宅，z为新单位的位置，边上的数字表示距离，则小张到新单位的最短距离为_.,13,2023/4/1,93 of 158,练习,假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有的活动。给出解决该问题的算法核心代码。例如，有如下活动的开始和结束时间。5 912 145 78 123 80 63 58 111 42 136 10,
