Euler 图和 Hamilton 图、求解旅行商问题的 改良圈算法 ：

浅夏110

             Euler 图就是从一顶点出发【每条边】恰通过一次能回到出发点的那种图，【中国邮递员问题】的数学模型是：在一个赋权连通图上求一个含所有边的回路， 且使此回路的权最小。 显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为 所求。
  r) Q5 J* E$ t* R
& \+ J, c/ ~1 T             Hamilton 图就是从一顶点出发【每个顶点】恰通过一次能回到出发点的那种图。【旅行商问题描述】一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。
! X, ?' O4 U7 A+ h+ H8 `
) x, E$ P5 J1 y0 N# P% n" j1 基本概念
【定义】 经过G 的每条边的迹叫做G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路或 E 回路；含 Euler 回路的图叫做 Euler 图。 直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即 不重复地行遍所有的边再回到出发点。



【定义 】包含G 的每个顶点的轨叫做 Hamilton(哈密顿)轨；闭的 Hamilton 轨叫做 Hamilton 圈或 H 圈；含 Hamilton 圈的图叫做 Hamilton 图。 直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。
- ~7 @5 r, ^: U/ a
2 Euler 回路的 Fleury 算法
0 y- {7 P! Y  z3 z1921 年，Fleury 给出下面的求 Euler 回路的算法。



. C( o0 Y$ ^3 y! {5 s
6 D3 a, e$ N4 [& s) u- x
/ s3 D* I# D# w4 H7 {例 ：邮递员问题
中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的 每条街道至少一次，为他设计一条投递路线，使得他行程最短。

上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路， 且使此回路的权最小。 显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为 所求。
4 g2 g! d( F% m+ \
非 Euler 图的权最小的回路的求解方法

对于非 Euler 图，1973 年，Edmonds 和 Johnson 给出下面的解法：
% w: O4 R4 Y8 M+ J$ N, g( ]- m# _. p
4 T/ z1 h1 l( q6 q/ N4 X
9 p. A- p1 V% l( o- j* Z
多邮递员问题
6 P8 D0 v* {: I) k% Y" ` 邮局有 k(k ≥ 2) 位投递员，同时投递信件，全城街道都要投递，完成任务返回邮 局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成 kPP。 kPP 的数学模型如下：
0 T7 A/ M/ k7 N( v. s2 E- p0 \


! f8 a6 _: v) s( f2 p" x* h3 旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称 为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行 商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。
, k& P, U5 i; ^9 z. C
3.1 改良圈算法

6 k6 T2 S# U' V. X: R

+ Q# ?: }9 ^4 _( L% h2 k
+ g0 Z9 U- Q8 M用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以 选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用 Kruskal 算法加以说明。

" `" O& t0 a5 v- q- l, t8 h假设C 是G 中的最优圈。 则对于任何顶点v ，C − v 是在G − v 中的 Hamilton 轨，因而也是G − v 的生成树。由 此推知：若 T 是 G − v 中的最优树，同时 e 和 f 是和 v 关联的两条边，并使得 w(e) + w( f ) 尽可能小，则 w(T ) + w(e) + w( f ) 将是 w(C) 的一个上界。 这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条 边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不对了。

6 k3 {; K$ R' h/ k- ^, t例 15 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa) 五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之 间的航线距离如表 7。

+ r9 R, `  V9 W9 v# I
. ]3 t$ @: K. R+ F& ^
解：编写程序如下：

function main
clc,clear
9 V0 F; W) a3 l5 K8 D# xglobal a
2 E5 ]* f& F% r( N1 [a=zeros(6);
( X" s& w! [' [, Y8 A) O0 da(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
- b0 O: V+ E  x+ _/ ?+ F9 ]4 [4 Ja(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;
a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;
a(5,6)=13; a=a+a'; L=size(a,1);
c1=[5 1:4 6];
* m, Z7 c  C& o1 }; p2 `( e+ j[circle,long]=modifycircle(c1,L);
2 s& r' U) [( c( e) E+ f+ Lc2=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
[circle2,long2]=modifycircle(c2,L);
if long2<long
    long=long2;
    circle=circle2;
end
1 h/ r2 k) P/ _- v: N, l0 v- q; X. |: ~! [circle,long
# M& T# B# C# t+ V%*******************************************
/ h! z5 H! t. A6 K) H%修改圈的子函数
%*******************************************
( X  D1 L0 J& p; |* M/ {4 P9 Ffunction [circle,long]=modifycircle(c1,L);
global a
" H# s! n, f) ]0 W8 A0 e4 `/ Pflag=1;
while flag>0
$ ]9 B( @; R* P/ q3 m4 j' x    flag=0;
' {# G/ |+ w* p4 ^- v    for m=1-3
        for n=m+2-1
: f1 D  w9 I! ^  b& G            if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
                a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
                flag=1;
                c1(m+1:n)=c1(n:-1:m+1);
            end
3 W$ Y* p5 A% p        end
    end
3 n. l, H/ |, _0 cend
long=a(c1(1),c1(L));
5 d" {/ q2 J2 z& M3 _/ Ofor i=1-1
- c' I6 w4 R% v1 t& `    long=long+a(c1(i),c1(i+1));
end
circle=c1;


3.2  旅行商问题的数学表达式
) z! `% ^: u% ~) O, E
& `2 E! Q: W3 Z* E3 d: r
将旅行商问题写成数学规划的具体形式还需要一定的技巧，下面的例子我们引用 LINGO 帮助中的一个程序。

例 16  已知 SV 地区各城镇之间距离见表 8，某公司计划在 SV 地区做广告宣传， 推销员从城市 1 出发，经过各个城镇，再回到城市 1。为节约开支，公司希望推销员走 过这 10 个城镇的总距离最少。


2 a' v0 J2 E: o

. k5 ~8 q! O5 @; y
解 编写 LINGO 程序如下：

MODEL:
SETS:
, [  p$ V- {9 x CITY / 1.. 10/: U; ! U( I) = sequence no. of city;
- d2 ^$ K& s# C% g( X3 c LINK( CITY, CITY):
DIST, ! The distance matrix;
+ N$ i0 {0 s3 {* ^3 K8 g) G X; ! X( I, J) = 1 if we use link I, J;
4 q0 A+ X5 Y. E- G- e ENDSETS
+ \/ O; f( a% m; q( m DATA: !Distance matrix, it need not be symmetric;
( b5 z9 g3 Q# _. ?2 w0 m DIST =0 8 5 9 12 14 12 16 17 22
/ }( q7 H  F7 |' d/ Q, q 8 0 9 15 17 8 11 18 14 22
# |  t7 I) o$ p 5 9 0 7 9 11 7 12 12 17
9 15 7 0 3 17 10 7 15 18
12 17 9 3 0 8 10 6 15 15
5 `- H3 A+ I" W  d- I 14 8 11 17 8 0 9 14 8 16
12 11 7 10 10 9 0 8 6 11
! W- g/ G0 V; L 16 18 12 7 6 14 8 0 11 11
17 14 12 15 15 8 6 11 0 10
$ S8 c1 `0 z6 e, a- i, h& h$ d 22 22 17 18 15 16 11 11 10 0;
ENDDATA
: O) x5 A; Q' w& [7 X !The model:Ref. Desrochers & Laporte, OR Letters,
8 O1 x2 o+ L; O0 o6 Z Feb. 91;
N = @SIZE( CITY);
" P3 O4 C: P: ^5 J* _2 w8 t MIN = @SUM( LINK: DIST * X);
@FOR( CITY( K):
! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
! Weak form of the subtour breaking constraints;
! These are not very powerful for large problems;
+ N+ f9 n6 d9 L @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
8 t; X- Y# B9 j0 l8 ^2 i7 Y/ x% K ( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K)));
# ?$ F3 O$ p6 ^& W4 t, q9 N ! Make the X's 0/1;
@FOR( LINK: @BIN( X));
! For the first and last stop we know...;
@FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
1 Y+ J) u" `% o: N. Q U( K) >= 1 + ( N - 2) * X( K, 1));
END



0 C) E# ^4 _( [% t' D————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 Q* L3 I) X! @, J, ]0 t, d原文链接：https://blog.csdn.net/qq_29831163/article/details/89788999
( R* F% z3 K6 G% t$ a+ h# {

3 g# L+ l0 ?/ A1 S# }  w0 c+ j