图论与网络优化 讲稿(4)PPT.ppt

引例：1 哥尼斯堡七桥问题 哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。哥尼斯堡人在寻找一条路线从某点出发经过每个桥一次回到出发点。欧拉将其概括为数学模型，“七桥”问题变为“一笔画”问题。CDBA 2 欧拉图和中国邮递员问题 欧拉图：如果从某点出发能经过图的每个边恰好一次再回到出发点，那么称此图为欧拉图。图为欧拉图的充要条件是每个点的度是偶数。1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”：一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线3 哈密顿环球旅行问题 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）一：图论的基本概念 图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.定义1 一个有序二元组(V,E)称为一个图,记为G=(V,E),其中 V称为G的顶点集,V,其元素称为顶点或结点,简称点;E称为G的边集,其元素称为边,它联结V 中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V=v1,v2,vn是有限非空点集,则称G为有限图或n阶图.如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.图1图2并且常记V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.用N(v)表示图G中所有与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.定理1：在简单图中，所以点的度的和等于边 数的两倍.定理2（握手定理）：在简单图中，奇数点的个数为偶数.定义2 若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3 设G=(V,E)是一个图,v0,v1,vkV,且1ik,vi-1viE,则称v0 v1 vk是G的一条通路.如果通路中没有相同的边,则称此通路为道路.始点和终点相同的道路称为圈或回路.如果通路中既没有相同的边,又没有相同的顶点,则称此通路为路径,简称路.定义4 任意两点均有通路的图称为连通图.定义5 连通而无圈的图称为树,常用T表示树.图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中：例 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16 种状态.在河东岸的状态类似记作.由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.二：最短路与最小生成树 定义1 设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记则称F(P)为路径P(u,v)的权或长度(距离).定义2 若P0(u,v)是G 中连接u,v的路径,且对任意在G 中连接u,v的路径P(u,v)都有F(P0)F(P),则称P0(u,v)是G 中连接u,v的最短路.重要性质：若v0 v1 vm 是图G中从v0到vm的最短路,则1km,v0v1 vk 必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.Dijkstra标号算法标号算法 如果刚刚得到P标号的点是vi，那么，对于所有这样的点将其T标号修改为：minT(vj)，P(vi)+wij。若G中没有T标号，则停止。否则，把点 的T标号修改为P标号，然后再转入。其中，满足 开始，先给v1标上P标号P(v1)0，其余各点标上T标号T(vj)+（j1）。FloydFloyd算法算法 n n某些问题中，要求网络上任意两点间的最短路，如例某些问题中，要求网络上任意两点间的最短路，如例1515就是这样。这类问题可以用就是这样。这类问题可以用DijkstraDijkstra算法一次改变起点的算法一次改变起点的办法计算，但比较繁琐。这里介绍的办法计算，但比较繁琐。这里介绍的FloydFloyd方法（方法（19621962）可直接求出网络中任意两点间的最短路。可直接求出网络中任意两点间的最短路。n n为计算方便，令网络的权矩阵为为计算方便，令网络的权矩阵为 。其中其中 n n算法基本步骤为：算法基本步骤为：n n首先介绍矩阵的两种运算：首先介绍矩阵的两种运算：例例：某县下属7个乡镇，各乡镇所拥有的人口数a(vi)（i=1，2，7），以及各乡镇之间的距离wij（i，j=1，2，7）如图所示。现在需要设立一个中心邮局，为全县所辖的7个乡镇共同服务。问该中心邮局应该设在哪一个乡镇（顶点）？图10.2.3解解：第第1步步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij（i，j 1，2，7），并将其写成如下距离矩阵 第第2 2步步：以各顶点的载荷（人口数）加权，求每一个顶点至其他各个顶点的最短路径长度的加权和 第3步：判断。因为 所以，v3和v4都是图10.2.3的中位点。即：中心邮局设在点v3或点v4都是可行的。最小生成树 由树的定义不难知道,任意一个连通的p,q图(p个顶点q条边)G适当去掉q-p+1条边后,都可以变成树,这棵树称为图G的生成树.设T是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权.一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树.求最小生成树问题有很广泛的实际应用.例如,把n个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短,即费用最小,就是一个求最小生成树问题.求连通图G的最小生成树T的算法(Kruskal避圈法)：将图G中的边按权从小到大逐条考察,按不构成圈的原则加入到T 中,直到 q(T)=p(G)-1为止.例如右图,其中p(G)=8.其最小生成树如下：类似地,可定义连通图G 的最大生成树.破圈法算法2 步骤如下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈.去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树.加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；再加上弦e7，得到圈 v4v5v2v4,去掉最大的权边e6，得到一棵新树；如此重复进行，直到全全部的弦均已试过,得最小树.有序二元树定义：若一个树的出度为二，有方向即有父子，兄弟之分，则称其为有序二元树.有序二元树编码：(1)根不标码.(2)兄弟有序，左为兄，标0，右为弟，标1.(3)从根到叶的轨上依次抄出各点之码，称为该叶的前缀码.(4)全树的叶从左到右抄出前缀码叫做该树的前缀码，中间用逗号隔开.000U1110111010100000 a0001 f001 g010 h011 i100 n101 x11 z11 010 011 101 011 100 001 0000 0001 0000 100 001 0000 001Huffman树定义：以U0为根，U1 Un为叶的有序二元 树，Ui代表的实物出现的概率为Pi，P1+P2+Pn=1，Pi的码长为它的0，1的个数，计为Li，使得 P1 Li1+P2 L2+Pn Lin=min则称该有序二元树为Huffman树构造Huffman树例：求带权0.2，0.2，0.3，0.3的Huffman树0.40.20.20.30.30.20.20.30.30.40.6v0.40.60.20.20.30.3例：画出带权0.1，0.1，0.1，0.1，0.2，0.4的Huffman树。例：画出带权0.2，0.17，0.13，0.1，0.1，0.8，0.06，0.06，0.07，0.03的Huffman树0.10.10.10.10.20.20.20.40.40.4u二部图 定义定义1 1 设设X,Y 都是非空有限集都是非空有限集,且且XY=,E xy|xX,yY,称称G=(X,Y,E)为为二部图二部图.二部图可认为是有限简单二部图可认为是有限简单无向图无向图.色数：色数：2 2 如果如果X中的每个点都与中的每个点都与Y中的每个点邻接中的每个点邻接,则则称称G=(X,Y,E)为为完备二部图完备二部图.若若F：ER+,则称则称G=(X,Y,E,F)为为二部赋二部赋权图权图.二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij)|X|Y|,其中其中aij=F(xi yj).定义定义2 2 设设G=(X,Y,E)为二部图为二部图,且且M E.若若M中任意两条边在中任意两条边在G中均不邻接中均不邻接,则称则称M是是二部图二部图G的一个的一个匹配匹配.定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配,如果如果G的的每一个点都是每一个点都是M中边的顶中边的顶点点,则称则称M是二部图是二部图G的的完美匹配完美匹配；如果如果G中没有另外的匹配中没有另外的匹配M0,使使|M0|M|,|,则则称称M是二部图是二部图G的的最大最大匹配匹配.(NP.(NP问题问题)在二部赋权图在二部赋权图G=(X,Y,E,F)中中,权数最大的权数最大的最大匹配最大匹配M称为二部赋权图称为二部赋权图G的的最佳匹配最佳匹配.显然显然,每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一反之不一定成立定成立.工作安排问题之一 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几个工作人员中每个人能胜任一项或几项工作项工作,但并但并不是所有工作人员都能从事任何一不是所有工作人员都能从事任何一项工作项工作.比如比如x1能做能做y1,y2工作工作,x2能做能做y2,y3,y4工作工作等等.这样便提出一个问题这样便提出一个问题,对所有的工作人员能对所有的工作人员能不能都分配一件他所能胜任的工作？不能都分配一件他所能胜任的工作？我们构造一个二部图我们构造一个二部图G=(X,Y,E),这里这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当并且当且仅当工作人员工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.求二部图G=(X,Y,E)的最大匹配算法(匈牙利算法,P149)迭代步骤:从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和和标记标记*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*,则则M是是G的最大匹配的最大匹配.否则任取否则任取X中一个既有标号中一个既有标号又有标记又有标记*的点的点xi,去掉去掉xi的标记的标记*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有若所有这样的这样的yj都已有标号都已有标号,则转向则转向,否则转向否则转向.对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的 yj 都是都是M的的饱和点饱和点,则转向则转向,否则否则逆向返回逆向返回.即由其中即由其中M的任一个非饱和点的任一个非饱和点 yj 的标的标号号i 找到找到xi,再由再由 xi 的标号的标号k 找到找到 yk,最后由最后由 yt 的标号的标号s找到标号为找到标号为0 0的的xs时结束时结束,获得获得M-增广路增广路xs yt xi yj,记记P=xs yt,xi yj ,重新记重新记M为为M P,转向转向.M P=MP MP,是对称差是对称差.将将yj在在M中与之邻接的点中与之邻接的点xk,给以标号给以标号 j 和和标记标记*,转向转向.例 求下图所示二部图G的最大匹配.解解 取初始匹配取初始匹配M0=x2 y2,x3 y3,x5 y5 (上图粗线所示上图粗线所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标都给以标号号0 0和标记和标记*(如下图所示如下图所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(如下图所示如下图所示).).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相都给以相应的标号和标记应的标号和标记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相都给以相应的标号和标记应的标号和标记*(如下图所示如下图所示).去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号邻接且尚未给标号的三个点的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号邻接且尚未给标号的三个点的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆所以顺着标号逆向返回依次得到向返回依次得到x2,y2,直到直到x1为为0为止为止.于是得到于是得到M0的增广路的增广路x1 y2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=M0P=x1 y2,x2 y1,x3 y3,x5 y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆所以顺着标号逆向返回依次得到向返回依次得到x2,y2,直到直到x1为为0为止为止.于是得到于是得到M0的增广路的增广路x1 y2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=M0P=x1 y2,x2 y1,x3 y3,x5 y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后去掉然后去掉x4的标记的标记*,将与将与x4邻接的两个点邻接的两个点y2,y3都给以标号都给以标号4.因为因为y2,y3都是都是M1的两个饱和点的两个饱和点,所以将它们所以将它们在在M1中邻接的两个点中邻接的两个点x1,x3都给以相应的标号和标都给以相应的标号和标记记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,因为与因为与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所以去掉所以去掉x3的标记的标记*.而与而与x3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*(如下图所如下图所示示),因此因此M1是是G的最大匹配的最大匹配.G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配,当然也不存当然也不存在完美匹配在完美匹配.工作安排问题 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.如果每个工作人员工作效率不同如果每个工作人员工作效率不同,要求要求工作分配的同时考虑总效率最高工作分配的同时考虑总效率最高.我们构造一个二部赋权图我们构造一个二部赋权图G=(X,Y,E,F),这里这里X=x1,x2,xn,Y=y1,y2,yn,F(xi yj)为工作人员为工作人员xi胜任工作胜任工作yj时的工作效率时的工作效率.则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配.在求在求G 的最佳匹配时的最佳匹配时,总可以假设总可以假设G为完备二为完备二部赋权图部赋权图.若若xi与与yj不相邻不相邻,可令可令F(xi yj)=0.同样地同样地,还可虚设点还可虚设点x或或y,使使|X|=|Y|.如此就将如此就将G 转化为完备转化为完备二部赋权图二部赋权图,而且不会影响结果而且不会影响结果.定义定义 设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,若若L：X Y R+满足：满足：xX,yY,L(x)+L(y)F(xy),则称则称L为为G的一个的一个可行点标记可行点标记,记相应的生成子图记相应的生成子图为为GL=(X,Y,EL,F),),这里这里EL=xyE|L(x)+L(y)=F(xy).求完备二部赋权图求完备二部赋权图G=(X,Y,E,F)的最佳匹的最佳匹配算法迭代步骤配算法迭代步骤(P152)(P152)：（：（KMKM算法算法)设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,L是其是其一个初始可行点标记一个初始可行点标记,通常取通常取 L(x)=max F(x y)|yY,xX,L(y)=0,yY.M是是GL的一个匹配的一个匹配.若若X的每个点都是饱和的的每个点都是饱和的,则则M是最佳匹配是最佳匹配.否则取否则取M的非饱和点的非饱和点uX,令令S=u,T=,转向转向.记记NL(S)=v|uS,uvGL.若若NL(S)=T,则则GL没有完美匹配没有完美匹配,转向转向.否则转向否则转向.调整标记调整标记,计算计算aL=minL(x)+L(y)-F(xy)|xS,yYT.由此得新的可行点标记由此得新的可行点标记 令令L=H,GL=GH,重新给出重新给出GL的一个的一个匹配匹配M,转向转向.取取yNL(S)T,若若y是是M的饱和点的饱和点,转向转向.否则否则,转向转向.设设x yM,则令则令S=S x,T=T y,转向转向.在在GL中的中的u-y路是路是M-增广路增广路,设为设为P,并令并令 M=M P,转向转向.欧拉图和中国邮递员问题 欧拉图：如果从某点出发能经过图的每个边恰好一次再回到出发点，那么称此图为欧拉图。图为欧拉图的充要条件是每个点的度是偶数。1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”：一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线弗罗莱（弗罗莱（Fleur y）算法）算法弗罗莱（Fleur y）算法思想解决欧拉回路 Fleur y算法：任取v0V(G)，令P0=v0；设Pi=v0e1v1e2e i vi已经行遍，按下面方法从中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为G i=G-e1,e2,e i中的桥（所谓桥是一条删除后使连通图不再连通的边）；（c）当（b）不能再进行时，算法停止。这个问题可以转化为：给定一个具有非负权的赋这个问题可以转化为：给定一个具有非负权的赋权图权图GG，（1 1）用添加重复边的方法求）用添加重复边的方法求GG的一个的一个EulerEuler赋权母图赋权母图GG*，使得，使得 （2 2）求）求GG*的的Euler Euler 回路。回路。这个问题可以由这个问题可以由Fleur yFleur y算法和算法和19731973年著名组合数学年著名组合数学家家J.EdmondsJ.Edmonds和和Johnson Johnson 给出的一个好的算法解决。给出的一个好的算法解决。算法步骤如下：(1)若G中无奇点，令G*=G，转2，否则转3；(2)求G*中的欧拉回路，结束；(3)求G中所有奇点对之间的最短路径；(4)以G中奇点集V为顶点集，边(v i,v j)的权为之间最短路径的权，得完全带权图K2k；(5)求K2k中最小权完美匹配M；(6)将M中边对应的各最短路径中的边均在G中加重复边，得欧拉图G*，转2。V4U6U53U1U2V1V3U3U4V21111111322222345G2 奥数题：设邮递员从邮局A出发，沿方格形街路走遍所有街路后回到邮局，若方形路的每条路长为1（千米），问邮递员至少要走多少路程？AHamilton图图 1)981)98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾.为考察灾情、为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视.巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线.情巡视路线情巡视路线”中的前两个问题是这样的：中的前两个问题是这样的：1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时.要在要在24小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数公路边的数字为该路段的公里数.2)2)问题分析：问题分析：本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条镇、村之间的公路看作此图对应顶点间的边，各条再回到点再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点图中寻找从给定点O出发，行遍所有顶点至少一次出发，行遍所有顶点至少一次 如第一问是三个旅行售货员问题，第二问是四如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸多旅行售货员问题多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题.有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）最小的闭链（闭迹）.个旅行售货员问题个旅行售货员问题.即求解没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解的问题可使用近似算法来求得近似最优解.旅行售货员问题旅行售货员问题 定义定义设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的哈密尔顿路的哈密尔顿路(Hamilton路路或或H路路).包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈).含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图).旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题.一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？而总距离最小？它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优圈最优圈.但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解只能找一种求出相当好（不一定最优）的解.一个可行的办法一个可行的办法:是先求一个是先求一个H圈圈,然后适当然后适当修改修改,以得到具有较小权的另以得到具有较小权的另一个一个H圈圈.定义 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C的一个的一个改进改进.二边逐次修正法二边逐次修正法:在接连进行一系列修改之后在接连进行一系列修改之后,最后得一个圈最后得一个圈,不能不能再用此方法改进了，这个最后的圈可能不是最优的再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它是比较好的，为了得到更高的精度，这个程序可以重复几次，每次都以不同的圈开始程序可以重复几次，每次都以不同的圈开始.这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.例例对下图对下图16的的K6,用二边逐次修正法求用二边逐次修正法求较优较优H圈圈.较优较优H圈圈:其权为其权为W(C3)=192 分析分析:找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，圈的一个下界，方法如下方法如下：设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v,C-v是是G-v的路，也的路，也G-v是的生成树是的生成树.如果如果T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联的边中权最小的两条关联的边中权最小的两条边边,则则w(T)+w(e1)+w(e2)将是将是w(C)的一个下界的一个下界.取取v=v3,得得G-v3的一的一最小生成树最小生成树(实线实线),其其权权w(T)=122,与与v3关联关联的权最小的两条边为的权最小的两条边为w(T)+w(v1v3)+w(v2v3)=178.故最优故最优H圈的权圈的权v1v3和和v2v3,故故w(C)应满足应满足178 w(C)192.6.最佳灾情巡视路线的模型的建最佳灾情巡视路线的模型的建立与求解立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O出发出发,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O,使得使得总权总权(路程或时路程或时时间时间)最小最小,即即最佳旅行售货最佳旅行售货员问题员问题.最佳旅行售货员问题是最佳旅行售货员问题是NP完全问题完全问题,采用一种采用一种近似算法求其一个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路,构造出完全图构造出完全图2)输入图输入图 的一个初始的一个初始H圈；圈；3)用对角线完全算法（见用对角线完全算法（见3）产生一个初始圈）产生一个初始圈;4)随机搜索出随机搜索出 中若干个中若干个H圈，例如圈，例如2000个；个；5)对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正法进行优化，得到近似最优H圈；圈；6)在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权最小的一个,此即要找的最优此即要找的最优H圈的近似解圈的近似解.因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关,故本算法故本算法第第2)，3)，4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以保证能得到较优的计算结果证能得到较优的计算结果.问题一问题一 若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题此问题是多个售货员的最佳旅行售货员问题.4)此问题包含两方面：此问题包含两方面：a)对顶点分组对顶点分组,b)在每组中在每组中求求(单个售货员单个售货员)最佳旅行售货员回路最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法存在多项式时间内的精确算法.故故多多也不也不 而图中节点数较多，为而图中节点数较多，为53个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1进行粗步划分后进行粗步划分后,求求出各部分的近似最佳旅行售货员回路的权出各部分的近似最佳旅行售货员回路的权,再进一再进一进一步进行调整，使得各部分满足均衡性条件进一步进行调整，使得各部分满足均衡性条件3).从从O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O点到该点的最短路点到该点的最短路.故用软件包求出故用软件包求出O点到其余顶点的最短路点到其余顶点的最短路.这些最短路构成一棵这些最短路构成一棵O为树根的树为树根的树.将从将从O点出发的树枝称为点出发的树枝称为干枝干枝.从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为分别为，.在分组时应遵从准则：在分组时应遵从准则：准则准则1 尽量使同一干枝上及其分枝上的点分在同一组尽量使同一干枝上及其分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组；准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：由上述分组准则，我们找到两种分组形式如下：分组分组1:（，），（），（，），（），（，）分组分组2:（，），（），（，），（），（，）分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.分组分组2:(,),(,),(,)对分组对分组2中每组顶点的生成子图中每组顶点的生成子图,用算法一求出近用算法一求出近似最优解及相应的巡视路线似最优解及相应的巡视路线.在每个子图所构造的完全图中在每个子图所构造的完全图中,取一个尽量包含上取一个尽量包含上图中树上的边的图中树上的边的H圈作为其第圈作为其第2)步输入的初始圈步输入的初始圈.分组分组2的近似解的近似解 因为该分组的均衡度因为该分组的均衡度.所以此分法的均衡性很差所以此分法的均衡性很差.为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C,2,3,D,4分给第分给第组（顶点组（顶点2为这两组的公共点），重新分为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.因该分组的均衡度因该分组的均衡度 所以这种分法的均衡性较好所以这种分法的均衡性较好.问题二问题二 当巡视人员在各乡（镇）、村的停留当巡视人员在各乡（镇）、村的停留停留时间一定停留时间一定,汽车的行驶速度一定汽车的行驶速度一定,要在要在24小时内小时内完成巡视完成巡视,至少要分几组及最佳旅行的巡视路线至少要分几组及最佳旅行的巡视路线.由于由于T=2小时小时,t=1小时小时,V=35公里公里/小时小时,需访问需访问的乡镇共有的乡镇共有17个，村共有个，村共有35个个.计算出在乡计算出在乡(镇镇)及及村的总停留时间为村的总停留时间为17 2+35=69小时，要在小时，要在24小时小时内完成巡回，若不考虑行走时间，有内完成巡回，若不考虑行走时间，有:69/i24(i为为分的组数分的组数).得得i最小为最小为4，故，故至少要分至少要分4组组.由于该网络的乡由于该网络的乡(镇镇)、村分布较为均匀、村分布较为均匀,故有可故有可能找出停留时间尽量均衡的分组能找出停留时间尽量均衡的分组,当分当分4组时各组停组时各组停停留时间大约为停留时间大约为69/4=17.25小时，则每组分配在路小时，则每组分配在路路途上的时间大约为路途上的时间大约为24-17.25=6.75小时小时.而前面讨而前面讨论过论过,分三组时有个总路程分三组时有个总路程599.8公里的巡视路线，公里的巡视路线，分分4组时的总路程不会比组时的总路程不会比599.8公里大太多公里大太多,不妨以不妨以599.8公里来计算公里来计算.路上约用路上约用599.8/35=17小时小时,若平若平均分配给均分配给4个组个组,每个组约需每个组约需17/4=4.25小时小时6.75小小小时小时,故分成故分成4组是可能办到的组是可能办到的.现在尝试将顶点分为现在尝试将顶点分为4组组.分组的原则：除遵从分组的原则：除遵从前面准则前面准则1、2、3外，还应遵从以下准则：外，还应遵从以下准则：准则准则4 尽量使各组的停留时间相等尽量使各组的停留时间相等.用上述原则在下图上将图分为用上述原则在下图上将图分为4组，同时计算组，同时计算各组的停留时间各组的停留时间,然后用算法一算出各组的近似最然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间从而得出完成巡视的近似最佳时间.用算法一计用算法一计计算时，初始圈的输入与分三组时同样处理计算时，初始圈的输入与分三组时同样处理.这这4组的近似最优解见表组的近似最优解见表3.