中国邮递员问题matlab实现

数学建模常用方法建模常用算法,仅供参考：1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具）3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用L i n d o、L i n g o软件实现）4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备）5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用）7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具）8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理）一、在数学建模中常用的方法：1.类比法2.二分法3.量纲分析法4.差分法5.变分法6.图论法7.层次分析法8.数据拟合法9.回归分析法10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划）11.机理分析12.排队方法13.对策方法14.决策方法15.模糊评判方法、16.时间序列方法17.灰色理论方法18.现代优化算法（禁忌搜索算法、模拟退火算法、遗传算法、神经网络)二、用这些方法可以解下列一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。

定理1 定理1 在加权图 G=(V,E)中,若对任意 x,y,z ∈ V,z ≠ x, z ≠ y, 都有 w(x,y) ≤ w(x,z)+w(z,y),则图 G 的最佳 H 圈也是最佳推销员 回路.
最佳推销员回路问题可转化为最佳 H 圈问题.方法是由给 定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G'=(V,E'), E' 的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权.即: x,y ∈ E', w(x,y)=mindG(x,y)
情形1 情形1
G 正好有两个奇次顶点
(1)用 Dijkstra 算法求出奇次顶点 u 与 v 之间的最短路径 P.
(2)令 G*=G ∪ P,则 G*为欧拉图.
(3)用 Fleury 算法求出 G*的欧拉巡回,这就是 G 的最佳巡回.
v1 e4 v4
e1 e5 e3
v2 e2 e6 v3 v7 e7
返回
推销员问题推销员问题-定义
流动推销员需要访问某地区的所有城镇,最后 回到出发点.问如何安排旅行路线使总行程最 小.这就是推销员问题 推销员问题. 推销员问题
若用顶点表示城镇,边表示连接两城镇的路, 边上的权表示距离(或时间,或费用),于是推 销员问题就成为在加权图中寻找一条经过每个顶 点至少一次的最短闭通路问题.
(5)用 Fleury 算法求出 G*的欧拉巡回,这就是 G 的最佳巡回.
例 求右图所示投递区的一条最佳邮递路线. 1.图中有 v 4, v 7, v 8, v 9 四个奇次顶点
用 Floyd 算法求出它们之间的最短路径和距离:
Pv 4 v 7 = v 4 v 3 v 2 v 7 , d ( v 4 , v 7 ) = 5 Pv 4 v 8 = v 4 v 8 , d ( v 4 , v 8 ) = 3 Pv 4 v 9 = v 4 v 8 v 9 , d ( v 4 , v 9 ) = 6 Pv 7 v 8 = v 7 v 8 , d ( v 7 , v 8 ) = 9 Pv 7 v 9 = v 7 v 9 , d ( v 7 , v 9 ) = 6 Pv 8 v 9 = v 8 v 9 , d ( v 8 , v 9 ) = 3

数学建模常用方法建模常用算法,仅供参考：1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具）3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用L i n d o、L i n g o软件实现）4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备）5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用）7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具）8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理）一、在数学建模中常用的方法：1.类比法2.二分法3.量纲分析法4.差分法5.变分法6.图论法7.层次分析法8.数据拟合法9.回归分析法10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划）11.机理分析12.排队方法13.对策方法14.决策方法15.模糊评判方法、16.时间序列方法17.灰色理论方法18.现代优化算法（禁忌搜索算法、模拟退火算法、遗传算法、神经网络)二、用这些方法可以解下列一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。

浙江师范大学2010数学建模集训之邮件送递邮件送递【摘要】本题可以转化为最佳旅行货物员问题。

在给定的加权网络图中寻找从起始点51出发，行遍所有有邮件到达的点至少一次再回到起始点，使得总权最小。

本文运用MATLAB软件求出所需的最小生成树，在某些特定的分岔路口运用Dijkstra最短路算法找到区域性的最优解，再运用Floyd算法结合原图及目标规划找出邮递员的最短路径。

针对问题一：将1~30号邮件送至21个地点，由于重量和体积都没有超出，采用单一目标规划，得到一个最优送货路线；针对问题二：在问题一的基础上加上每号邮件的时间限制，采用多目标规划，对问题一所得路线进行调整，求得近似最优路线；针对问题三：只考虑重量和体积的限制，将100号邮件（总重量148公斤，总体积2.8立方米）送至50个地点，可根据原图的最小生成树的树枝的大体分布情况分成三个类似哈密尔顿回路，求得近似最优解；针对问题四：在前三问的基础上，将各地需要寄出的邮件（总重量75.52公斤，总体积6.12立方米）带回邮局，故我们分七个类似哈密尔顿回路，派遣两名邮递员完成任务。

纵观全文，本文解决了在时间，重量，体积等不同条件限制下的最优路线问题，具有较强的实践意义。

【关键字】邮件送递，最小生成树，目标规划，类似哈密尔顿回路，最短路线一、问题重述现在社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个售货员需要以最快的速度将货物送达，才能在这个市场上处于不败的地位。

怎样设置邮递员的路线才能使其尽量少走不必要的路线并且在规定的时间内完成邮递任务呢？根据本题要求，邮递员的最大载量是50公斤，所带货物的最大体积为1立方米，邮递员路上平均速度为30公里/小时，每件货物交接花费2.5分钟，解决如下问题：1．将1~30号邮件（总重量和总体积均没有超出）送至21个地点，设计最短的送货路线，求出最少花费的时间；2．在问题1的基础上，该邮递员从早上8点出发，要求1~30号邮件的送达时间不能超过指定时间（邮件送达地点及不超过的送达时间的信息如下表），设计最快完成路线与方式，标出路线；3．若不需要考虑所有邮件送达时间限制(包括前30件货物)，现在要将100件邮件（总重量148公斤，总体积2.8立方米）送到1~50号地点并返回。

§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。

1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。

2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。

伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。

对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。

我们将这些重复的边组成的集合称可行集，即找最小的可行集。

命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。

完整的算法流程如下：
1如果G的基图连通且所有顶点的入、出度均不为0，转2，否则返回无解并结束；
2计算所有顶点v的d’(v)值；
3构造网络N；
4在网络N中求最小费用最大流；
5对N中每一条流量f(u,v)的边(u,v)，在图G中增加f(u,v)次得到G’；
6在G’中求欧拉回路，即为所求的最优路线。
NPC问题：
if(in[i] +1 == out[i]) ...{
spos = i;
break;
}
}
}
else ...{
for(i=0;i<30;i++) ...{
if(f[i] != -1) ...{
spos = i;
break;
}
}
}
for(i=0;i<30;i++) sort(words[i].begin(), words[i].end());
如果部分街道能够双向通行，部分街道只能单向通行。这个问题已被证明是NPC的。[5]
--------------------------------------------------------------------------------
[1]大城市邮政投递问题及其算法研讨
[2]忽略有向图所有边的方向，得到的无向图称为该有向图的基图。
step = 0;
memset(vis, 0, sizeof(vis));
find_euler(spos);
//memset(vis, 0, sizeof(vis));
for(i=step-1;i>0;i--) ...{
spos = seq[i];
string snext;

MATLAB编程（运筹学之运输问题）运筹学与最优化MATLAB编程使⽤MATLAB求解：1、某公司经销甲产品。

它下设三个加⼯⼚。

每⽇的产量分别是：A1位7吨，A2为4吨，A3为9吨。

该公司把这些产品分别运往4个销售点。

各销售点的每⽇销量分别为：B1为3吨，B2为6吨，B3为5吨，B4为6吨，已知运价如下表所⽰，问该公司如何调⽤产品，在满⾜各销地需求量的前提下，使总运费最少。

运价表加⼯⼚销地B1B2B3B4A1311310A21928A374105解：设x ij为第i加⼯⼚运往第j销地的产品则min Z=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34根据合同要求，需满⾜x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6M⽂件如下：c=[3,11,3,10,1,9,2,8,7,4,10,5]；Aeq=[1,1,1,1,0,0,0,0,0,0,0,0;0,0,0,0,1,1,1,1,0,0,0,0;0,0,0,0,0,0,0,0,1,1,1,1;1,0,0,0,1,0,0,0,1,0,0,0;0,1,0,0,0,1,0,0,0,1,0,0;0,0,1,0,0,0,1,0,0,0,1,0;0,0,0,1,0,0,0,1,0,0,0,1]；beq=[7;4;9;3;6;5;6]；lb=[0;0;0;0;0;0;0;0;0;0;0;0]；ub=[Inf;Inf;Inf;Inf;Inf;Inf;Inf;Inf;Inf;Inf;Inf;Inf]；[x,fval]=linprog(c,[],[],Aeq,beq,lb,ub)2、某⼚按合同规定须于当年每个季度末分别提供10,15,25,20台同⼀格的柴油机。

一笔画问题：从某一点开始画画，笔不离纸， 各条线路仅画一次，最后回到原来的出发点。
h
5
v1 a
b
c
v2
v3
v4
图1
图2
图1和图2当中哪一个图满足：从图中任何一点出 发，途径每条边，最终还能回到出发点？
试想：一个图应该满足什么条件才能达到上面要
求呢？
h
6
一笔画问题
凡是能一笔画出的图，奇点的个数最多 有两个。始点与终点重合的一笔画问题， 奇点的个数必是0。
求解。
推广的中国邮递员问题： 混合图的中国邮递员问题，有各种限制
的中国邮递员问题，动态网络的中国邮 递员问题。 其他相关问题-旅行售货员（TSP）问题， 灾清巡视路线。
谢谢!
上述两算法都是在连通欧拉图中求欧拉 回路的算法.
h
11
中国邮递员问题
一个邮递员送信，要走完他负责投递的 全部街道，投完后回到邮局，应该怎样 走，使所走的路程最短？
这个问题是我国管梅谷同志1960年首先 求出来的，因此在国际上通称为中国邮 递员问题。在物流活动中，经常会遇到 这样的问题，如：每天在大街小巷行驶 的垃圾车、洒水车、各售货点的送货车 等都需要解决一个行走的最短路程问题。
h
15
求解中国邮递员问题的算法
管梅谷教授首先提出的方法是奇偶点图上作业 法（1962年）
Edmonds，Johnson（1973年）给出有效算法。
复杂度为 O(|V(G)|2|E(G)|)
h
16
求解中国邮递员问题的算法（例）
h
17
求解中国邮递员问题的算法（例）
h
18
解决这样的问题，可以采用奇偶 点图上作业法：如果在配送范围 内，街道中没有奇点，那么他就 可以从配送中心出发，走过每条 街道一次，且仅一次，最后回到 配送中心，这样他所走的路程也

邮件送递问题【摘要】本文的主要思想，是将邮件送递问题转化为图论中的旅行商问题，求最佳哈密尔顿回路，在此基础上，结合重量、体积、时间这三个约束条件，对送递路线进行调整，找到最佳的送递路线。

问题一，用Floyd算法计算51个地点任意两点之间的最短距离，然后采用二边逐次修正法求21个送达地点构成的最佳H圈。

为减小二次逐边修正法对初始圈的敏感，每次随机搜索1000个初始圈。

为提高计算速度；我们采用在MATLAB 环境中，用矩阵翻转的方法来实现二边逐次修正的过程。

最终我们求得序号分别为3和150的两条总路程最短的送递路径。

两条路径的总长度均为54.708km，总时间3.149小时。

问题二，在第一问的基础上，我们对1000条近似最短路径进行时间检验，计算每条路径上每一点邮件送达的时间是否早于要求的时间，从而判断该路径是否符合时间要求。

我们从1000条近似最短路径中筛选出48条符合时间要求的路径，再从中找出总长度最短的路径，得到序号为150的路径为本问题的最佳方案。

问题三，本问题相比第一问，增加了分组的问题。

由于邮件重量和体积的约束，100个邮件需分批次送递，我们制定了衡量分组优劣的标准——均衡度 ，以此为准则，我们对Prim算法求出的50点最小生成树做适当调整，并结合重量、体积两个约束条件，确定分组。

完成分组后，求解每一组地点的送递路径，与第一问相同。

最终我们得到均衡度为0.026的分组方案及各组的送递路径，并求出送完所有邮件的最短时间为6.728h。

问题四针对第一小问，在第一问基础上增加检验邮递员到达每一地点的重量和体积，我们求出分2组的送递路径。

针对第二小问，在第一小问基础上增加检验邮递员到达每一地点的实际时间，提出以准点率为标准衡量路径优劣，求出准点率为76.2%的最佳路径。

针对第三小问，由于邮件增多带来的重量、体积的上升，分组数目相应增加，最终我们求出分6组，准点率为72.0%的送递路径。

【关键词】最优H圈，二边逐次修正法，矩阵翻转，最小生成树，均衡度一、问题的提出现有一邮局在图1中的O 点，一邮递员需将邮件送至城市内多处。

网络优化与优化算法
一、网络优化及实例
例：中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件. 如何设计一条最短 的投递路线(从邮局出发，经过投递区内每条街道至少一次， 最后返回邮局)？由于这一问题是我国学者管梅谷教授1960 年首先提出的，所以国际上称之为中国邮递员问题.
大规模数据处理是近年竞赛题的 倾如:向
1. 04年A题:奥运会临时超市网点设计 2. 05年A题:长江水质的评价和预测 3. 05年B题:DVD的在线租赁
难 度逐年增大
计算机的应用能力是必要的内容
考虑用一个 图来代替县城结点， 将问题转化为一个TSP问题：
再将三点收缩成一点，就得到 一个三个巡视组的TSP巡视路线
接下来的工作是要均衡各个巡视小组 的工作时间（十分复杂的工作！）
05年杭州电子科技大学校内竞赛题B题 是一个网络优化问题
桥梁选址问题
设下图中每一个圆点代表一个区，连接各圆点的 直线代表公路，粗实线代表交通主干线，曲线代 表一条河流。随着城市经济发展,为了便利河两岸 的交通，决定在适当的位置造桥。假设河流北侧 A到D段有沿岸公路，河的南侧当前还没有修建沿 岸公路。试分别就以下问题讨论：
•单向？ •双向？
欧拉把哥尼斯堡七桥问题转化为一个 图论上的问题：
七桥问题 的
因
答案 是 否定的
为 图
中
没
有
偶
度
顶
点
有些问题目前找不到现成的软件
也没有快速求解最优解的方法
例4 TSP（Travel Sales Man Problem）问题
到设城有市城j市的集费合用I 为 {1，c2，ij，，in,}

G-E（C）仍然无奇数度结点。
?
由于G是连通的，C中应至少存在一点v，使G-
E（C）中有一条包含v的回路C′。（见示意图）
2019/7/8

计算机学院
7
C
v
C'
这样，就可以构造出一条由C和C′组成的 G的回路，其包含的边数比C多，与假设矛盾。 因此，C必是Euler回路，结论成立。
2019/7/8
计算机学院
类似于无向图的讨论，对有向图我们有以下 结论： 定理13-1.2 ⅰ）有向连通图G含有有向欧拉道路，当且仅当
除了两个结点以外，其余结点的入度等于出度， 而这两个例外的结点中，一个结点的入度比出 度大1，另一个结点的出度比入度大1。 ⅱ）有向连通图G含有有向欧拉回路，当且仅当G 中的所有结点的入度等于出度。
计算机学院
16
显然，当这个图是欧拉图时，任何一条欧拉回路都 符合要求；当这个图不是欧拉图时，所求回路必然要重复 通过某些边。
对此，管梅谷曾证明，若图的边数为m，则所求回 路的长度最小是m，最多不超过2m，并且每条边在其中 最多出现两次。中国邮递员问题，一般为在带权连通图 中找一条包括全部边的且权最小的关回键路是。：复制哪些边？
V6
d(V2,V5)=3， d(V3,V5)=4
G
各路径:V1V2(3),V3V5(4)—7
V1V3(5),V2V5(3)—8
V1
V1V5(4),V2V3(2)—6
∴两条长度最短P1=V1V7V5,P2=V2V3
3．构造G’的任一E图就是中国邮递员 V6
问题的解。
G′
V2
3
2
1 3
3 6
V3
3
V7
7

欧拉回路与中国邮递员问题一、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G （V ，E ）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果：定理1 对连通图G （V ，E ），下列条件是相互等价的：（1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．证明 ：()()12⇒ 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数． ()()23⇒ 设G 中每一个节点的度数均为偶数．若能找到一个回路C 1使G=C 1，则结论成立．否则，令G 1=G\C 1，由C 1上每个节点的度数均为偶数，则G 1中的每个节点的度数亦均为偶数．于是在G 1必存在另一个回路C 2．令G 2=G 1\C 2，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路C r 使 G r =G r-1\C r 上各节点的度数均为零，即C r =G r-1．这样就得到Ｇ的一个分解 G C C C r =⋅⋅⋅12 ．()()31⇒ 设G C C C r =⋅⋅⋅12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法．二、弗罗莱算法算法步骤如下：（1）任取起始点v v R 00,;→（2）设路)},({,),,({),,({1211201r r i i r i i i v v e v v e v v e R -⋅⋅⋅=已选出，则从E\},,,{21r e e e ⋅⋅⋅中选出边1+r e ，使1+r e 与r i v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等下面给出此算法的matlab程序：function myeuler%求出一个图的欧拉回路n=input('输入起点')result=[n];a=load('D:\data.txt');%边权矩阵while length(result)~=length(find(a>0&a<99999999))n=result(length(result));temp=a(n,:);p=find(temp>0&a<99999999);if length(p)==0sprintf('不是euler图')breakendresult=[result,p(1)];a(n,p(1))=0;endresult三、中国邮递员问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图G（V，E）中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数和最小．也就是说要从包含G的每条边的回路中找一条权数和最小的回路．如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G有奇数度节点，则G的奇数度节点必是偶数个（握手定理）．把奇数度节点分为若干对，每对节点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E ．令G/ =G+E/，即把附加边子集E/叠加在原图G上形成一个多重图G/，这时G/中连接两个节点之间的边不止一条．显然G/是一个欧拉图，因而可以求出G/的欧拉回路．该欧拉回路不仅通过原图G中每条边，同时还通过E/中的每条边，且均仅一次．邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E/的权数ω(E/ )为最小？为此有下列定理．定理3 设G（V，E）为一个连通的赋权图，则使附加边子集E/的权数ω(E/)为最小的充分必要条件是G+E/中任意边至多重复一次，且G+E/中的任意回路中重复边的权数之和不大于该回路总权数的一半．程序实现步骤如下：（1）求出奇数度的点和它们之间任意两点之间的最短距离Matlab程序：function [s,S]=mypostmana=load(‘D:\data.txt’);%也可以直接给出%为了方便我假设我将边权矩阵保存在D盘中%具体情况可以相应修改b=sparse(a);%构造稀疏矩阵Dist=graphallshortestpaths(b);%求出途中任意两点的最短距离s=[];%奇数度的点for k=1:size(a,1)p1=find(a(k,:)>0&a(k,:)<99999);p2=find(a(:,k)>0&a(:,k)<99999);%找出每一个点的出度和入度if mod(p1+p2,2)==1s=[s,k];endendS=Dist(s,s);（2）求出奇数点两两组合权和最小的组合因为使用lingo求解此问题相对简单，因此使用此软件求解Lingo参变量约束条件如下：Lingo程序如下：model:sets:!这里假设有6个奇数度的点;!具体问题作出相应调整即可;city/1..5/;citys(city,city):x,w;endsetsdata:w=@ole('D:\data.xls',w);!将边权矩阵保存在以上地址;enddatamin=@sum(citys:w*x);@for(citys:@bin(x));@for(city(i):x(i,i)=0;);@for(citys(i,j):x(i,j)=x(j,i););@for(city(i):@sum(city(j):x(i,j))=1;@sum(city(j):x(j,i))=1;);（3）利用弗洛来算法求解欧拉回路Matlab程序：function mypostman1x=load('D:\data1.txt');%由lingo软件得到[s,S]=mypostman;a=load('D:\data.txt');%边权矩阵[m,n]=find(x==1);for k=length(s)a(s(m(k)),s(n(k)))=S(m(k),n(k));path=graphshortpath(s(m(k)),s(n(k)),sparse(a))endn=input('输入起点')result=[n];while length(result)~=length(find(a>0&a<99999999))n=result(length(result));temp=a(n,:);p=find(temp>0&a<99999999);if length(p)==0sprintf('不是euler图')breakendresult=[result,p(1)];a(n,p(1))=0;endresult。

值得注意的是，这个方法主要困难在于检查判定标准2。它要求对于图中的每一个圈都检查一遍。当一个连通图所包含的圈数比较多时，将会大大提高运算的工作量，比如“田”字型的图就有13个圈。
到目前为止，关于中国邮递员问题，已经找到了更好的算法，由于篇幅所限，我们就不去介绍它了。
当q=3时，显然G是欧拉图。假设q=n时成立，看q=m+1的情形：由于G是无奇点的连通图，并且G的点数p>=3，因此存在三个点μ，v,w,使得[μ，v],[w,v]∈E。从G中去掉边[μ，v],[w,v]，增加新的边[μ，w]，得到一个新的多重图G1，G1有q-1条边，且仍不含奇点，G1至多有两个分图。
推论 一个多重连通图G有欧拉链的充分必要条件是G有且仅有两个奇点。
这个推论的证明留给读者作为习题。
从这个定理的证明可以看出，识别一个连通图能否一笔画出的条件是它是否有奇点。若有奇点，就不能一笔画出。若没有奇点，就能够一笔画出，并回到原出发地。
比如前面提到的哥尼斯堡七桥问题，欧拉把它抽象成具有四个项点，并且都是奇点的图8.26的形状。很明显，一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。图8.27。仅有两个奇点，可以一笔画出。
v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1, 总长是12。 也可以按照另一条路线走： v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1, 总长是11。 按照第1条路线走，在边[v2,v4],[v4,v6],[v6,v5]上各走3两次，按照第2条路线走，在边[v3,v2],[v3,v5]上各走了两次。
图8.26
B
A
D
C
图8.27
v5
v6
v4

结合图论知识,上述货郎担问题本质就是在赋 权完全图中，找出一个最小权的Hamilton圈，此 圈称为最优圈.与最短路问题相反，至今尚未有求 解旅行售货商问题的有效算法，因此，在这里只试 图找出较好的解，但不一定是最优解。
针对旅行售货商问题,给出较好的近似算法，即 最临近算法和一个修改算法.设n个顶点的赋值完 全图为G，W为权值矩阵。根据实际问题，可以 假设wuv+w(vx)>=w(ux).
2. 用新圈代替旧圈,直至终止.
算法的Matlab程序见文档
例：给定四个点 0,0,(100,1000),(0,2),(1000,0),用改良圈算法 计算经过这四个点的Hamilton圈.
V= 0 0 ;100 1000; 0 2; 1000 0 For i=1：4
for j=1:4 Wi,j=sqrt((V(i,1)-V(j,1))^2+(V(i,2)-V(j,2))^2); end end
ቤተ መጻሕፍቲ ባይዱ
第四讲习题： 1. 判断图1是否是欧拉图,若是，求Euler回路.
2.给定10个点的坐标5,67,(37,8),(4,97),(200,9),
(81,5),(4,50),(4,420),(250,381),(-3,40),(7,-64), 试用改良圈算法求通过这10个点的Hamilton圈. 计算直接10个点顺序的圈的长度,并比较结果。
Fleury算法步骤
1. 确定任意一个起点. 2. 若某条行迹已经确定,从E-{e1,e2,…,ei}中选择
下一条边，满足
a。 ei+1与ei相邻
b。除非无选择余地，否则ei+1不是G=G-
{e1,e2,….ei}的桥 3. 直到步骤2不能进行为止。

要求1）的解法1 由于是双车道，因此可将每条边看成来回两条 异向弧，此时，图是有向欧拉图，可用hierholzer算 法在有向图上求出有向欧拉巡回。 10 v2 6 v3 v1 6 v6 5 v12 8 v4 5 7 v7 4 3 3 v5 4 9 6 5 v9 1 v10 2 v15
2 v8 3
v11 1 1 v13 v14
基本概念与基本结论
无向图的情形
设G=(V,E)是连通无向图。 G=(V,E)是连通无向图 是连通无向图。 1）巡回：经过G的每边至少一次的封闭路线。 巡回：经过G的每边至少一次的封闭路线。 2）欧拉巡回：经过G的每边正好一次的巡回。 欧拉巡回：经过G的每边正好一次的巡回。 3）欧拉图：存在欧拉巡回的图。 欧拉图：存在欧拉巡回的图。 4）欧拉道路：经过G的每边正好一次的道路。 欧拉道路：经过G的每边正好一次的道路。 5）最佳巡回：加权连通图的边权总和最小的巡回。 最佳巡回：加权连通图的边权总和最小的巡回。
求欧拉图欧拉巡回的算法
Fleury算法 Fleury算法 是欧拉图。 设G是欧拉图。 V(G) = {v0,v1,…,vn} , E(G) = {e1,e2,…,em} 1) 任选顶点为v0 ，置途径W= v0 。 任选顶点为v 置途径W= 2) 设途径W= v0 e1v1… ei vi已经选定，则按下述条件 设途径W= 已经选定， 中选取e 从E - {e1,e2,…, ei}中选取ei+1。 相关联。 （a） ei+1与vi相关联。 除非没有别的选择，否则一定要使e （b） 除非没有别的选择，否则一定要使ei+1不是 G - {e1,e2,…, ei}的割边。 的割边。 3 ) 当第2步不能执行时，算法停止。 当第2步不能执行时，算法停止。 停止后， 即是所求欧拉回路。 停止后，W 即是所求欧拉回路。

图论方法：
最短路问题：两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线 （Dijkstra算法 ）每对顶点之间的最短路径 （Dijkstra算法、Floyd算法 ）。
最小生成树问题：连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法 ）。
图的匹配问题：人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)。
遍历性问题：中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线
时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列—通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动）
自回归模型：一般自回归模型AR(n)—系统在时刻t的响应X(t)仅与其以前时刻的响应X(t-1),…， X(t-n)有关，而与其以前时刻进入系统的扰动无关 ；移动平均模型MA(m)—系统在时刻t的响应X(t) ，与其以前任何时刻的响应无关，而与其以前时刻进入系统的扰动a(t-1),…,a(t-m)存在着一定的相关关系 ；自回归移动平均模型 ARMA(n,m)—系统在时刻t的响应X(t)，不仅与其前n个时刻的自身值有关，而且还与其前m个时刻进入系统的扰动存在一定的依存关系 。
这些方法可以解一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。
拟合与插值方法（给出一批数据点，确定满足特定要求的曲线或者曲面，从而反映对象整体的变化趋势）： matlab可以实现一元函数，包括多项式和非线性函数的拟合以及多元函数的拟合，即回归分析，从而确定函数； 同时也可以用matlab实现分段线性、多项式、样条以及多维插值。

中国邮递员问题的matlabchengxuclear;clc;M=inf;a(1,1)=0;a(1,36)=10.3;a(1,37)=5.9;a(1,38)=11.2; a(1,50)=6.0;a(2,2)=0;a(2,50)=9.2; a(2,5)=8.3;a(2,3)=4.8;a(3,3)=0;a(3,39)=8.2; a(3,38)=7.9;a(4,4)=0;a(4,39)=12.7; a(4,8)=20.4;a(5,5)=0;a(5,6)=9.7; a(5,39)=11.3; a(5,48)=11.4;a(6,6)=0;a(6,7)=7.3;a(6,47)=11.8; a(6,48)=9.5;a(7,7)=0;a(7,47)=14.5; a(7,40)=7.2; a(7,39)=15.1;a(8,8)=0;a(8,40)=8.0;a(9,9)=0;a(9,40)=7.8; a(9,41)=5.6;a(10,10)=0;a(10,41)=10.8;a(11,11)=0;a(11,42)=6.8; a(11,45)=13.2; a(11,40)=14.2;a(12,12)=0;a(12,43)=10.2; a(12,42)=7.8;a(12,41)=12.2;a(13,13)=0;a(13,45)=9.8;a(13,44)=16.4;a(13,42)=8.6; a(13,14)=8.6; a(14,14)=0;a(14,43)=9.9; a(14,15)=15.0;a(15,15)=0;a(15,44)=8.8;a(16,16)=0;a(16,17)=6.8;a(16,44)=11.8;a(17,17)=0;a(17,22)=6.7; a(17,46)=9.8;a(18,18)=0;a(18,46)=9.2; a(18,45)=8.2; a(18,44)=8.2;a(19,19)=0;a(19,20)=9.3; a(19,45)=8.1; a(19,47)=7.2;a(20,20)=0;a(20,21)=7.9;a(20,25)=6.5; a(20,47)=5.5;a(21,21)=0;a(21,23)=9.1;a(21,25)=7.8; a(21,46)=4.1;a(22,22)=0;a(22,23)=10.0; a(22,46)=10.1;a(23,23)=0;a(23,24)=8.9; a(23,49)=7.9;a(24,24)=0;a(24,27)=18.8; a(24,49)=13.2;a(25,25)=0;a(25,49)=8.8; a(25,48)=12.0;a(26,26)=0;a(26,27)=7.8; a(26,49)=10.5; a(26,51)=10.5;a(27,27)=0;a(27,28)=7.9;a(28,28)=0;a(28,52)=8.3; a(28,51)=12.1;a(29,29)=0;a(29,52)=7.2; a(29,51)=15.2; a(29,53)=7.9;a(30,30)=0;a(30,32)=10.3; a(30,52)=7.7;a(31,31)=0;a(31,33)=7.3;a(31,32)=8.1; a(31,53)=9.2;a(32,32)=0;a(32,33)=19;a(32,35)=14.9;a(33,33)=0;a(33,35)=20.3; a(33,36)=7.4;a(34,34)=0;a(34,35)=8.2; a(34,36)=11.5; a(34,37)=17.6;a(35,35)=0;a(36,36)=0;a(36,53)=8.8;a(36,37)=12.2;a(37,37)=0;a(37,38)=11.0;a(38,38)=0;a(38,50)=11.5;a(39,39)=0;a(41,41)=0;a(42,42)=0;a(43,43)=0;a(44,44)=0;a(44,45)=15.8;a(45,45)=0;a(46,46)=0;a(47,47)=0;a(48,48)=0;a(48,49)=14.2; a(48,50)=19.8;a(49,49)=0;a(50,50)=0;a(50,53)=12.9;a(50,51)=10.1;a(51,51)=0;a(52,52)=0;a(53,53)=0;% 用1、2 、3……35表示35个村：用36、37……53表示各乡镇。