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

浅夏110

             Euler 图就是从一顶点出发【每条边】恰通过一次能回到出发点的那种图，【中国邮递员问题】的数学模型是：在一个赋权连通图上求一个含所有边的回路， 且使此回路的权最小。 显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为 所求。

             Hamilton 图就是从一顶点出发【每个顶点】恰通过一次能回到出发点的那种图。【旅行商问题描述】一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。
, d- {' i5 s7 @% p1 A
% g+ ]+ G/ H$ I. D1 基本概念
0 x' g4 o: |+ y0 b: a( k5 f【定义】 经过G 的每条边的迹叫做G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路或 E 回路；含 Euler 回路的图叫做 Euler 图。 直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即 不重复地行遍所有的边再回到出发点。
& s: K& P3 k" S: Q7 R3 g9 K% b


【定义 】包含G 的每个顶点的轨叫做 Hamilton(哈密顿)轨；闭的 Hamilton 轨叫做 Hamilton 圈或 H 圈；含 Hamilton 圈的图叫做 Hamilton 图。 直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。

; O3 m; t( W4 J/ }! I  C2 Euler 回路的 Fleury 算法
" j7 e7 M9 N. l2 H7 J1921 年，Fleury 给出下面的求 Euler 回路的算法。
1 U5 V8 F/ F, ^! Q7 T

' q% ?/ d% S) M+ h- o" E& q
" Q  U9 J# F! x& K/ C
; }* b9 O5 O; h9 y: N8 i
8 B  |: I! N# H1 v例 ：邮递员问题
0 V+ f" u' J: R) L) P. `. r! B$ Y" X; }9 D中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的 每条街道至少一次，为他设计一条投递路线，使得他行程最短。

' ^: e+ B/ ^. o' Q上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路， 且使此回路的权最小。 显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为 所求。

; @0 [0 S+ ?  s1 g+ {" [非 Euler 图的权最小的回路的求解方法
) D; @* d6 O3 H) e- B+ S: [4 b8 s
对于非 Euler 图，1973 年，Edmonds 和 Johnson 给出下面的解法：



多邮递员问题
1 \/ u& w7 j3 n- ]* F 邮局有 k(k ≥ 2) 位投递员，同时投递信件，全城街道都要投递，完成任务返回邮 局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成 kPP。 kPP 的数学模型如下：
* m9 D- c) \5 `3 U


. R2 X$ q1 q+ G4 r7 r$ r# R3 旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称 为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行 商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

3.1 改良圈算法
+ X! r- \: j# o9 X* R. I  E5 y



9 U& W+ s, A9 q$ _; v4 q用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以 选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用 Kruskal 算法加以说明。
1 C) K2 g! f2 ^% b8 c
假设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) 的一个上界。 这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条 边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不对了。

. Z3 P  I; R+ T例 15 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa) 五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之 间的航线距离如表 7。
. w/ y5 b0 L) ^9 Y0 K
6 P8 `6 }  o$ p& p& c- V  P& n

# ]9 T; D& _- I* ~$ R解：编写程序如下：

function main
7 n) z4 D! M& S; P1 j& Oclc,clear
global a
% \9 Q6 t3 {. L1 w9 ~0 b- _- w4 _. [a=zeros(6);
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
3 m/ @' X8 q# e9 s! {& \a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;
$ ^  o) D& S8 D/ ]a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;
3 `$ x3 K# z7 \7 x: H7 Wa(5,6)=13; a=a+a'; L=size(a,1);
c1=[5 1:4 6];
; a$ J$ r) ~  y( u4 I[circle,long]=modifycircle(c1,L);
4 f! C8 A/ h% F! uc2=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
( X. \" I% g% v1 Y3 h1 p2 j[circle2,long2]=modifycircle(c2,L);
if long2<long
    long=long2;
    circle=circle2;
& p7 e% t7 M; d/ @! N  gend
circle,long
4 t6 V0 ~3 X. Y( W; [%*******************************************
%修改圈的子函数
%*******************************************
9 o( b" L3 L2 e! y. G' Cfunction [circle,long]=modifycircle(c1,L);
global a
flag=1;
while flag>0
& Z  h, K3 P; x( ^% Q; W    flag=0;
    for m=1-3
        for n=m+2-1
            if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
$ L7 U/ \8 N. q9 Y3 I4 Z! }* b                a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
                flag=1;
                c1(m+1:n)=c1(n:-1:m+1);
            end
        end
    end
end
long=a(c1(1),c1(L));
7 U! Q+ O- N2 U* d3 ]. wfor i=1-1
4 q+ ?6 q& j: A3 \    long=long+a(c1(i),c1(i+1));
end
circle=c1;


3.2  旅行商问题的数学表达式


将旅行商问题写成数学规划的具体形式还需要一定的技巧，下面的例子我们引用 LINGO 帮助中的一个程序。

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

0 X) _* l, h3 d- `* L
! X6 P8 W) E& H( e; m# R) ^6 _2 n

; {+ y/ }, X, W4 d
; o1 l/ k. @- N" ^5 c/ f9 C# H解 编写 LINGO 程序如下：

MODEL:
4 f: l/ d$ }! ]  a0 z: w, e+ J SETS:
2 q, e7 s2 t2 X( B' P' x3 x# a CITY / 1.. 10/: U; ! U( I) = sequence no. of city;
6 f7 P) d9 N3 m( b+ o: p/ V LINK( CITY, CITY):
+ w% [7 O$ B( b" {& r/ F1 J DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Distance matrix, it need not be symmetric;
8 |4 i* }2 |' l! U DIST =0 8 5 9 12 14 12 16 17 22
' U. Z2 _5 j! C4 }( R/ T& U( m 8 0 9 15 17 8 11 18 14 22
# O2 d6 W. w1 F! s% h 5 9 0 7 9 11 7 12 12 17
4 }# Y: T4 T/ Z" e/ H1 W 9 15 7 0 3 17 10 7 15 18
12 17 9 3 0 8 10 6 15 15
5 F1 A) l$ M+ s/ S 14 8 11 17 8 0 9 14 8 16
12 11 7 10 10 9 0 8 6 11
1 c8 J( \4 a5 n& Y3 ~9 H0 `! w8 q7 I 16 18 12 7 6 14 8 0 11 11
17 14 12 15 15 8 6 11 0 10
5 ?, j! U2 P/ S' K0 h( @" N 22 22 17 18 15 16 11 11 10 0;
% j( U' j3 d' s) a9 ]2 @  l ENDDATA
!The model:Ref. Desrochers & Laporte, OR Letters,
Feb. 91;
" Y+ @/ Z, `$ _) f N = @SIZE( CITY);
" W+ k4 r6 b/ [2 Z; s MIN = @SUM( LINK: DIST * X);
. j1 y, |! G% V: [$ O' w9 H8 a0 p @FOR( CITY( K):
! b: |* l1 o; v ! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
8 [( [+ J/ R6 t0 j) b7 ~ ! It must be departed;
& y' G' a1 ?: ^# _8 K @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;
. e  H/ \5 |- l @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
0 ~7 f. x2 h1 M, T, ]4 N7 k U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
8 K, \, X. k+ c" o7 ^ ( N - 3) * X( J, K)));
4 R$ E1 y) U! W- P& K ! Make the X's 0/1;
" N' j- Z& [9 I8 _) @4 ] @FOR( LINK: @BIN( X));
& z* t* n% V2 b5 {* X* E ! For the first and last stop we know...;
8 I9 [- a# o- m @FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
2 M" ^& P3 b! z U( K) >= 1 + ( N - 2) * X( K, 1));
END
9 ~8 h" b, Y- y, P  v% b' `


! y2 ]! ]) H6 G3 w————————————————
) D" X1 r" L) o2 y; f5 O版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 Q* [+ F4 _- }+ ]2 t原文链接：https://blog.csdn.net/qq_29831163/article/details/89788999

2 T3 s" K( J; ]8 q* }2 m