可行遍性及赛题讲解ppt课件

可行遍性问题,Euler图 中国邮递员问题 Hamilton图 推销员问题 建模案例：最佳灾情巡视路线, ,文理学院数学系：徐艳 ,1 Euler图,1、图的定义 定义 一个二元有序数组（V，E）称为一个图，记作G =（V，E）。V称为顶点，E为边。 若每个边对应一个数F，称（V，E，F）为赋权图。 如果两点是有序的，则称有向图，否则，无向图。 常用术语： （1）端点相同的边称为环。 （2）若一对顶点之间有两条以上的边联结，则这些边称为重边。,1 Euler图,（3）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边。 （4）边和它的端点称为互相关联的。 （5）既没有环也没有重边的图称为简单图。 （6）任意两顶点都相邻的简单图，称为完备图。,1 Euler图,2、顶点的次数 定义 （1）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)。 （2）在有向图中，从顶点v引出的边的数目称为v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v)。 d(v)= d+(v)+ d-(v)称为v的次数。 容易验证公式： 由公式可以证明 任何图中奇次顶点的总数必为偶数；生活中握过奇次手的人数是偶数。,1 Euler图,例子 哥尼斯堡（Konigsberg） 七桥问题 Euler在1736年访问Konigsberg时，他发现Konigsberg城中有一条名叫Pregel的河流，河上建有七座桥如图所示: 市民有趣的消遣活动是星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点，是否可能？,1 Euler图,1 Euler图,定理 对于非空连通图G，下列命题等价： （1）G是Euler图； （2）G无奇次数顶点； （3）G的边集能划分为圈。,定理 图G是Euler图的充分必要条件是：图G连通且所有顶点的次数均为偶次。 可见，七桥问题中，每个顶点都是奇次的，由上述定理知，七桥问题不是Euler图，所以不存在Euler迹，此图不可以“一笔画”。,1 Euler图,确定Euler图中Euler环游的方法 Fleury算法解决了这一问题。 Fleury算法的基本思想：从任一点出发，每当访问一条边时，先要进行检查。如果可供访问的边不止一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选为止。 注：割边的定义：设G连通， ，若从G中删除边e后，图Ge不连通，则称边e为图G的割边。,1 Euler图,1 Euler图,2 中国邮递员问题,邮递员从邮局出发，经过他所投递范围的每一条街道至少一次，完成邮件的投递任务后返回邮局。如何安排他的路线，使得总路程最短。 这个问题最早由山东大学的管梅谷1962年提出，并给出了一个解法，被国际上称为中国邮递员问题。,2 中国邮递员问题,一、Euler图中的最优环游 显然这时任意一个Euler环游都是最优环游。可以用Fleury算法找出。 二、非Euler图中的最优环游 邮递员要完成任务，某些边经过的次数超过一次，即图G不是Euler图。 解决这类问题的一般方法是，把邮递员重复走过的边在原图上画出，权与原边一样(这种边称为重复边)，使原图变成Euler图，但希望的所有添加的重复边的权的总和为最小。,2 中国邮递员问题,怎样添加一些重复边，使得原图变为Euler图，并且重复边的权和达到最小？,2 中国邮递员问题,情形1 G正好有两个奇次顶点。 设G正好有两个奇次顶点u和v，求G的最佳环游的算法如下： （1）用Dijkstra(迪克斯特拉）算法求出顶点u和v之间的最短路径P。 （2）令G*=GP，则G*为Euler图。 （3）用Fleury算法求出G*的Euler环游，这就是G的最佳环游。,2 中国邮递员问题,情形2 图G有2n个奇次顶点（n2) Edmonds于1965年提出的最小对集算法，很好的解决了这一类问题。 Edmonds算法的基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小，再沿点对之间的最短路径添加重复边得Euler图G*， G*的Euler环游便是原图的最佳环游。,2 中国邮递员问题,Edmonds最小对集算法： （1）用Floyd算法求出所有奇次顶点之间的最短路径和距离。 （2）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1。 （3）用Edmonds算法求出G1的最小权理想匹配M,得到奇次顶点的最佳配对。 （4）在G中沿配对顶点之间的最短路径添加重复边得Euler图G*. (5)用Fleury算法求出G*的Euler环游，这就是G的最佳环 游。,2 中国邮递员问题,例 求图1所示投递区的一条最佳邮递路线。,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,2,3,5,6,9,8,10,1,1,1,2,3,4,图1,2 中国邮递员问题,解 图中有v4,v7,v8,v9四个奇次顶点，用Floyd算法求出它们之间的最短路径和距离如下： Pv4v7=v4v3v2v7, d(v4，v7)=5 Pv4v8=v4v8, d(v4 ，v8)=3 Pv4v9=v4v8v9, d(v4 ，v9)=6 Pv7v8=v7v8, d(v7 ，v8)=9 Pv7v9=v7v9, d(v7 ，v9)=6 Pv8v9=v8v9, d(v8 ，v9)=3,2 中国邮递员问题,以v4,v7,v8,v9为顶点，它们之间的距离为边权构造完备图G1，如图2。,v4,v7,v8,v9,3,3,6,6,9,5,图2,2 中国邮递员问题,求出G1的最小权完美匹配M=(v4,v7),(v8,v9). 在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径添加重复边，得Euler图G2,如图3. 在G2中一条Euler环游就是G的一条最佳环游。,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,2,3,5,6,9,8,10,1,1,1,2,3,4,图3,3 Hamilton图,定义 设G=(V,E)是连通无向图 （1）经过G的每个顶点正好一次的路径，称为G的一条哈密顿路径，简称H路径。 （2）经过G的每个顶点正好一次的圈，称为G的哈密顿圈或H圈。 （3）含H圈的图称为哈密顿图或H图。 显然，Hamilton圈(路)是通过所有顶点的最短回路(路径)。,3 Hamilton图,直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 1859年，数学家Hamilton发明了一种“周游世界”的数学玩具，在一个12面体的20个顶点上分别刻上北京、东京、华盛顿等20个大城市的名字，要求玩家从某城出发，沿12面体的棱通过每个城市恰一次，再回到出发的那个城市。 实际上，是在以12面体的顶点为顶点，以其棱为边的图上寻求一条Hamilton圈，其答案是很多的。,3 Hamilton图,1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,北京,东京,1,2,3,4,5,6,7,8,9,10,11,12,13,13,14,15,16,17,18,19,20,3 Hamilton图,注：要判断一个图是否含有H圈是NP完全问题，要求出一个图的H圈也没有多项式时间算法。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 下面仅给出几个简单的必要或充分条件。,3 Hamilton图,定理 设无向图G = (V,E)是哈密顿图的必要条件是：对于V的任意非空子集S，均有： (G S) |S| 其中(GS)是从G中删除S中的顶点之后所得到的连通子图的个数。 定理 设G=(V,E)是具有n 3个顶点的简单无向图。如果对任意两个顶点u, vV，均有d(u)+d(v)n-1 则G中存在Hamilton路；若有 d(u)+d(v)n，则G中存在Hamilton圈。,4 推销员问题,一个推销员需要访问某地区的所有城镇，然后回到出发地。问应怎样计划他的旅行路线，使总行程最小？这个问题在图论中称为推销员问题。 推销员问题也是NP-完备问题，目前没有求解推销员的有效算法。 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。,4 推销员问题,定义 （1）经过图G的每个顶点正好一次的圈（如果存在），称为G的哈密尔顿圈或H圈。其中权最小的哈密尔顿圈称为最佳H圈。 （2）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈。但是最佳推销员回路问题可转化为最佳H圈问题。,4 推销员问题,方法是:由给定的图G=(V,E)构造一个以V为顶点集的完备图G=(V,E)，E的每条边(x,y)的权等于顶点x与y在图中最短路的权。 这时，我们有结论：加权图G的最佳推销员回路的权与G的最佳H圈的权相同 因此，在加权图中寻找最佳推销回路的问题就转化为一个完备图中寻找最佳哈密顿圈的问题，称为TSP问题。,4 推销员问题,TSP问题也称旅行商问题(traveling salesman Problerm) ：一个旅行商从一个城市出发，经过其它城市一次且仅一次，最后回到出发城市，求一个路径，使总的行程最短。 很多实际应用的问题，如印刷电路版、物流路线等经过简化处理后，均可转化为TSP问题。,4 推销员问题,求解TSP问题的近似算法： （1）最小生成树算法（缺点：在节点数较大时，实现十分困难，复杂度骤升）。 （2）分枝定界法，动态规划法。 （3）稳态遗传算法 （4）蚁群算法 （5）基于神经网络的近似算法：模拟退火法，弹性网法。,4 推销员问题,TSP近似算法 思想：找到一个初始Hamilton圈C，然后适当修正C，以得到具有较小权的另一个Hamilton圈。 TSP近似算法包括构造型算法和改进型算法。构造型算法是按一定规则一次性地构造出一个解。而改进型算法则是以某一解作为初始解，逐步迭代，改进解，是一种迭代法。一般是以构造型算法得到一个初始解，然后再用改进型算法逐步改进。 常见的两种构造型算法是最小权匹配算法和对角线完全算法。 下面介绍一个改进型算法：二边逐次修正法,4 推销员问题,二边逐次修正法：,4 推销员问题,例：利用上述算法找出右图旅行售货员的一个近似最优解。,4 推销员问题,L MC NY P B T L,L P NY MC B T L,5 建模案例：最佳灾情巡视路线,下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。,乡村分布图,5 建模案例：最佳灾情巡视路线,1、若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2、假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 3、上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4、若巡视组数已定(如三组)，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。,5 建模案例：最佳灾情巡视路线,一、问题分析 将公路网图中，每个乡（镇）或村看做图中的一个节点，各乡（镇）、村之间的公路看做图中对应节点间的边，各条公路的长度（或行驶时间）看做对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即为最佳推销员回路问题。,5 建模案例：最佳灾情巡视路线,二、模型假设 1、公路不考虑等级差别，也不受灾情或交通情况的影响； 2、各条公路段上汽车行驶的速度可以认为是均匀的； 3、巡视人员在各乡（镇）、村停留的时间一定，不会出现特殊情况而延误时间； 4、各巡视组巡视的乡（镇）、村不受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内 5、忽略不计巡视人员上、下车所用的时间； 6、当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,四、模型的建立与求解 将公路网图中，每个乡（镇）或村看做图中的一个节点，各乡（镇）、村之间的公路看做图中对应节点间的边，各条公路的长度（或行驶时间）看做对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即为最佳推销员回路问题。 在加权图G中求最佳推销员回路问题是NP-完全问题，我们采用一种近似算法求出该问题的一个近似最优解。,5 建模案例：最佳灾情巡视路线,算法一 求加权图G(V,E)的最佳推销员回路的近似算法： （1）用Floyd算法求出G中任意两个顶点间的最短路，构造出完备图G(V,E)。 （2）输入图G的一个初始H圈。 （3）用对角线完全算法产生一个初始H圈。 （4）随机搜索出G中若干个H圈。 （5）在求出的所有H圈中，用二边逐次修正法进行优化，得到近似最佳H圈。 （6）在求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。 注：由于二边逐次修正法的结果与初始圈有关，故分别用三种方法产生初始圈，以保证能得到较优的计算结果。,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路。故用Dijkstra算法求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，从下图中可以看出，从O点出发到其它点共有6条干枝，它们分别记为，。 根据实际工作的经验及上述分析，在分组时应遵循以下准则：,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,准则1：尽量使同一干枝上及其分枝上的点分在同一组； 准则2：应将相邻的干枝上的点分在同一组； 准则3：尽量将长的干枝与短的干枝分在同一组。 由此，我们找到两种分组形式： 分组一：（ ， ），（ ，），（ ，） 分组二：（ ，），（ ，），（ ，） 显然分组二更为均衡，故考虑分组二。,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,为改善均衡性，将第组中的顶点C,2,3,D,4分给第组，重新分组的近似最优解如下表：,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视路线,5 建模案例：最佳灾情巡视