图论中的几个典型问题上

《图论中的几个典型问题上》由会员分享，可在线阅读，更多相关《图论中的几个典型问题上（70页珍藏版）》请在金锄头文库上搜索。

1、图论中的几类典型问题（上）图论中的几类典型问题（上）二二. .行遍性问题：中国邮递员问题，货行遍性问题：中国邮递员问题，货郎担问题郎担问题( (旅行售货商题旅行售货商题HamiltonHamilton问题）问题）三三. .建模竞赛中的实例建模竞赛中的实例一一. .最短路问题最短路问题1重要性质：重要性质： 若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也即：最短路是一条路，且最短路的任一段也是最短路是最短路. 求非负赋权图求非负赋权图G中某一点到其它各

2、点最短路，中某一点到其它各点最短路，一般用一般用Dijkstra标号算法标号算法；求非负赋权图上任意；求非负赋权图上任意两点间的最短路，一般用两点间的最短路，一般用Floyd算法算法. .这两种算法这两种算法均适用于有向非负赋权图均适用于有向非负赋权图. . 一一. .最短路问题最短路问题2固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路3求赋权图中固定起点的最短路的求赋权图中固定起点的最短路的Dijkstr

3、a算法：算法：4算法步骤：算法步骤：5 TO MATLAB(road1)6u1u2u3u4u5u6u7u87算法的基本思想算法的基本思想返回返回求赋权图中任意两点的最短路的求赋权图中任意两点的最短路的Floyd算法：算法：8算法原理算法原理 求距离矩阵的方法求距离矩阵的方法返回返回9算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R 即当即当vk被插入任何两点间的最短被插入任何两点间的最短路径时，被记录在路径时，被记录在R(k)中，依次中，依次求求 时求得时求得 ，可由，可由 来查找来查找任何点对之间最短路的路径任何点对之间

4、最短路的路径10ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点则由点i到到j的最短路的路径为：的最短路的路径为：11 设设A = (aij )nn为赋权图为赋权图G = (V, E, F)的权矩阵的权矩阵, dij表示从表示从vi到到vj点的距离点的距离, rij表示从表示从vi到到vj点的最短点的最短路中一个点的编号路中一个点的编号. 赋初值赋初值. 对所有对所有i, j, dij = aij, rij = j. k = 1. 转转向向. 更新更新dij , rij . 对所有对所有i, j, 若若dik + dk jdij , 则令则令di

5、j = dik + dkj , rij = k, 转向转向; 终止判断终止判断. 若若k = n终止终止; 否则令否则令k = k + 1, 转向转向. 最短路线可由最短路线可由rij得到得到. 算法步骤算法步骤12例例2 2 求下图中任意两点间的最短路求下图中任意两点间的最短路: :13 解解：用：用Floyd算法算法, ,首先写出其首先写出其( (对称的对称的) )权矩权矩阵阵A = (aij )88，然后利用计算机编程计算，然后利用计算机编程计算. . 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 0 2 8 1 1 1 2 0 6 1 2 0 6

6、1 2 2 8 6 0 7 5 1 2 8 6 0 7 5 1 2 3 3 1 7 0 9 1 7 0 9 4 4 1 5 0 3 8 1 5 0 3 85 5 1 3 0 4 6 1 3 0 4 66 6 2 9 4 0 3 2 9 4 0 37 7 8 6 3 0 8 6 3 014以下仅从图上进行直观操作以下仅从图上进行直观操作. 根据若根据若dik + dkjdij , 则令则令dij = dik + dkj . .将原来将原来的的赋权值改变为赋权值改变为|v2v4|=4, ,|v5v6|=3. . 再依次改变为再依次改变为|v1v2|=5, ,|v0v2|=7. . 接下来根据接下来

7、根据若若dij = dik + dkj , ,则删除则删除vi到到vj的连的连线线. .得到得到15从上图中容易得到任意两点间的最短路从上图中容易得到任意两点间的最短路. .例如例如, ,v1到到v6的路有三条：的路有三条： v1v0v3v2v6( (长度为长度为12),12), v1v4v5v2v6( (长度为长度为7),7), v1v4v7v6( (长度为长度为12).12).16 TO MATLAB(road2(floyd)17最优截断切割问题最优截断切割问题 问题：从长方体中经问题：从长方体中经6 6次截断切割切出一个已知尺寸、次截断切割切出一个已知尺寸、位置预定的长方体位置预定的长方

8、体( (两长方体对应表面平行两长方体对应表面平行) )，设水平切，设水平切割单位面积费用是垂直切割单位面积费用割单位面积费用是垂直切割单位面积费用r r倍倍. .当先后两当先后两次切割的平面不平行时，因调整刀具需额外费用次切割的平面不平行时，因调整刀具需额外费用e.e.试设试设计各面加工次序计各面加工次序( (称称“切割方式切割方式”) )方法，使加工费用最方法，使加工费用最少少. .假假 设设1. 水平切割单位面积费用为水平切割单位面积费用为r，垂直切割单位面积费用，垂直切割单位面积费用1；2.先后两次切割平面不平行时，调整刀具需额外费用先后两次切割平面不平行时，调整刀具需额外费用e；3.第

9、一次切割前，刀具已调整完毕，即第一次垂直切割不第一次切割前，刀具已调整完毕，即第一次垂直切割不加入刀具调整费用；加入刀具调整费用；4.每个待加工长方体必须经每个待加工长方体必须经6次截断切割次截断切割.18模型的建立与求解模型的建立与求解设待加工长方体的左右面、前后面、上下面间距离分别设待加工长方体的左右面、前后面、上下面间距离分别为为 a0、b0、c0 ，六个切割面，六个切割面Mi i=1、2、3、4、5、6分别位分别位于左、右、前、后、上、下，这六个面与待加工长方体于左、右、前、后、上、下，这六个面与待加工长方体相应外侧面的边距分别为相应外侧面的边距分别为 ui i=1、2、3、4、5、6

10、. 这样这样, 一一种切割方式就是六个切割面一个排列种切割方式就是六个切割面一个排列, 共共P66=720种切割种切割方式方式. 当考虑切割费用时，显然有局部优化准则：两个当考虑切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工平行待切割面中，边距较大的待切割面总是先加工. 由此准则由此准则,在求最少加工在求最少加工费用时只需考虑费用时只需考虑 种切割方式种切割方式.19设设u1u2，u3u4，u5u6，故只考虑，故只考虑M1在在M2前、前、M3在在M4前、前、M5在在M6前的切割方式前的切割方式. 1、e=0 的情况的情况 构造有向赋权网络构造有向赋权网络图图G

11、(V,E).为了表为了表示切割过程的有向示切割过程的有向性，在网络图上加性，在网络图上加上坐标轴上坐标轴x，y，z. 图图9-13 G(V,E) 20 (1) 图中点图中点Vi(xi,yi,zi)表示被切石材所处状态表示被切石材所处状态. 坐标坐标xi、yi、zi分别代表石材在左右、前后、上下方向已被切割的刀数分别代表石材在左右、前后、上下方向已被切割的刀数. 如：如：V24(2,1,2) 表示石材在左右方向上已切两刀，前后方表示石材在左右方向上已切两刀，前后方向被切一刀，上下方向被切两刀，即面向被切一刀，上下方向被切两刀，即面M1、M2、M3、M5、M6均已被切割均已被切割. 顶顶V1(0,

12、0,0) 表示石材最初待加工状表示石材最初待加工状态，顶态，顶V27(2,2,2)表示石材加工完成状态表示石材加工完成状态. (2) 长方体长方体石材从状态石材从状态Vi一次切割变为一次切割变为VjVi(xi, yi, zi)到到Vj(xj, yj, zj)有弧有弧(Vi,Vj)，相应弧上的权，相应弧上的权W(Vi,Vj)为此切为此切割过程的费用割过程的费用. W(Vi,Vj)=(xj -xi)(bi ci)+(yj -yi)(ai ci)+(zj -zi)(ai bi)r 其中，其中，ai、bi、ci分别代表在状态分别代表在状态Vi时，长方体的左右时，长方体的左右面、上下面、前后面之间的距离

13、面、上下面、前后面之间的距离. 例如，状态例如，状态V5(1,1,0)，a5=a0+u1, b5=b0+u3, c5= c0; 状态状态V6(2,1,0); W(V5,V6)(b0+u3)c0.21(3)根据准则知第一刀应切根据准则知第一刀应切M1、M3、M5中某个面，分别中某个面，分别对应弧对应弧( V1,V2)，(V1,V4)，(V1,V10). 从从V1到到V27任意一条任意一条有向路代表一种切割方式有向路代表一种切割方式. 共对应共对应90种切割方式种切割方式. V1到到V27的最短路对应所求的最优切割方式的最短路对应所求的最优切割方式 实例：待加工长方体和成品长方体的长、宽、高分实例

14、：待加工长方体和成品长方体的长、宽、高分别为别为10、145、19 和和3、2、4，两者左侧面、正面、底面，两者左侧面、正面、底面之间的距离分别为之间的距离分别为6、7、9，则边距如下表：，则边距如下表：V1V10V13V22V23V26V27，其权为，其权为374r=1时，求得最短路为时，求得最短路为:u1u2u3u4u5u66175569对应最优切割为对应最优切割为M5M3M6M1M4M2， 费用为费用为374元元. 222、 e 0的情况的情况 先后两次切面不平行时，需加调刀费先后两次切面不平行时，需加调刀费e. 图图9-13中某些边在所有切割序列中顺序不同，故所加权不中某些边在所有切割

15、序列中顺序不同，故所加权不同同. 怎么办怎么办? 先切一对平行面，再切另外一对平行面，先切一对平行面，再切另外一对平行面，总费用比总费用比e=0时的费用增加时的费用增加e. 先切一个，再切一对平行面，最后割剩余先切一个，再切一对平行面，最后割剩余的一个，总费用比的一个，总费用比e=0时的费用增加时的费用增加2e. 切割面是两两相互垂直，总费用比切割面是两两相互垂直，总费用比e=0时的时的费用增加费用增加3e. 所考虑所考虑90种切割中，上述三种情况下切面的排列种切割中，上述三种情况下切面的排列及在图及在图G中对应有向路必经点如下表：中对应有向路必经点如下表： 四个垂直面的切割顺序只有三种可能情

16、况：四个垂直面的切割顺序只有三种可能情况： 23垂直切割面排列情形垂直切割面排列情形有向路必有向路必经点点情况一情况一 (1)M1M2M3M4(1,0,z),(2,0,z),(2,1,z)情况一情况一 (2)M3M4M1M2(0,1,z),(0,2,z),(1,2,z)情况二情况二 (1)M3M1M2M4(0,1,z),(1,1,z),(2,1,z)情况二情况二 (2)M1M3M4M2(1,0,z),(1,1,z),(1,2,z)情况三情况三 (1)M1M3M2M4(1,0,z),(1,1,z),(2,1,z)情况三情况三 (2)M3M1M4M2(0,1,z),(1,1,z),(1,2,z)z

17、=0,1,2 24由上表知由上表知: 三种情况中三种情况中 情形情形(1)有公共点有公共点集集(2,1,z)|z=0,1,2， 情形情形(2)有公共点集有公共点集(1,2,z)|z=0,1,2. 情形情形(1)的有向路不通过情形的有向路不通过情形(2)的公共点集，的公共点集， 情形情形(2)的有向路也不通过情形的有向路也不通过情形(1)的公共点集的公共点集.故这两部分是独立的、互补的故这两部分是独立的、互补的.在图在图G中分别去掉点集中分别去掉点集(1,2,z)|z=0,1,2和和(2,1,z)|z=0,1,2及与之相关联的入弧，形成及与之相关联的入弧，形成1和和2两两个新图个新图. 则则1和

18、和2具有互补性具有互补性. 所求最短路必存在于所求最短路必存在于1和和2某一个中某一个中. 调整调整3次刀具，总费用增加次刀具，总费用增加3e，先安排此情况的，先安排此情况的权增加值，每次转刀，给其待切弧上的权增加权增加值，每次转刀，给其待切弧上的权增加e. 如如图图9-14所示所示. 再判断是否满足调整二次、一次刀具时再判断是否满足调整二次、一次刀具时的情况，发现所加的权满足另外两类切割序列的情况，发现所加的权满足另外两类切割序列. 25 综述，将图综述，将图G分为图分为图1和和2，把指定边上的权增，把指定边上的权增加加e，分别求，分别求1和和2中从中从V1到到V27的最短路，最短路的的最短

19、路，最短路的权分别为权分别为:d1, d2. 则整体最少费用：则整体最少费用：d = min(d1,d2) ，最，最优切割序列即为其对应的最短路径优切割序列即为其对应的最短路径.例：例：r=15,e=2时，最短路为时，最短路为H2的路的路V1V4V5V14V17V26V27，权为，权为4435，对应最优切割序列为，对应最优切割序列为M3M1M6M4M5M2，最优费用为，最优费用为4435.图图9-14 H1 图图9-15 H2 26 欧拉回路和中国邮递员问题中国邮递员问题(Chinese Postman Problem, CPP)由我国管梅谷教授于1962年首先提出并发表的问题是从邮局出发，走

20、遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP 问题也就迎刃而解了若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点显然要在奇次点间加重复边如何使所加的边长度最少归结为求奇次点间的最小 匹配( minimum weighted match) 由Edmons 给出 多项式算法(1965)27一一. .中国邮递员问题中国邮递员问题- -定义定义28中国邮递员问题中国邮递员问题- -算法算法 Fleury算法算法-基本思想：从任一点出发，每当访问基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问

21、的边不只一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的一条，则应选一条不是未访问的边集的导出子图的割边割边(桥桥:G的某条边的某条边,不在不在G的任一圈或者去掉该边图的任一圈或者去掉该边图就不连通就不连通)作为访问边，直到没有边可选择为止作为访问边，直到没有边可选择为止.29V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e1030 若若G不是欧拉图，则不是欧拉图，则G的任何一个巡回的任何一个巡回经过某些边必定多于一次经过某些边必定多于一次 解决这类问题的一般方法是，在一些点对之间解决这类问题的一般方法是，在一些点对之间引入重复边（重复边

22、与它平行的边具有相同的权），引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小权的总和为最小31V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e932（）求出（）求出G1的的最小权理想匹配最小权理想匹配M，得到奇次顶点的最佳配对，得到奇次顶点的最佳配对33 解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边5、根据得到的偶图，给出欧拉回路

23、的若干种走法34 解中国邮递员问题的步骤35 二二. 哈密顿环球旅行问题哈密顿环球旅行问题( (货郎担问题货郎担问题, ,旅行售货商问旅行售货商问题题,Hmilton,Hmilton问题问题):): 十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个城市否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏） 含一切顶的轨叫含一切顶的轨叫Hamilton轨轨。 闭的闭的Hamilton轨轨为为Hamilton圈。圈。 36哈密尔顿回路

24、及旅行售货商问题哈密尔顿回路及旅行售货商问题 ( Hamiltonian circuit)连通图连通图G(V,E)中的回路称为中的回路称为哈密尔顿回路哈密尔顿回路，若，若该回路包括图中所有的点。显然哈密尔顿回该回路包括图中所有的点。显然哈密尔顿回路有且只有路有且只有 n 条边，若条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是么？这个问题是由爱尔兰数学家由爱尔兰数学家哈密尔顿哈密尔顿1859年年提出的，但至今仍未解决提出的，但至今仍未解决.欧拉回路是对边进行访问的问题，哈密尔顿回欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行

25、访问的问题路是对点进行访问的问题搜索哈密尔顿回路的难度是搜索哈密尔顿回路的难度是 NP-complete37任两点间都有边的图为任两点间都有边的图为完全图完全图, 完全图中有完全图中有(n-1)!/2条不同的哈密尔顿回路条不同的哈密尔顿回路, 有有(n-1)/2个边不个边不相交的哈密尔顿回路相交的哈密尔顿回路.哈密尔顿路径哈密尔顿路径：包含图中所有点的路径：包含图中所有点的路径.旅行售货商旅行售货商(TSP)：设：设v1, v2, .,vn 为为 n 个城市，城个城市，城市之间的路程已知，售货商从市之间的路程已知，售货商从 v1出发，走遍所有城出发，走遍所有城市一次且仅一次回到市一次且仅一次回

26、到v1，并使总旅程最短，并使总旅程最短.不允许点重复的售货商问题就是最小哈密尔顿回路问题不允许点重复的售货商问题就是最小哈密尔顿回路问题一般一般售货商售货商问题问题( (GTSPGTSP) )：允许点重复的：允许点重复的TSPTSP当网路边权满足三角不等式时，一般当网路边权满足三角不等式时，一般售货商问题售货商问题等价于等价于最小哈密尔顿回路问题最小哈密尔顿回路问题网路边权不满足三角不等式时，用两点间最短路的距离网路边权不满足三角不等式时，用两点间最短路的距离代替原来边权，就可满足三角不等式，在此基础上求最小代替原来边权，就可满足三角不等式，在此基础上求最小哈密尔顿回路哈密尔顿回路38 G是有

27、向图，把是有向图，把G各边方向去掉所得无向图叫各边方向去掉所得无向图叫G的底图；若的底图；若G的底图是连通图，则称的底图是连通图，则称G是是弱连通有弱连通有向图向图；在有向图；在有向图G中，中，u,v V(G), 且且G 中存在有向中存在有向轨轨P(u,v)，则称则称u可到达可到达v，每对顶都连边的有向图为每对顶都连边的有向图为竞赛图竞赛图。竞赛图必有竞赛图必有Hamilton轨。轨。一台机器完成一台机器完成n项工作，项工作，i工作工作j工作的机器调工作的机器调整时间为整时间为tij试安排试安排n项工作，使项工作，使 tijmin ;(有有向图上求向图上求Hamilton轨轨)39哈哈 密密

28、尔尔 顿顿 图图40售货商问题售货商问题- -定义定义旅行售货商需要访问某地区的所有城镇，旅行售货商需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使最后回到出发点问如何安排旅行路线使总行程最小这就是售货商问题总行程最小这就是售货商问题 若用顶点表示城镇，边表示连接两城若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费镇的路，边上的权表示距离（或时间、费用），于是售货商问题就成为在加权图中用），于是售货商问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭寻找一条经过每个顶点至少一次的最短闭通路问题通路问题41定义在加权图定义在加权图G=(V,E)中，中，（）权

29、最小的哈密尔顿圈称为最佳（）权最小的哈密尔顿圈称为最佳H圈圈（）经经过过每每个个顶顶点点至至少少一一次次的的权权最最小小的的闭闭通路称为最佳售货商回路通路称为最佳售货商回路 一般说来，最佳哈密尔顿圈不一定是最佳推一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳销员回路，同样最佳售货商售货商回路也不一定是最佳回路也不一定是最佳哈密尔顿圈哈密尔顿圈H回路，长回路，长22最佳售货商回路，最佳售货商回路，长长442旅行售货商问题近似算法：旅行售货商问题近似算法：二边逐次修正法：二边逐次修正法：43例例对对以以下下完完备备图图，用用二二边边逐逐次次修修正正法法求求较较优优H圈圈44 灾情巡视路线

30、灾情巡视路线(CUMCM 1998 B题题)45 今年夏天该县遭受水灾。为考察灾情、今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责组织自救，县领导决定，带领有关部门负责人到全县各乡人到全县各乡(镇镇)、村巡视。巡视路线从县、村巡视。巡视路线从县政府所在地出发，走遍各乡政府所在地出发，走遍各乡(镇镇)、村，又回、村，又回到县政府所在地。到县政府所在地。 1.若分若分3组组(路路)巡视，试设计总路线最短且巡视，试设计总路线最短且各组尽可能均衡的巡视路线。各组尽可能均衡的巡视路线。 2.假设巡视人员在各乡假设巡视人员在各乡(镇镇)停留时间停留时间T2小时，在各村停留时间小时

31、，在各村停留时间t=1小时，汽车行驶小时，汽车行驶速度速度V35公里公里/小时。要在小时。要在24小时内完成小时内完成巡视至少分几组？给出这种分组下你认为最巡视至少分几组？给出这种分组下你认为最佳的巡视路线。佳的巡视路线。46A B C D E F G HRPMQ29313230NJLL2018K21图例：图例：北北县政府所县政府所在地在地乡政府所乡政府所在地在地村村47 3. 在上述关于在上述关于T、t、和和V的假设下，如果的假设下，如果巡视人员足够多，完成巡视的最短时间是多少巡视人员足够多，完成巡视的最短时间是多少？给出这种最短时间完成巡视的要求下，你认？给出这种最短时间完成巡视的要求下，

32、你认为最佳的巡视路线。为最佳的巡视路线。 4. 若巡视组数已定若巡视组数已定(比如比如3组组)，要求尽快完，要求尽快完成巡视，讨论成巡视，讨论T、t、V改变对最佳路线的影响。改变对最佳路线的影响。最佳灾情巡视路线的数学模型最佳灾情巡视路线的数学模型杨庭栋杨庭栋 李晓涛李晓涛 郑长江郑长江解放军后勤工学院解放军后勤工学院一一. 问题重述问题重述(略略)二二. 模型假设与符号说明模型假设与符号说明(略略)48三三. 模型的建立与分析模型的建立与分析 本问题要求在县、乡、村公路网中，寻找本问题要求在县、乡、村公路网中，寻找从县出发走遍各乡、村，返回县的最短路程从县出发走遍各乡、村，返回县的最短路程或

33、最小时间。或最小时间。 把县、乡、村看作点把县、乡、村看作点，乡与村之间的，乡与村之间的公公路路看作边，看作边，距离看作距离看作对应边上的对应边上的权权。问题。问题就转化成在加权有向图从给定点就转化成在加权有向图从给定点O出发，历出发，历遍各点回到遍各点回到O，使使总权和最小总权和最小。为方便，先给出图论中一些相关定义。为方便，先给出图论中一些相关定义。 定义定义1：经过图：经过图G每个顶点各一次的圈，每个顶点各一次的圈，称为称为哈米尔顿圈哈米尔顿圈，简称，简称H圈。圈。定义定义2：在加权图：在加权图G=(V, E)中中(1). 权和最小的权和最小的H圈称为圈称为最佳最佳H圈圈。49 (2).

34、 经过每个顶点至少一次且权和最小经过每个顶点至少一次且权和最小的通路称为的通路称为最佳经销商回路最佳经销商回路。 最佳经销商回路可转化成最佳最佳经销商回路可转化成最佳H圈求圈求。 方法是：以图方法是：以图G的顶点集的顶点集构造完备图构造完备图G (V,E ), E 中每条边中每条边(x,y)的权为顶点的权为顶点x与与y在在图图G中最短路线。则：中最短路线。则： 定理定理1：图图G中最佳中最佳经销商经销商回路与回路与G 中中最佳最佳H圈相同。圈相同。 定理定理2：在加权有向图中求最佳：在加权有向图中求最佳H圈是圈是NP问题。问题。下面采用近似算法求此问题一个近似最优解。下面采用近似算法求此问题一

35、个近似最优解。本问题就是求图本问题就是求图G的最佳的最佳经销商经销商回路。回路。50算法算法1：(求图求图G的最佳的最佳经销商经销商回路回路) 1. 用用Dijkstra算法求出图算法求出图G中中任意两顶点任意两顶点之间的最短路。之间的最短路。构造完备图构造完备图G (V,E )。2.输入图输入图G 一个初始一个初始H圈。圈。3. 用对角线完全算法产生一个初始用对角线完全算法产生一个初始H圈。圈。 4. 随机输入随机输入G 一个一个H圈，圈，(例如例如2000个个)； 5.对第对第2、3、4步所得每个步所得每个H圈，用改良圈圈，用改良圈法求一个近似最佳法求一个近似最佳H圈。圈。 问题问题1：分

36、分3组巡视，设计总路线最短且各组组巡视，设计总路线最短且各组尽可能均衡的路线。尽可能均衡的路线。求图求图G顶点集顶点集V的一个划分的一个划分V1，V2， Vn。 6. 取第五步求出所有取第五步求出所有H圈中，权和最小者圈中，权和最小者为近似解。为近似解。51 将将G分成分成n个生成子图个生成子图GV1, GV2, , G Vn。使得：使得：(1). 顶点顶点O G(Vi)； i=1,2,n. (2). U Vi = V(G)n i =1(3).其中其中Ci为为G(Vi)导出导出子图中的最佳子图中的最佳H圈，圈， (Ci)为为Ci的权。的权。(4). (Ci)=minn i =1 定义定义3.称

37、称:a0= 为该分组实为该分组实际路线的均衡度。际路线的均衡度。a为最大允许度。为最大允许度。52 求求V的一个划分：求的一个划分：求O到其余各点的最短路，到其余各点的最短路，这些路构成一棵树，如图这些路构成一棵树，如图(1): 由经验知，分组由经验知，分组应遵从以下准则：应遵从以下准则： (1).同一干支同一干支上的点仅量分在上的点仅量分在一组。一组。 (2).应将相邻干应将相邻干支的点分在一组。支的点分在一组。 (3). 尽量将长尽量将长干支与短干支分在干支与短干支分在一组。一组。按以上准则找按以上准则找到两种分组形式：到两种分组形式：OCBRQA1 165PN4MK3LEFH2图图 1分

38、组分组1:(,) (,) (,)分组分组2:(,) (,) (,)不均不均衡舍衡舍去去!53 就分组就分组2中每组顶点的生成子图，用算法中每组顶点的生成子图，用算法1求尽量包含图求尽量包含图1中树上边的近似最佳解。中树上边的近似最佳解。该分组均衡度：该分组均衡度：a0=54.2%表表1 分组分组2的近似最优解的近似最优解小组小组名称名称路路 线线总路总路线长线长路线路线总长总长O-P-28_27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C-OO-R

39、-29-Q-30-32-31-33-35-34-A-B-1-O191.1241.9125.5558.5均衡均衡性很差性很差54 为改善均衡性，将第为改善均衡性，将第组中顶点组中顶点C、2、3、D、 4归入第归入第组。重新求得近似最优解，如表组。重新求得近似最优解，如表2。表表2 分组分组3的近似最优解的近似最优解小组小组名称名称路路 线线总路总路线长线长路线路线总长总长 O-P-2827-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OO-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-OO-R-2

40、9-Q-30-32-31-33-35-34-A-1-B-C-3-D-4-D-3-2-O191.1216.4192.3599.8该分组均衡度：该分组均衡度：a0=11.69%改善了改善了均衡度均衡度最优巡视路线见图最优巡视路线见图2。55用算法用算法1算出整个网络的近似算出整个网络的近似最佳推销员回路：最佳推销员回路：O-C-3-2-5-D-4-8-E-9-F-10-F-12-H-12-G-11-J-19-L-7-6-M-N-25-20-21-K-18-J-13-14-15-I-16-17-22-23-24-27-26-P-28-Q-30-Q-29-R-31-33-31-32-35-34-A-B

41、-O 总路线长为总路线长为588.6公里。公里。可以认为表可以认为表2所示结果近似最优。所示结果近似最优。 问题问题2：当巡视人员在乡、村停留时间一定，当巡视人员在乡、村停留时间一定，汽车速度一定，且在汽车速度一定，且在24小时内巡视完，至少分小时内巡视完，至少分OC BARPNIKMDLJGHFE图图2. 分为分为3组时各组的巡视路线组时各组的巡视路线Q56几组及最佳巡视路线。几组及最佳巡视路线。 T2小时小时，t=1小时，小时，V=35公里公里/小时，小时，乡镇共乡镇共17个，村共个，村共35个。假设分个。假设分4组计算：组计算：乡镇总停留时间为：乡镇总停留时间为：1723569小时小时

42、24小时巡视完至少分小时巡视完至少分4组组。69/417.25小时，小时，2417.256.75小时小时分分4组时路线总长不会比组时路线总长不会比599.8大太多。大太多。599.8/35/4=4.25(小时小时) 6.75(小时小时)分分4组的分组原则：组的分组原则：准则一、二、三同上准则一、二、三同上。准则四：尽量使各组停留时间相同准则四：尽量使各组停留时间相同。 按以上准则分按以上准则分4组，再用算法组，再用算法1求出近似求出近似最优解，得：最优解，得：57表表3 分组分组4的近似最优解的近似最优解(单位：公里单位：公里)小组小组名称名称路路 线线行走行走时间时间路线路线总长总长O-2-

43、5-6-7-E-8-E-11-G-12-H-12-F-10-F-9-E-7-6-5-2-OO-R-29-Q-30-Q-28-27-26-N-24-23-22-17-16-K-22-23-N-26-P-OO-M-25-20-21-K-18-I-15-14-13-J-19-L-6-M-O199.2 16 5.69 21.69 159.1 18 4.54 22.54O-R-A-33-31-32-35-34-B-1-C-D-4-D-3-2-O195.8 17 5.59 22.59166 18 4.74 22.74停留停留时间时间 总总 时间时间58该分组均衡度：该分组均衡度：a0=4.62%OC BA

44、RPNIKMDLJGHFE图图3. 分为分为4组时各组的巡视路线组时各组的巡视路线Q 注注:兰点前面已停留此次只过不停留，上加线点只过不停留。兰点前面已停留此次只过不停留，上加线点只过不停留。 问题问题3:在在T、t、V假定下，假定下，巡视人员足够巡视人员足够多完成巡视任多完成巡视任务的最短时间务的最短时间为多少？并给为多少？并给出最佳路线。出最佳路线。 经计算知经计算知O到到H的最短时间是所有最短时间的最短时间是所有最短时间中最长者，其距离为中最长者，其距离为77.5公里。所需时间为：公里。所需时间为：tH=277.5/3526.43小时小时在最短时间限下完成巡视的最优路线应满足：在最短时间

45、限下完成巡视的最优路线应满足：59(1)每个巡视组总时间不超过每个巡视组总时间不超过6.43小时；小时；(2)所有点必须访问到，不得遗漏。所有点必须访问到，不得遗漏。(3)巡视组要尽量少。巡视组要尽量少。寻找最优路线从距寻找最优路线从距O较远点开始。步骤如下：较远点开始。步骤如下：第一步：由图第一步：由图1算出算出O到每个点的最短距离。到每个点的最短距离。 第二步：找出最远一点，计算第二步：找出最远一点，计算O沿最短路沿最短路线巡视最短时间线巡视最短时间ti，并求并求 t= tH ti第三步：若第三步：若t1，则在余下的点中选一距则在余下的点中选一距O最远者，最远者，根据条件看这一组能否巡视这

46、一点。根据条件看这一组能否巡视这一点。第四步：若能巡视则计算第四步：若能巡视则计算 t，转第三步。转第三步。第五步：若不能，依次找次远点，第第五步：若不能，依次找次远点，第3远点远点60满足总巡视时间不超过满足总巡视时间不超过tH ，就让这组巡视这，就让这组巡视这一点，直到一点，直到t0时：时： 要保证原均衡分组不变，则：要保证原均衡分组不变，则：max T SiSjVXiXj 0 (YiYj)tXiXjmax SiSjVXiXj 0 (YiYj)tXiXj(3)632.当当YiYj0时：时： 要保证原均衡分组不变，则：要保证原均衡分组不变，则：max T SiSjVXiXj 0 (XiXj)

47、tYiYjmax SiSjVXiXj 0 (XiXj)tYiYj3.当当SiSj0时：由时：由(2)得得. 0 (XjXi)T+(YjYi)t 时：时： (XiXj)T+(YiYj)t SiSjV max (5)SiSj 0. (XjXi)T+(YjYi)t 时：时：(4)64 (XiXj)T(YiYj)t SiSj max V SiSj 0(XjXi)T+(YjYi)t SiSj max (6)SiSj 0(二二). 分三组的实例讨论分三组的实例讨论问题问题1所得的所得的3组，当组，当TT02小时小时，t=t0=1小时，小时，VV035公里公里/小时；结果如表小时；结果如表5：编号编号 Xi

48、 Yi Si 行驶时间行驶时间 总时间总时间 5 13 191.1 5.46 28.46 6 11 192.3 5.49 28.49 6 11 216.4 6.18 29.18表表5(路程单位公里，时间单位小时路程单位公里，时间单位小时)65均衡度均衡度a0=2.5%；时间误差时间误差 00.72小时；小时； 现分别就分组最大允许均衡度：现分别就分组最大允许均衡度：a=2.5%和和a=5%，最大允许时间误差：最大允许时间误差： 0.72小时和小时和 1.44小时，计算小时，计算T、t、V固定任意两个，在不破固定任意两个，在不破坏均衡分组时，另一个的变化范围。坏均衡分组时，另一个的变化范围。a=

49、2.5%， 0.72 1.25 T 2 1 t 1.38 V 35a=5%， 1.44 0.51 T 2.74 0.63 t 1.75 V 17.3 t, V 不不 变变 T, V 不不 变变 T,t 不不 变变表表6 (路程单位公里，时间单位小时路程单位公里，时间单位小时)(三三).对实例结果的分析对实例结果的分析 上例均衡分组，当各组停留时间相等，即上例均衡分组，当各组停留时间相等，即TT02小时小时，t=t0=1小时，小时，VV035公里公里/小时小时66时，在表时，在表5分组中分组中(XiXj)T0+(YiYj)t0=0 i, j=1, 2, 3(7) 定义定义4 各组停留时间相等的均

50、衡分组称为停各组停留时间相等的均衡分组称为停留时间相等的均衡分组。留时间相等的均衡分组。 下面对停留时间相等的均衡分组讨论下面对停留时间相等的均衡分组讨论T、t、V的变化规律。的变化规律。 0= max | +(XiXj)T0+(YiYj)t0 |SiSjV0i, j=max | | =SiSj V0i, jSi Sj V0Si =max(Si) Sj =min(Si)ii其中：其中：T，t不变时，即不变时，即TT0，t=t0，VV0时时(9)67因：因：(XiXj)T0+(YiYj)t0=0 0 SiSj max SiSj 0Si Sj 取取: 0 则由则由(9)得：得： Vmin V0 0

51、 时：时：则由则由(9)得：得： Vmin 0 ，当，当T、t不不变时，要使均衡分组不变，变时，要使均衡分组不变，V变化下界小于变化下界小于 V0 。68四四.模型推广模型推广(略略).五五.模型优缺点：模型优缺点：优点：优点： 1.本文分组准则简便易行，可操作性强。本文分组准则简便易行，可操作性强。且可逐步调整使分组达到均衡、且可逐步调整使分组达到均衡、2.用均衡度的定量刻划了均衡性。用均衡度的定量刻划了均衡性。 3.在用近似算法计算近似最佳推销员回在用近似算法计算近似最佳推销员回路时，采用路时，采用3种方法产生初始圈，使算法比种方法产生初始圈，使算法比较完善，得到了误差很小的近似最优解。较完善，得到了误差很小的近似最优解。 4. 从理论上定量讨论了从理论上定量讨论了V、T、t的变化对的变化对分组均衡度的影响，得到了很好的结果。分组均衡度的影响，得到了很好的结果。缺点缺点(略略)69参考文献参考文献1. 舒贤林，徐志才编著，图论基础及应用舒贤林，徐志才编著，图论基础及应用.2.龚龚 编，编， 图论与网络最优算法。图论与网络最优算法。3. 费培之编著，图和网络及最优算法。费培之编著，图和网络及最优算法。70