第二章 道路与回路3-应用

1、第二章第二章 道路与回路道路与回路2015年秋年秋主要内容主要内容5:062图论问题基本求解思路图论问题基本求解思路图论模型图论模型5:0645:0655:0665:0675:068图图论模型实论模型实例例5:0695:06105:06115:06125:06135:0614 数据实例1 输入51 22 33 44 55 6 输出Some beads may be lost5:0615 数据实例2 输入 输出5 2 12 1 1 32 2 3 43 4 4 23 1 2 22 4 5:0616 1) 珠子为顶点，珠子串接的可能为边无法将问题的内容表达完全无法将问题的内容表达完全如实例2, 在图

2、中可以遍历(1, 2) (2, 3) (2, 2), 得到的项链不符合题意.5:06175:06182.5 旅旅行商问行商问题题回回顾：顾： Euler回路：回路： 经过每条边一次，也仅仅一次的回路。经过每条边一次，也仅仅一次的回路。 Hamilton路：路： 经过每个结点一次，也仅仅一次的回路。经过每个结点一次，也仅仅一次的回路。H。5:06205:0621例例 1)d(0)= ，权值从权值从小到大排队，编号小小到大排队，编号小前前边 a35 a15 a24 a14 a12 a13 a34 a23 a45 a25权 3 4 4 9 10 10 11 13 16 201423541013111

3、69 1020435:0622例例边边 a35 a15 a24 a14 a12 a13 a34 a23 a45 a25权权 3 4 4 9 10 10 11 13 16 20 2)在边权序列中依次选边深探，取在边权序列中依次选边深探，取 N条边条边 3)判断是否构成判断是否构成H回路回路， 若是，结束；若是，结束； 否则否则，将将试探路试探路的的最后最后元素换元素换成下一个待选元素成下一个待选元素，直到能构成直到能构成H回回路，路，此此时记下其路长时记下其路长d(i)。 如如果果d(i) d(0)，赋赋给给d(0). 4)退出退出上述上述H回路回路的的最后最后2个个元素，换成新的元元素，换成新

4、的元素，判断其路长素，判断其路长d(i)是否小于是否小于d(0).若若小于小于d(0)则则回到第回到第3步步(有可能得到更短的回路有可能得到更短的回路)，否则再多退一个元素，否则再多退一个元素，重复第重复第4步的判断工作步的判断工作，若无元素可退，若无元素可退则中止寻找工作，即换掉最后三则中止寻找工作，即换掉最后三个元素个元素5:0623 a35 a15 a24 a14 a12 a13 a34 a23 a45 a25 3 4 4 9 10 10 11 13 16 20D(0)= D(1)=(a35,a15,a24,a14,a12) 三个三个1 不可不可D(2)=(a35,a15,a24,a14

5、, a13) 三个三个1 不可不可D(3)=(a35,a15,a24,a14, a34) 一一个个2, 不可不可D(4)=(a35,a15,a24,a14, a23) 构成回路构成回路, d4=3+ 4+4+9+13=33 此时此时d0=33已成回路已成回路,寻找寻找短于短于33的的H回路回路, 这时若这时若换换最后的那条边最后的那条边只会加只会加长长退退2条边条边D(5)=(a35,a15,a24, a12,a13) d5=31d0,可能存在更短可能存在更短H回路回路,再继续深探再继续深探,换最后换最后一边一边5:0624142354101311169102043a35 a15 a24 a1

6、4 a12 a13 a34 a23 a45 a25 3 4 4 9 10 10 11 13 16 20 D(5)=(a35,a15,a24, a12,a13) d5=31d0,可能存在更短可能存在更短H回路回路,再继续深探再继续深探. D(6)= (a35,a15,a24, a12,a34) D(6)=32d0不可能最短，故剪枝，退出后不可能最短，故剪枝，退出后3个元素个元素 D(8)= (a35,a15, a14,a12,a13 ) D8=36d0不可能最短，故剪枝，退出后不可能最短，故剪枝，退出后4个元素个元素5:0625142354101311169102043 D(8)= (a35,a

7、15, a14,a12,a13 ) D8=36d0不可能最短故剪枝，退出不可能最短故剪枝，退出后后4个元素个元素 D(9)=(a35, a24 a14 a12 a13) D9=36d0不可能最短故剪枝不可能最短故剪枝,退出退出后后5个元素个元素 D(10)=(a15 a24 a14 a12 a13 ) D10=37d0不可能最短故剪枝，无路可退！这时不可能最短故剪枝，无路可退！这时若换掉最后的元素只会增加路长！不可能短若换掉最后的元素只会增加路长！不可能短5:0626142354101311169102043a35 a15 a24 a14 a12 a13 a34 a23 a45 a25 3 4

8、 4 9 10 10 11 13 16 20小结：小结： 由由于对边权进行了排序，因此于对边权进行了排序，因此“深探深探”时时删删除最后添加除最后添加边边ek，添加下一条待选的边，添加下一条待选的边ej,则则Lj Lk，故故此路的长度此路的长度d是递增的是递增的。 当当找到一条找到一条H回路时其路回路时其路长长d(0)为为“界值界值”。 一一旦确定界值，则旦确定界值，则路长路长 d(0)的的分支分支不必不必“深深探探”即即“剪枝剪枝”。 最最后得到的后得到的界值界值就是问题的最佳解。就是问题的最佳解。 计计算工作量算工作量O(n!)，需需采用近似算法。采用近似算法。 5:0627 024281

9、927240172125281702335192123018272535180a43 a21 a52 a42 a32 a54 a41 a51 a53 a3117 18 19 21 23 24 25 27 28 35 5:0628D(0)=(a43 a21 a52 a42 a32 ) 不成不成H回路回路,深探深探D(1)=(a43 a21 a52 a42 a54 ) 不成不成H回路回路,深探深探D(2)=(a43 a21 a52 a42 a41 ) 不成不成H回路回路,深探深探D(3)=(a43 a21 a52 a42 a51 ) 不成不成H回路回路,深探深探D(4)=(a43 a21 a52

10、a42 a53 ) 不成不成H回路回路,深探深探D(5)=(a43 a21 a52 a42 a31 ) 不成不成H回回,退出最后退出最后2元素元素 D(6)=(a43 a21 a52 a32 a54 ) 不成不成H回回,因前因前4个中有个中有3个个2，退出前，退出前3个元素个元素a43 a21 a52 a42 a32 a54 a41 a51 a53 a3117 18 19 21 23 24 25 27 28 35 5:0629D(6)=(a43 a21 a52 a32 a54 )不不成成,因前因前4个中有个中有3个个2,退退出前出前3个个D(7)=(a43 a21 a42 a32 a54 )

11、，退出前，退出前3个元素。个元素。D(8)=(a43 a21 a32 a54 a41 ) ，不成，不成H回路回路,深深探探D(9)=(a43 a21 a32 a54 a51 ) 成成H回回路，路，d0=109退栈退栈D(10)=(a43 a21 a32 a41 a51 ) d10d0不不可可能，退能，退栈栈D(11)=(a43 a21 a54 a41 a51 ) d11d0不可不可能，退能，退栈栈D(12)=(a43 a52 a42 a32 a54 ) d12d0深探？退栈深探？退栈D(13)=(a21 a52 a42 a32 a54) 仍不深探，栈空仍不深探，栈空5:0630a43 a21

12、a52 a42 a32 a54 a41 a51 a53 a3117 18 19 21 23 24 25 27 28 35 旅行旅行商问题商问题-便便宜算法宜算法 便宜算法适用的情况便宜算法适用的情况: (1)G是无向正权图。是无向正权图。(正权正权) (2)W(i,j)+W(j,k) W(i,k)，即任，即任何两边之和大何两边之和大于第三边于第三边(三角不等三角不等) 基基本思路本思路： 从从编号为编号为1的点出发，寻找与的点出发，寻找与“已确定的回路已确定的回路”距离最近的点，插入到回路中距离最近的点，插入到回路中。5:0631算法设计方法：贪心法算法设计方法：贪心法5:06325:0633

13、V1V1V21818根据第根据第1行确定与行确定与V1最近的点最近的点，根根据第据第2行确定与行确定与V2最近的点最近的点。在在1,2行的行的3,4,5列找到最小列找到最小19=W(2,5)加入加入V5。V1V22718V519在在1,2,5行的行的3,4列列 找最小值找最小值21=W(2,4)加入加入V4 0242819272401721252817023351921230182725351805:0634在在1,2,5行的行的3,4列列 找最小值找最小值21,即即V2与与V4相连相连21,那那V4另一头另一头与谁相连呢与谁相连呢?若若V4的的另一头与另一头与V1相连相连,则需剪则需剪断断e

14、12,新回路长新回路长d=27192521,增长增长21+25-18=28若若V4的的另一头与另一头与V5相连相连,则需剪则需剪断断e25,增长增长21+24-19=26V1V22718V519V421 024281927240172125281702335192123018272535180 25245:0635 024281927240172125281702335192123018272535180V1V22718V5V42124 若若V4的的另一头与另一头与V1相连相连,则剪断则剪断e12,新回路长新回路长d=27192521,增长增长21+25-18=28 若若V4的的另一头与另一头

15、与V5相相连连,则剪断则剪断25,增长增长21+24-19=26 在在V2的邻居中寻找相连对象的邻居中寻找相连对象. V4与与V5相连相连,费用便宜费用便宜.5:0636V1V227V5V421241817V3 024281927240172125281702335192123018272535180 在在1,2,4,5行寻剩下点距离最短的边行寻剩下点距离最短的边. W(4,3)=17. 在在V4的的老邻居老邻居中寻找一个与中寻找一个与V3相连相连,使路之增长最使路之增长最小。小。 若若V3与与V2相连则剪断相连则剪断e24, 增长增长17+23-21=19。 若若V3与与V5相连则剪断与相连

16、则剪断与e45增长增长17+28-24=21, 与与V2相连最便宜相连最便宜。 18+23+17+24+27=1095:0637便宜算法便宜算法：1)T=(1,1) S=2,3,n,d0=02)根据权矩阵根据权矩阵,在余点集在余点集S中中,寻找与寻找与回路回路T之距离之距离最小最小的点的点Vk,T中与中与Vk相连点为相连点为Vj, 3)在原回路中加进在原回路中加进Vk,断开断开Vj的的2个回路邻居个回路邻居Vt,Vr中某个。中某个。 W(k,j)+W(k,t)-W(t,j) or W(k,j)+W(k,r)-W(r,j) ? 4)k加入到回路加入到回路T中中, S中去掉中去掉k.VjVtVrV

17、k5:0638TSP-39v1v2viVi+1vjvj+1vn初始H圈Cv1v2viVi+1vjvj+1vn5:064013221705651607835365168576861TPePaNYMCL5:06 解：取初始圈为：41132156603651TPePaNYMCL278132170603651TPePaNYMCL2785:0642132170353651TPePaNYMCL251132170356856TPePaNYMCL2515:062.6最短路径最短路径概念概念 最短路问题：最短路问题： 在在结点结点V1到任意结点到任意结点Vi的所有路中，寻找长度最的所有路中，寻找长度最短的路短的

18、路(记为记为P(i)）及相应的路长）及相应的路长D(i). 路路中不可能含有负长回路。中不可能含有负长回路。 回回忆忆:通通过过BFS、DFS寻找过寻找过V1到任意结点到任意结点Vi是否有路。是否有路。 如如果有路，如何找出最短路，果有路，如何找出最短路， 正正如如TSP是最短的是最短的H路一样。路一样。 能能否否最短路径算法最短路径算法来解决来解决TSP问题问题?5:06441、正权图中正权图中V1到各点的最短路径到各点的最短路径V1ViVjP(j)P(j)P(i)5:06451、正权图中、正权图中V1到各点的最短路径到各点的最短路径5:0646Dijkstra算法算法(迪杰斯特拉迪杰斯特拉

19、) 1)D(1)=0,D(i)=W(1,i),即即i与与1有边相连则有边相连则路长路长D(i)=权重权重W(1,i),否则否则 . S=2,3,n 2)在在S中寻找路长中寻找路长D(i)最小点最小点j,并且并且S= S-j，直到直到S为为空，否则转空，否则转3）。）。 3) 调整调整j之后继点的路长之后继点的路长:在在S中寻找中寻找j的的后后继继结结点点i，若，若d(j)+w(j,i)8不改不改 2的后代的后代d6=d2+1=6+1=7d4不不改，改，2的后代的后代d6=d2+1=6+1=7d6,则则d6=7D1=0,d2=6,d3=1,d4=8,d5=3,d6=7，S4,6中最小路长为中最小

20、路长为7(D6),S=4,6的后代的后代V5不在不在S中，所以不处理中，所以不处理5:0650V1V4V5V2V3V64715123375D1=0,d2=6,d3=1,d4=8,d5=3,d6=7，S4中最小路长为中最小路长为8(d4),S=,修改修改4的后代，但它没有后代的后代，但它没有后代 .D1=0,d2=6,d3=1,d4=8,d5=3,d6=7，S4,6中最小路长为中最小路长为7(D6),S=4,6的后代的后代V5不在不在S中，所以不处理中，所以不处理5:06512、边权边权为为1时时V1到到各点各点的最短路径的最短路径 可可以直接采用以直接采用Dijkstra方法，但有些步骤可以方

21、法，但有些步骤可以省省略。略。 这属于路由的这属于路由的跳数跳数计算，计算，最短路由最短路由的问题的问题V1V4V5V2V3V611111111115:0652V1V4V5V2V3V61111111111D1=0 D2=1 D3=1 d4=d5=d6= S=2,3,4,5,6 中最小中最小1(D2) S=3,4,5,6 ，修改修改V2后代后代的路长的路长,为为: d4=d2+1=2 ，d6=d2+1=2D1=0 D2=1 D3=1 d4=2,d5=,d6=2 S=3,4,5,6 中最小中最小1(D3), S=4,5,6 ，修改修改V3后代的路长后代的路长,为为: d5=d3+1=2，d6=d3

22、+1=25:0653V1V4V5V2V3V61111111111D1=0 D2=1 D3=1 d4=2,d5=2,d6=2 S=4,5,6 中最小中最小2(D4), S=5,6 ，修改，修改V4后代后代的路长的路长,无邻接点。无邻接点。D1=0 D2=1 D3=1 d4=2,d5=,d6=2S=3,4,5,6 中最小中最小1(D3),S=4,5,6 ，修改修改V3后代的路长后代的路长,为为: d5=d3+1=2 d6=d3+1=25:0654Dijkstra边权为边权为1时的算法时的算法1)D(1)=0,D(i)=,k=0,S=1,S0=1 2)第第k步，置步，置Sk+1= +Sk S 本轮处

23、理对本轮处理对象：象：直直接后继中未处理过接后继中未处理过的节点的节点。 D(i)=k+1,i Sk+1, 本轮结点距离本轮结点距离k+1 S=S Sk+1 S为已处理结点集为已处理结点集3)若若|S|=n则结束，否则重复第则结束，否则重复第2步。步。5:0655V1V4V5V2V3V611111111111)D(1)=0,D(i)=,k=0,S=1,S0=12)S1=So+1= +S0 S=2,3 2,3,4,5,6 =2,3 D(2)=0+1=1, D(3)=0+1=1 S= S S0+1 =1,2,3 k=k+1=0+1=1.5:0656V1V4V5V2V3V611111111112)S

24、1= +S0 S=2,3 2,3,4,5,6=2,3 k为为0 D(2)=0+1=1,d(3)=0+1=1 S= S S0+1 =1,2,3, S= 4,5,6 k=k+1=0+1=13) Sk+1= +S1 S=4,6,5 4,5,6=4,5,6 k为为1 D(4)=1+1=2, d(5)=1+1=2 d(6)=1+1 S= S Sk+1 =1,2,3 4,5,6=1,2,3,4,5,65:06573、边、边权任意时权任意时v1到各点的到各点的算法算法5:0658V1V4V5V2V3V647822-23122D1=0 d2=d3=d4=d5=d6= V2的父结点为的父结点为V1,V3, 经经

25、V1到达到达V2的距离为的距离为7,而而D3均为均为，故故d2=7 V3的父结点为的父结点为V1,V5,经过经过V1到达到达V3的距离为的距离为8,而而D5为为，故最小为故最小为D3=8. V4的父结点为的父结点为V2,V5,经过经过V2达到达到V4的距离为的距离为D2+W24=7+4=11,而而D5为为,d4=11。78115:0659 V5的父结点为的父结点为V2,V6,经经V2达到距离达到距离=D2+w(2,5)=8,而而D6=,故故d5=8 V6的父结点为的父结点为V2,V3,经经V2到达到达=D2W26=9,经经过过V3到达到达=D3+W36=10,最小为最小为9，而，而D6原值为原

26、值为，故，故D6=9.V1V4V5V2V3V647822-231227811985:0660V2的父为的父为V1,V3, 故故d2不变不变。V3的父为的父为V1,V5,经过经过V1到达到达V3的距离为的距离为8, 经经V5到达为到达为8-2=6,故故d3=6V4的父为的父为V2,V5,经过经过V2达到达到V4的距离为的距离为11,经经D5达到为达到为10，d4=10。V5的父为的父为V2,V6,经经V2距离距离8，经，经V6为为13,不变不变。V6的父为的父为V2,V3,经经V2为为9,经经V3为为8，D6为为8。V1V4V5V2V3V647822-231227610885:0661V2的父为

27、的父为V1,V3, 故故d2不变不变。V3的父为的父为V1,V5,因因d1,d5未动，故未动，故d3不变不变V4的父为的父为V2,V5,经过经过V2达到达到V4的距离为的距离为11,经经D5达到为达到为10，d4=10 不变不变。V5的父为的父为V2,V6,经经V2距为距为8，经，经V6为为13,不变不变。V6的父为的父为V2,V3,经经V2为为9,经经V3为为8，D6为为8不变不变V1V4V5V2V3V647822-231227610885:06623、边权可正可负时的算法、边权可正可负时的算法-改进改进 前面介绍的方法即 Ford算法工作量由算法工作量由“迭代迭代次数次数”确定，确定，先删

28、除权为负数的边先删除权为负数的边，用，用Dijkstra算法得到最短路径，按路长从低到高算法得到最短路径，按路长从低到高排队，重新编号。排队，重新编号。 再再添上负数边添上负数边，将，将D法得到的路长作为路长的法得到的路长作为路长的初值，以提高运算速度。初值，以提高运算速度。5:06631)D1=0 d2=7,d3=8,d4=d5=d6= S=12) S=2,3,4,5,6，其路长最小为，其路长最小为d2,值为值为7，故，故S=1,2, 2的后继距离调为的后继距离调为D4=11,d5=8,d6=9 此时：此时： S=3,4,5,6D1=0 d2=7,d3=8 D4=11,d5=8,d6=9V1

29、V4V5V2V3V647822-231227811895:0664V1V4V5V2V3V647822-23122D1=0 d2=7,d3=8 D4=11,d5=8,d6=93) S=3,4,5,6,路长路长最小为最小为d3的的8，V3的未处理的未处理的后继的后继V6,D6不变不变,S=1,2,3.4) S=4,5,6,路最短为路最短为D5之之8，D5之未处理的之未处理的后继后继V4，经，经V5的路长为的路长为10原值，原值，D4=10. S=1,2,3,5.D1=0 d2=7,d3=8 D4=10,d5=8,d6=95:0665V1V4V5V2V3V647822-23122D1=0 d2=7,

30、d3=8 D4=10,d5=8,d6=95) S=4,6，路最小为，路最小为D6之之9，V6之未处理的之未处理的后继没有。后继没有。S=1,2,3,5,66)未处理的为未处理的为4,路最小为路最小为d4之之10。5:0666D1=0 d2=7,d3=8 D4=10,d5=8,d6=94) S=4,5,6,路最短为路最短为D5之之8，D5之未处理的后继之未处理的后继V4，经，经V5的路长为的路长为10原值，原值，D4=10. S=1,2,3,5.a)D1=0 d2=7,d3=8 D4=10,d5=8,d6=9b)for (i=2;i6;i+)V2的直接前趋为的直接前趋为V2,V3,D2不变不变。

31、V3的直接前趋为的直接前趋为V1,V5,经经V5路长为路长为d5+w53=8-2=6D3 故故D3=6.V4的直接前趋为的直接前趋为V2,V5,不变不变V5的直接前趋为的直接前趋为V2,V6,不变不变V6的直接前趋为的直接前趋为V2,V3,D3已变已变,D6=8，V1V4V5V2V3V647822-231227810895:06672.72.7关关键路径键路径概念概念 一项工程技术由很多工作步骤组成，有些可以并一项工程技术由很多工作步骤组成，有些可以并行，有些只能串行行，有些只能串行， 如如何估计工期何估计工期？ 如如何控制工期？何控制工期？ 抓住主要矛盾，抓住抓住主要矛盾，抓住关键路线关键路

32、线，便解决问题。，便解决问题。5:0669序号序号名称名称时间时间先期工序先期工序1基础设施基础设施152下部砌砖下部砌砖513电线安装电线安装414圈梁安装圈梁安装325水暖管道水暖管道426大梁安装大梁安装24,57楼板吊装楼板吊装26，9，108楼板浇模楼板浇模36，9，109吊装楼梯吊装楼梯34，510上部砌砖上部砌砖42土建工程的控制点土建工程的控制点5:0670v1v11v3v8v10v2v4v6v5v9v715423451553232345344图图中中Vi表示表示作业作业，以，以Vi为始点的为始点的边之权边之权是作业是作业Vi时间时间。如如V3的作业时间是的作业时间是4天。天。

33、Vi最早开始最早开始时间是以时间是以Vi为终点为终点的系列作业的完成时刻的系列作业的完成时刻。如如V3最早开工时间最早开工时间V1作业作业15天后。天后。作业图作业图5:0671作作业业6开工，须开工，须4、5已完工，已完工，4、5完工须完工须2已完工，已完工，V1V2V4V6所花所花23天，天，V1 V2 V5V6所花所花24天，天，所所以作业以作业6最早开工为第最早开工为第24天，天，开开工日期工日期为为V1Vi的最长路长，的最长路长，与与最短路长相反，算法类似。最短路长相反，算法类似。5:0672v1v11v3v8v10v2v4v6v5v9v715423451553232345344最早

34、开工最早开工时间时间,求最长路长求最长路长，一代接一代。，一代接一代。初始化初始化d1=0,d3=d2=15,有边直接相连。有边直接相连。到到V2,V3后代的最长值后代的最长值d4=d5=d10=20,d11=19到到V4,V5,V10后代的最长值后代的最长值d6=d9=d7=d8=24到到V6,V9,V7,V8后代后代d7=27=d8到到V7,V8后代后代d11=30v31515202020v1v11v8v10v2v4v6v5v9v715423451553232345344245:0673 V9的前趋的前趋V4,V5,最长路为最长路为d9=24 V8的前趋的前趋V9,V10,最长路最长路D8

35、=27 V7的前序的前序V6,V9,最长路最长路D7=27v32020201515v1v11v8v10v2v4v6v5v9v71542345155323234534424242727 V11的前序的前序V3,V7,V8,最长路最长路D11=30305:0674PT(Potential Task)不存在有向回路不存在有向回路,否否则某些工序在自身已完工后才能开工则某些工序在自身已完工后才能开工,显然错的显然错的。由引理可知存在入度或出度为由引理可知存在入度或出度为0的结点的结点,如如V1入度为入度为0,V11出度为出度为0.v1v11v3v8v10v2v4v6v5v9v7154234515532

36、323453445:0675重新编号重新编号: 为为简化计算简化计算,便于计算机处理便于计算机处理,须对图中的结点须对图中的结点重新编号重新编号,使使起点编号起点编号终点编号终点编号, 如如V10V8边重新编号。边重新编号。v32020201515v1v11v8v10v2v4v6v5v9v71542345155323234534424242727305:0676 按按上述方式编号后上述方式编号后,假定假定V1到各点的最长路长到各点的最长路长为为D1,D2,Dn,则则 Dj=max(Di+Wij) 1 ij. 直直接前趋结点到接前趋结点到Vj的最长路的最长路长长. 算法算法1: a)对结点重新编

37、号为对结点重新编号为V1,V2,Vn b)对对j从从2到到n,计算计算Dj=max(Di+Wij) 1 iji是是Vj的直接前趋结点的直接前趋结点. 由由此得到此得到PT图中最长的路即为一条关键路径图中最长的路即为一条关键路径, 其其长度为整个工程的最早完工时间长度为整个工程的最早完工时间, 该该路上的工序不能延误路上的工序不能延误, 现现考虑非关键工序考虑非关键工序,最多可以耽误多长时间最多可以耽误多长时间,最晚最晚开工时间开工时间.5:0677 设设D(n)是工程完工的是工程完工的最早时间最早时间, 工序工序i的的最晚开工最晚开工时间时间T(i)=D(n)-D(i,n)=最最早完工早完工-

38、工工序序i到到n的最长路长。的最长路长。 D(i,n)为为Vi到到Vn的最长路的最长路,将图将图G的各边方向反向而权重不的各边方向反向而权重不变得到新图变得到新图G, G中中Vi到到Vn的最长路长等于的最长路长等于G中中Vn到到Vi的最长路长的最长路长. 由由于于G不存在回路不存在回路,那么那么G中也不存在回路中也不存在回路, 故故用可算法用可算法1计算计算D(n,i), 从从而得到每道工序的最晚开工时间而得到每道工序的最晚开工时间T(i)=D(n)-D(i,n).最晚时间最晚时间5:0678T11=30(必须保证，不能延迟必须保证，不能延迟),由由此倒推此倒推T10=26,T9=30-3=2

39、7,T8=30-2=28,T7=为保证后继为保证后继V9,V8最晚最晚开工开工, 较少值较少值-V7的作业时长的作业时长，故，故T7=24. 或或T7=30-d(7,11)最长路最长路.15423451553232345344V1V2V3V4V5V6V7V8V9V10V1115202020242427271530262728 24最晚时间最晚时间5:0679T6为保为保V8,V9最晚开工最晚开工,较小值较小值27-2=25, 最迟最迟25;T5为保为保V8,V9最晚开工最晚开工,较小值较小值27-4=23故最迟故最迟23,T4为保为保V6,V7最晚开工最晚开工,较小值较小值24-4=20T3为

40、保为保V6,V7最晚开工最晚开工,较小值较小值24-3=21T2为保为保V3,V4,V5最晚开工最晚开工,较小值较小值20-5=15. 关键路上不能晚关键路上不能晚15423451553232345344V1V2V3V4V5V6V7V8V9V10V1115202020242427271530262728 2425232021155:0680PERT 前前面面KP： 结结点为工序点为工序,边指向后继点边指向后继点 Programme Evaluation and Review Technique(计划评估和回顾技术计划评估和回顾技术)：一项大的或比较大的任一项大的或比较大的任务，总可按其完成工作

41、的顺序分解为若干作业务，总可按其完成工作的顺序分解为若干作业，并用一有向图表示，即，并用一有向图表示，即PERT图。图。 有有向边向边表示表示工序工序, 边权边权值值表表示完成该工序示完成该工序所所需需时间时间. 如如果果ei完成后完成后ej才能开始才能开始, 则则令令ej是是ei的终的终点点 只只有一个入度为有一个入度为0的顶点，表示任务开始阶段的顶点，表示任务开始阶段 只只有一个出度为有一个出度为0的顶点，表示任务结束的顶点，表示任务结束 前前例的例的PERT图如下图如下.5:0681v1v11v3v8v10v2v4v6v5v9v715423451553232345344V1151V243

42、52V33445104V46293V52783V65:0682 PERT图中不可能有有向回路图中不可能有有向回路。 V1Vn的最长路长度，为关键路径的最长路长度，为关键路径。 工工序序ek=(Vi,Vj)的最早启动时间是的最早启动时间是D(i), 按按算法算法1求出每点的最长路求出每点的最长路D(i).D1=0,工序工序1最早开工最早开工,D2=15,工序工序2,3最最早开工第早开工第15天，天，D3=20,工序工序4,5,10最早开工是第最早开工是第20天天D4=24,工序工序6,9最早开工是第最早开工是第24天天D5=27,工序工序8最工开工是第最工开工是第27天。天。5:0683V115

43、1V24352V33445104V46293V583V601520242730逆推逆推： 结点结点V5最晚最晚t5=30-3=27, 结点结点V4最晚最晚t4=27-3=24, 结点结点V3最晚最晚:24-3=21,24-4=20,27-4=23,t3=20 结点结点V2最晚最晚:30-4=26,20-5=15,t2=15 对于每个工序对于每个工序ek=(Vi,Vj)的最晚开工的最晚开工d(j)-w(i,j),如工如工序序6=27-2=25第第25天是最晚开工，最早天是最晚开工，最早24日。日。5:0684V1151V24352V33445104V46293V583V601520242730P

44、T(Potential Task)与与PERT(Programme Evaluation and Review Technique)相比：相比： PT图中用图中用“结点结点”表示工序，表示工序，PERT用用“边边”表示工表示工序序 故故将将PT转换转换PERT时，将时，将每个点转换成边每个点转换成边, 一一般般点数点数边数边数，故，故PERT比比PT要简单些。要简单些。 PT图更加灵活。图更加灵活。 计算方法类似计算方法类似 为为了便了便于计算，于计算，需重新编号，保证每边的需重新编号，保证每边的起点编号值起点编号值终点编号值。终点编号值。 5:06852.8 中国邮路中国邮路概念概念5:06

45、875:0688无向无向图的中国邮路图的中国邮路5:06895:0690V1V2V3V4V5V6V7V2与与V4度数为度数为3，首先使之为，首先使之为偶数偶数。重复部分重复部分长长=6，最小回路最小回路V1,V2,V3,V4。该回路长。该回路长=14，未过半。，未过半。24543326143V1V2V3V4V5V6V724543326143245:0691V3,V5,V6,V7是是单数单数，重复边如图，重复边如图，对对V3-V5间间重复重复边，在回路边，在回路V3-V5-V6上，超过一半。上，超过一半。 取反取反并调整如右并调整如右图图对对V3-V7间间重复重复边边，回，回路路V2-V1-V4

46、-V3-V7-V2重复为重复为9超超半，半，故故该回取反。该回取反。V1V2V3V4V5V6V72454332614324632V1V2V3V4V5V6V745433261432435:0692 将将所有的所有的单数的邻接单数的邻接点直接连起来，以最少点直接连起来，以最少代价使每个点变成偶数代价使每个点变成偶数。2V1V2V3V4V5V6V7454332614322432V1V2V3V4V5V6V745433261433415:0693有向图的中国邮路有向图的中国邮路 对于对于有向图有向图来说来说, 其原因是其原因是G中可能含有中可能含有出度出度(正度正度)或入度或入度(负度负度)为为0的结点，可能的结点