-
最优闭回路问题
目录
（1）先求图1中任意两点之间的距离矩阵d1如表1（Floyd算法）。
一、欧拉回路与道路
1、欧拉回路与道路
连通图G中，若存在一条道路，经过每一边一次且仅一次，则称这条路为欧拉道路。若存在一条回路经过每边一次仅一次，称这条回路为欧拉回路。
具有欧拉回路的图称为欧拉图，简称E图。
2、欧拉图存在的条件
（1）无向连通图G是欧拉图当且仅当G中无奇点（出入次和为奇数）。
（2）连通有向图G是欧拉图，当且仅当它的每个顶点的出次等于入次。
二、中国邮路问题
1、中国邮路问题
一个邮递员，负责某一地区邮件投递，他每天从邮局出发，走遍该地区所有街道在返回邮局，问应如何安排送信的路线，可以使他所走的路线总路程最短（1962，管谷梅）。
给定一个连通图G，每边有权L(e)，要求一条回路经过每边至少一次，且满足总权和最小。
2、中国邮路问题求解
（1）若连通图G没有奇点，则是一个欧拉图，显然按照欧拉回路走就满足要求：每边一次仅一次，且权和最小；
（2）若G中有奇点，则有些边走过不止一次，这相当于对图G增加一些重复边E1，得到新的图G1=G+E1，使得G1没有奇点，且满足路程最短。
3、有奇点的G的中国邮路问题等价问题
连通图G=(V,E)中，求一个边集E1(E的子集），将E1的边均变成重复边得到G1=G+E1,使得G1无奇点，且
E1*存在的充分必要条件：
（1）每条边最多重复一次；
（2）对图G中每个初等圈来说，重复边的长度不超过圈长的一半。
例1
求图1所示网络的中国邮路问题
【问题分析】
图1中，点v2,v4,v6,v8为奇点，为了使得所有的点为偶点，需要构造辅助边.如果增加(v6,v3)和（v3,v2)，等价于直接增加边(v6,v2)（距离由最短距离决定）。
（1）先求图1中任意两点之间的距离矩阵d1如表1（Floyd算法）。
- sets:
- dian/1..10/:L;
- link(dian,dian):d,x;
- endsets
- data:
- d=@ole('d:\lianxian','d_1');
- enddata
- n=@size(dian);
- min=@sum(link(i,j)|i#ne#j:d(i,j)*x(i,j));
- @for(dian(i):@sum(dian(j)|j#ne#i:x(i,j))=1);
- @for(dian(i):@sum(dian(j)|j#ne#i:x(j,i))=1);
- @for(dian(i):@for(dian(j)|j#ne#i#and#j#gt#1:
- L(j)>L(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i)));
- @for(dian(i):L(i)
- @for(dian(i):L(i)>-1+(n-2)*x(i,1));
- @for(link:@bin(x));
表1 图1中各点间最短距离
vi\vj
v1
v2
v3
v4
v5
v6
v7
v8
v9
v1
0
5
10
9
11
12
13
15
16
v2
5
0
5
10
6
7
14
10
11
v3
10
5
0
9
5
2
13
9
6
v4
9
10
9
0
4
7
4
8
11
v5
11
6
5
4
0
3
8
4
7
v6
12
7
2
7
3
0
11
7
4
v7
13
14
13
4
8
11
0
4
7
v8
15
10
9
8
4
7
4
0
3
v9
16
11
6
11
7
4
7
3
0
根据表1，奇点间最短距离为
d1(v2,v6)=7;
d1(v2,v4)=10;
d1(v2,v8)=10;
d1(v4,v6)=7;
d1(v4,v8)=8;
d1(v6,v8)=7;（2）确定奇点之间的连线方案
- 如图2所示，若增加(v2,v6)，(v4,v8)边，所有点为偶数点，增加长度为15；
- 如图3所示，若增加(v6,v8)，(v2,v4)边，所有点为偶点，增加长度为17；
- 如图4所示，若增加重复边(v4,v6)，(v2,v8)，所有点为偶点，增加长度为17；
三种方案比较，选择图2所示方案。
（3）规划邮路
从v1出发，经过图2中所有边一次，仅一次回到v1的路径，见图5箭头所示。
v1-v4-v7-v8-v9-v6-v3-v2-v6-v5-v8-v4-v5-v2-v1（不止一种线路）
三、旅行商问题
Hamilton图： 包含图G中每个顶点的路，称为Hamilton路，包含G中每个顶点的圈，称为Hamilton圈（回路）。
例2 旅行商路线问题（算法：tsp问题）
某公司计划在某地区的1-10这10个城镇做广告宣传，推销从城市1出发，再回到1，已知这个10个城镇之间的距离如表2所示。为节约开支，公司希望推销员走过这10个城镇的总距离最少。
表2 各城镇之间的距离
i/j
1
2
3
4
5
6
7
8
9
10
1
0
8
5
9
12
14
12
16
17
22
2
8
0
9
15
16
8
11
18
14
22
3
5
9
0
7
9
11
7
12
12
17
4
9
15
7
0
3
17
10
7
15
15
5
12
16
9
3
0
8
10
6
15
15
6
14
8
11
17
8
0
9
14
8
16
7
12
11
7
10
10
9
0
8
6
11
8
16
18
12
7
6
14
8
0
11
11
9
17
14
12
15
15
8
6
11
0
10
10
22
22
17
15
15
16
11
11
10
0
【符号设置】
- G=(V,E) 各城镇连接生产的图；
- dij 两点i与j的距离；
- L(i) 点i到根1的距离（水平变量）；（用来防止提前生成圈）
【模型假设】
（1）经过各城镇一次仅一次；
【建立模型】
（1）连接的各城镇之间的总距离的最小值
（2）每个点只有一个出次
（3）每个点只有一个入次
（4）点i与j的前行后继关系（除1外）
（5）节点i与节点1的距离
（6）变量限制
【数学模型】
【模型求解】
最小路程为73（单位），点与点的连接关系为x(1,2)=1,x(2,6)=1,x(6,5)=1,x(5,4)=1,x(4,8)=1 x(8,10)=1,x(10,9)=1,x(9,7)=1,x(7,3)=1,x(3,1)=1
行程网络图如下
-
相关阅读:
FinalShell软件连接成功后，root文件夹显示一直加载中....
.NET ABP.Zero 项目疑似内存排查历程
奔跑的大学生
计算 tensorflow 和 pytorch 模型的浮点运算数
wxFormBuilder + wxPython的wxListbook实现页面切换菜单
递归组装树结构的数据
TaWRKY19/61/82激活糖转运蛋白TaSTP3从而增强小麦条锈病敏感性
农村人口房屋管理系统（C#+Mysql）
(4E)-TCO-PEG4-DBCO,1801863-88-6,反式环辛烯-四聚乙二醇-二苯并环辛炔
利用反射动态构造wrapper条件( 利用反射获取注解值以及实体类值)
- 原文地址：https://blog.csdn.net/m0_63024355/article/details/133916950
