资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最短通路问题,离散数学,图论初步,南京大学计算机科学与技术系,最短通路问题离散数学图论初步,内容提要,引言,Dijkstra,算法,旅行商问题（,TSP,）,内容提要引言,埃德斯数（,Erds number,）,Paul Erds(1913-1996),Hungary,U.S.A.,Israel,Erds number,埃德斯数（Erds number）Paul Erds(,带权图与最短通路问题,带权图,：三元组,(,V,E,W,),，,(,V,E,),是图，,W,是从,E,到非负实数集的一个函数。,W,(,e,),表示边,e,的权。,一条通路上所有边的权的和称为该通路的长度。,两点之间长度,最小,的通路称为两点之间的最短通路，不一定是唯一的。,单源点最短路问题,给定带权图,G,(,V,E,W,),，并指定一个源点，确定该源点到图中其它任一顶点的最短路（长度和路径）。,带权图与最短通路问题带权图：三元组(V,E,W)，(V,Dijkstra,最短路径的算法思想,(1959),源点,s,到顶点,v,的最短路径若为,su,v,则,su,是,s,到,u,的最短路径。,(n-1),条最短路径按照其长度的非减次序求得，设它们的相应端点分别为,u,1,u,n-1,，最短路径长度记为,d(s,u,i,),，,i=1,n-1.,假设前,i,条最短路径已知，第,(i+1),条最短路径长度：,d(s,u,i+1,)=mind(s,u,j,)+W(u,j,u,i+1,)|j=1,i,Dijkstra最短路径的算法思想(1959)源点s到顶点v,求最短路径的,Dijkstra,算法,输入：连通带权图,G,，,|V,G,|=,n,指定顶点,s,V,G,输出：每个顶点,v,的标注,(L(,v,),u,),其中：,L(,v,),即从,s,到,v,的最短路径长度（目前可得的）,u,是该路径上,v,前一个顶点。,求最短路径的Dijkstra算法输入：连通带权图G，|VG|,求最短路的一个例子,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,b,a,c,d,e,f,g,h,求最短路的一个例子s77212412448353 4630b,求最短路的一个例子,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,1,c,2,c,8,c,7,c,4,c,U1,b,a,c,d,e,f,g,h,求最短路的一个例子s77212412448353 46301,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,1,c,2,c,8,c,7,c,4,c,U2,b,a,c,d,e,f,g,h,4,b,S1,s77212412448353 46301,c2,c8,c7,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,1,c,2,c,8,c,7,c,4,c,U3,b,a,c,d,e,f,g,h,4,b,S2,3,e,6,e,s77212412448353 46301,c2,c8,c7,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,1,c,2,c,8,c,6,e,4,c,b,a,c,d,e,f,g,h,U4,3,e,9,h,S3,s77212412448353 46301,c2,c8,c6,s,7,7,2,1,2,4,1,2,4,4,8,3,5,3,4,6,3,0,1,c,2,c,8,c,6,e,4,c,b,a,c,d,e,f,g,h,U5,3,e,9,h,S4,6,d,s77212412448353 46301,c2,c8,c6,求最短路的一个例子,(,续,),s,7,7,2,1,2,3,1,2,4,4,8,3,5,3,4,6,5,0,1,2,6,6,4,3,9,求最短路的一个例子(续)s77212312448353 46,求最短路的一个例子,(,续,),s,7,7,2,1,2,5,1,2,4,4,8,3,5,3,4,6,3,0,s,7,7,2,1,2,3,1,2,4,4,8,3,5,3,4,6,5,0,1,2,6,6,4,1,2,6,4,3,3,9,6,9,求最短路的一个例子(续)s77212512448353 46,Dijkstra,算法的描述,1,初始化：,i=0,S,0,=,s,L(,s,)=0,对其它一切,v,V,G,将,L(,v,),置为,。,若,n,=1,，结束。,2,v,S,i,=V,G,-S,i,比较,L(,v,),和,L(,u,i,)+,W,(,u,i,v,),的值,(,u,i,S,i,),如果,L(,u,i,)+,W,(,u,i,v,)L(,v,),则将,v,的标注更新为,(L(,u,i,)+,W,(,u,i,v,),u,i,),，,即：,L(,v,)=min L(,v,),min,u,Si,L(,u,)+,W,(,u,v,),3.,对所有,S,i,中的顶点，找出具有最小,L(,v,),的顶点,v,作为,u,i,+1,4,S,i+1,=S,i,u,i,+1,5.i=i+1;,若,i=n-1,终止。否则：转到第,2,步。,Dijkstra算法的描述1初始化：i=0,S0=s,Dijkstra,算法的,分析,可终止性,计数控制,正确性,需证明当算法终止时,L(,v,)=d(s,v,),对一切,v,成立。,由标记中的诸,u,i,确定的路径是一条最短路径,(,这里,d,(,s,v,),是,s,到,v,的最短路径长度，即距离。,),复杂性,O(n,2,),Dijkstra算法的分析可终止性,旅行商问题,(Travelling Salesman Problem,TSP),n,个城市间均有道路，但距离不等，,旅行商从某地出发，走过其它,n-1,城市各一次，最后回到原地，,如何选择最短路线？,数学模型：,无向带权,图,G,：,顶点对应于城市，边对应于城市之间的道路，道路长度用相应边的权表示。,问题的解：权最小的哈密尔顿回路。,G,是带权完全图，总共有,(n-1)!/2,条哈密尔顿回路。因此，问题是如何从这,(n-1)!/2,条中找出最短的一条。,(,含,25,个顶点的完全图中不同的哈密尔顿回路有约,3.1,10,23,条，若机械地检查，每秒处理,10,9,条，需,1,千万年。,),旅行商问题(Travelling Salesman Pro,旅行商问题,一个货郎（销售员）生活在城市,a,，假定访问的城市是,d,b,c,，然后回到,a,，求完成这次访问的最短路,径的,距离,.,18,14,b,c,a,d,11,10,12,7,旅行商问题一个货郎（销售员）生活在城市a，假定访问的城市是d,旅行商问题,解：列出哈密尔顿回路,并求其距离：,（,1,）（,abcda,）,=,（,12+7+11+18,）,=48,（,2,）（,acbda,）,=,（,14+7+10+18,）,=49,（,3,）（,abdca,）,=,（,12+10+11+14,）,=47,18,14,b,c,a,d,11,10,12,7,旅行商问题解：列出哈密尔顿回路,并求其距离：1814bca,哈密尔顿回路（路径）的最短路径问题,！,下面介绍一种,最邻近算法,：,（,1,）选择任一顶点作为始点，找出离始点距离最小的顶点，形成一条边的初始路径；,（,2,）设,u,是最新加到这条路径上的,顶,点，从不在这条路径上的所有,顶,点中选择一个与,u,距离最小的,顶,点,把连接,u,与此结点的边加入路径中；重复执行直到,G,中的各,顶,点均含在这条路径中。,旅行商问题,哈密尔顿回路（路径）的最短路径问题！旅行商问题,旅行商问题,（,3,）把始点到最后加入的,顶,点的边放入路径中得到一条哈密尔顿回路，并为近似最短的哈密尔顿回路,.,18,14,b,c,a,d,11,10,12,7,旅行商问题（3）把始点到最后加入的顶点的边放入路径中得到一,旅行商问题,(TSP),的研究进展,（在最坏情况下）时间复杂性为多项式的算法？,（在最坏情况下）时间复杂性为多项式的近似算法,保证,:,W,W,cW (c=3/2),误差为,50%,实际应用中，已有好的算法能够在几分钟内处理,1000,个节点的规模，误差在,2%,。,旅行商问题(TSP)的研究进展（在最坏情况下）时间复杂性为多,作业,教材,9.6,p.507:6,21,22,25,作业教材9.6,
展开阅读全文