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

浅夏110

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

2 N& V1 Z: u. `- U$ Z5 ~+ C             Hamilton 图就是从一顶点出发【每个顶点】恰通过一次能回到出发点的那种图。【旅行商问题描述】一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。
4 u. N. [9 j3 Y; I2 a# a2 |
1 基本概念
【定义】 经过G 的每条边的迹叫做G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路或 E 回路；含 Euler 回路的图叫做 Euler 图。 直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即 不重复地行遍所有的边再回到出发点。
& t; n* z0 P/ k4 N1 M

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

4 N( d+ T4 L6 m" R2 Euler 回路的 Fleury 算法
. S0 J2 h  Q( U3 N- Z1921 年，Fleury 给出下面的求 Euler 回路的算法。



, C* S+ g- g6 h. p( _
' G& E+ K7 Q2 t: Q2 n7 W( e
5 w# d% z* t. t+ R( E  V例 ：邮递员问题
7 x0 H- @' `5 y/ b7 j# F3 C; ]# y中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的 每条街道至少一次，为他设计一条投递路线，使得他行程最短。

上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路， 且使此回路的权最小。 显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为 所求。
& K, ~% `" q# E8 F: s
! Q& l+ m% H* H; b) V% u* w1 h非 Euler 图的权最小的回路的求解方法
( p: f+ K0 |# o# Z
; L4 U' G0 c/ T- E对于非 Euler 图，1973 年，Edmonds 和 Johnson 给出下面的解法：
% x0 v( T+ x# c: U

6 C7 \4 a6 p9 j2 V% U" [
多邮递员问题
邮局有 k(k ≥ 2) 位投递员，同时投递信件，全城街道都要投递，完成任务返回邮 局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成 kPP。 kPP 的数学模型如下：
$ r& T9 n' L. n. U  _1 c
; T4 l0 y9 |' g+ v1 \$ P5 `
& ], k: U, J4 y+ H
! z. e/ J' D; \3 旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条 最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称 为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行 商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

3.1 改良圈算法


: x4 R3 q" V" [* u* G
6 R/ {, x0 x5 Y3 C
用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以 选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用 Kruskal 算法加以说明。

. a7 W" u9 D) i: c3 F假设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) 的一个上界。 这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条 边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不对了。

! k4 l% I8 M/ |" O. j% G( ~例 15 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa) 五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之 间的航线距离如表 7。

6 J  F# F5 h- q2 i. G- N3 ]4 d% ]
6 i6 H( A  x4 s2 `" g, U. k
解：编写程序如下：

function main
7 J9 s/ ]: n2 y0 d. Pclc,clear
global a
, Z1 V( P, p9 p% oa=zeros(6);
# r0 h; [5 p; b! q5 t7 o3 [0 ?a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
& ?% W4 T' l6 V" I. b2 \! o8 ^- Fa(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];
[circle,long]=modifycircle(c1,L);
" h8 ]$ V, y# J* ~% uc2=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
. w4 b" y& R) U" n; A: T8 h5 c5 U[circle2,long2]=modifycircle(c2,L);
3 c& b, D/ M; A! M& ^, B& {if long2<long
    long=long2;
" J; w8 T4 L: ]8 ]: f    circle=circle2;
end
circle,long
9 @2 a! W2 V9 J, `) n%*******************************************
! U- o- F: }3 j9 [%修改圈的子函数
9 P" j7 o3 E/ H3 A%*******************************************
function [circle,long]=modifycircle(c1,L);
+ j: W: y% N* z- oglobal a
* f( @& ], i3 o2 qflag=1;
9 l0 t8 R7 a0 Y2 v* Jwhile flag>0
4 ], {+ g. E) d  x9 f7 p; G7 ]    flag=0;
; L: N+ o2 p- m' E8 z' y9 e    for m=1-3
0 c. |/ o; Z2 X+ |$ m9 x        for n=m+2-1
            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))
6 P4 V- g7 m$ y! s& x0 ?                flag=1;
                c1(m+1:n)=c1(n:-1:m+1);
6 E: O5 M# T) n* I) ^            end
5 x9 z8 n+ l: ^4 g+ Y6 ^        end
5 O* c5 y7 j( S. w& R! G/ c" I# k    end
end
long=a(c1(1),c1(L));
9 F: P1 ~# f3 ^/ dfor i=1-1
$ S# u* z7 u" z& F3 |) Z2 s    long=long+a(c1(i),c1(i+1));
end
circle=c1;
6 W* N8 c$ k6 i9 A5 |. g
0 `& V. q( c9 a& N2 [$ I1 t! o
3.2  旅行商问题的数学表达式

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

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

  u# P/ `1 @' E5 u. N- f: @


: O: U! R8 U' G& f! y5 Y" n解 编写 LINGO 程序如下：
; \3 T1 M/ f+ [1 h" r( Y0 r
MODEL:
SETS:
& j+ V7 I3 j% `$ ?( S" s+ L+ F% o CITY / 1.. 10/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
0 d2 ^1 e) W; J- T* i ENDSETS
9 g4 B0 ~  h& C9 \/ _( q7 G. d DATA: !Distance matrix, it need not be symmetric;
DIST =0 8 5 9 12 14 12 16 17 22
8 0 9 15 17 8 11 18 14 22
5 9 0 7 9 11 7 12 12 17
4 n0 ?6 d' [- w6 i2 P+ A/ ] 9 15 7 0 3 17 10 7 15 18
12 17 9 3 0 8 10 6 15 15
5 O, y; n$ j! c) G" J% G- r% j: } 14 8 11 17 8 0 9 14 8 16
12 11 7 10 10 9 0 8 6 11
: `& X. A( T  Z5 O 16 18 12 7 6 14 8 0 11 11
17 14 12 15 15 8 6 11 0 10
+ S1 ^, @8 Q) U& o4 H- }/ U 22 22 17 18 15 16 11 11 10 0;
ENDDATA
, L: T1 O  M. ]( y- k8 J8 i$ v !The model:Ref. Desrochers & Laporte, OR Letters,
Feb. 91;
, g+ x  t; n0 u4 p N = @SIZE( CITY);
8 L$ ~# t: A: G1 s" Y8 ]; r' I MIN = @SUM( LINK: DIST * X);
@FOR( CITY( K):
! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
6 h* J) m6 H5 u  g* j0 Y9 {4 l0 u# o ! It must be departed;
) \$ R+ c# T: F, s: H/ l @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;
! g/ w. a; V/ p6 G @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K)));
. G- Z! M! V* _' [. R ! Make the X's 0/1;
@FOR( LINK: @BIN( X));
! For the first and last stop we know...;
@FOR( CITY( K)| K #GT# 1:
! n) ]6 P* }% r4 k5 n, _7 w7 \- n U( K) <= N - 1 - ( N - 2) * X( 1, K);
3 E+ M1 b4 F- O- W& V' P. g U( K) >= 1 + ( N - 2) * X( K, 1));
END

0 P8 v! i" M9 W, z9 m

2 }* h- i' u! J* P- ?: N( i6 y————————————————
9 j! _. {( n$ T: t) N% {8 P版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89788999