《行遍性问题.ppt》由会员分享，可在线阅读，更多相关《行遍性问题.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、行遍性问题安徽工业大学数理学院行遍性问题一、中国邮递员问题一、中国邮递员问题二、推销员问题二、推销员问题1 1、欧拉图、欧拉图2 2、中国邮递员问题、中国邮递员问题1 1、哈密尔顿图、哈密尔顿图2 2、旅行商问题旅行商问题欧拉图18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题这就是哥尼斯堡七桥问题，一个著名的图论问题。1727年20岁瑞士数学家欧拉，被俄国请去在
2、圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多人困惑的问题。1736年欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”欧拉巧妙地把哥尼斯堡城图化为下图所示图G，他把陆地设为图G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图G中从某一结点出发找出一条路，它通过每条边恰好一次后回到原出发结点，亦即等价于在图G中寻找一个圈，它通过G中每一条边恰好一次。e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5
3、v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定义1:设G=(V,E)是连通无向图1、经过G的每边至少一次的闭通路称为巡回2、经过G的每边正好一次的巡回称为欧拉巡回(圈)3、存在欧拉巡回的图称为欧拉图4、经过G的每边正好一次的道路称为欧拉道路e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图定理1:对于非空连通图G，下列命题等价：1、G是欧拉图2、G无奇次顶点3、G的边集能划分为圈推论1:设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投递范
4、围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回 定义:设图G=(V，E)，ME，若M的边互不相邻，则称M是G 的一个匹配.若顶点v与M的一条边关联，则称v是M饱和的 设M是G的一个匹配，若G的每个顶点都是M饱和的，则称M是G的理想匹配.G的边e是割边的充要条件是e不含在G的圈中设G连通，eE(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边割
5、边的定义：割边v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9中国邮递员问题-算法 1、G是欧拉图 此时G的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回Fleury算法：求欧拉图的欧拉巡回Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不止一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10b)除非不能选择，否则一定要使ei+1不是Gi=GE-e1,e2,ei 的割边Fleury算法算法步骤：1、任选一个顶点v0，令
6、道路w0=v02、假定道路wi=v0e1v1e2eivi已经选好，则从Ee1,e2,ei中选一条边ei+1，使：a)ei+1与vi相关联3、第2步不能进行时就停止 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小2、G不是欧拉图情形G正好有两个奇次顶点1、用Dijkstra算法求出奇次顶点u与v之间的最短路径P2、令G*=GP，则G*为欧拉图3、用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回v7e3v1v2v3v4e1e2e4 1e5
7、v5v6e6e7e8e942314243情形2G有2n个奇次顶点（n2）Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回算法步骤：1、用Floyd算法求出的所有奇次顶点之间的最短路径和距离2、以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G13、求出G1的最小权理想匹配M，得到奇次顶点的最佳配对4、在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*5、用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回例
8、例求右图所示投递区的一条最佳邮递路线1、图中有v4、v7、v8、v9四个奇次顶点用步骤3求出G1的最小权理想匹配M，得到奇次顶点的最佳配对v1v2v3v4v5v6v7v8v9114211108639325v4v7v8v93936652、以v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图G1 3、求出G1的最小权完美匹配M=(v4,v7),(v8,v9)4、在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径v8v9添加重复边，得欧拉图G2G2中一条欧拉巡回就是G的一条最佳巡回其权值为64与欧拉圈非常类似的问题是哈密尔顿圈的问题。1859年，爱尔兰数学家哈密尔顿(W.R.H
9、amilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市，这个正十二面体同构于一个平面图，要求旅游者能否找到沿着正十二面体的棱，从某个顶点(城市)出发，经过每个顶点(城市)恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。哈密尔顿图哈密尔顿图定义:设G=(V,E)是连通无向图1、经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径2、经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈3、含H圈的图称为哈密尔顿图或H图按图中所给的编号进行旅游，便是哈密尔顿问题的解。对于任何连通图也有类似的问题。哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却
10、有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一最小Hamilton回路与旅行商问题设G=(V,E,w)，其中V是顶点集，E是边集，w为定义在E上的权（非负）。G的一个Hamilton回路是顶点集V上的一个循环排列p=v1v2vnvn+1(v1=vn+1)，其中vivi+1E，w(p)定义为p上所有边权之和，当w(p)达到最小时，p称为最小Hamilton回路。G的一个旅行商路线是顶点集V的可重复的但不遗漏的一个循环排列，多旅行商路线则是顶点集可重复的但总体上不遗漏的多个循环排列。Hamilton回路（圈）旅行商线路若G是连通的但不是完全图时，G可能不
11、存在Hamilton回路，更不存在最小Hamilton回路，但若G是连通的，就一定存在最优旅行商路线。v1v2v4v3v5151214右图不存在Hamilton回路，但最优旅行商线路为v1v2 v4 v5 v4 v3 v1若G完全图时，则G一定存在Hamilton回路，且亦存在最小Hamilton回路，但该最小Hamilton回路未必就是最优旅行商路线。v1v2v3v4v52914558467试考察右图v1v2v3v4v52914558467右图的最小Hamilton回路为：v1 v2 v3 v4 v5v1右图的最优旅行商路线为：v1 v2 v3 v4 v1 v5v1最小Hamilton回路长
12、19，最优旅行商路线长17。问题：在什么条件下，最小Hamilton回路就是最优旅行商线路？定理若完全图G=(V,E,w)的权满足三角不等式则G的最小Hamilton回路就是最优旅行商路线最优旅行商路线无法直接求，要设法将其化为求最小Hamilton回路，由上面的结论，设法将图化为完全图且边权满足三角不等式。方法如下（若G是非完全图）1）将G=(V,E,w)化为完全图G=(V,E,w)，其中wij用vi到vj的最短路代替，这样G的边权就满足了三角不等式。2）求G的最小Hamilton回路。3）将求出的最小Hamilton回路中的边vivj用相应的vi到vj的最短路代回，即求出了最优旅行商路线。
13、问题转化为如何求Hamilton圈问题。求Hamilton圈为一难解问题，现已从理论上证明了其无有效算法。所以仅能求近似解。一种近似算法（改良圈法）1）在完全图上任取一Hamilton圈，不妨设为C=v1v2vnv12）检查是否存在ij，使vi-1vjE(G),vivj+1E(G)且成立wi,j+1+wi-1,jwi-1,i+wj,j+1,若成立则有改良圈C1=v1v2vi-1vjvj-1 vivj+1vj+2 vnv1。3）令C=C1，转2），直到停止。vi-1vivj+1vj+2vnv1vj-1vj该算法得到的Hamilton圈未必是理想圈，但其算法复杂度低。示例从北京(Pe)到伦敦(L)
14、、墨西哥城(MC)、纽约(NY)、巴黎(Pa)、东京(T)各城去环球讲学，乘飞机到各城一次再返回首都北京，应如何安排行程最省旅费？（各城间距离作为边权在图中标出）PeTLMCNYPa13605651 35702216178 68 51 68 51 36 PeTLMCNYPaPe01351786851T13060706861L5160056352MC78705602151NY68683521036Pa5161251360问题求解给出初始圈 C=(Pe)(T)(L)(MC)(NY)(Pa)(Pe)PaNYPeMCTLPaNYPeMCTLPaNYPeMCTLPeLPaNYMCT得到改良圈C=(Pe)(T)(MC)(NY)(L)(Pa)(Pe)其总长度为13+70+21+35+2+51=192该结论未必达到最小Hamilton圈，即最小Hamilton圈长度一定小于等于192。其是对最小Hamilton圈的一种近似。如何估计近似解的近似程度呢？方法如下TLMCNYPaPe1351235211）先求出图G的一棵最小生成树，算出其最小生成树的长度，该问题为122。2）从近似解的Hamilton圈中去掉一条最大的边，其也为一棵生成树，算出其长度。该问题为132。3）求出他们的长度之差，就是近似解与最优解最大的误差范围。该问题的误差最大限度为10。