Matlab写的回溯法解TSP问题

tankadozmy

1. function tsp_backtrace(i)
   0 B# I. e% l4 e# e
2. global d;
   8 b: S5 X: G4 o3 ?3 P6 |3 V2 g
3. global x;8 r3 K' H7 Q8 g5 Y5 _
   
4. global n;
   . {- G( c& _+ L3 @. A2 D; ^
5. global m_x;& R8 E. k6 K7 K- _\" T8 Y
   
6. global m_val;
   $ ?' v/ k7 {. C; W# J
7. if i>n
     V\" Z$ A$ Q! ^. J7 ?: p* ?0 e
8. val=0;
   ( U: Q7 _/ s9 t4 h
9. for j=1:n-1! u0 }1 o5 Z\" D; e3 g
   
10. val=val+d(x(j),x(j+1));
    / v7 m. [0 W! i# g& N6 R
11. end
    ( b+ a- [& L' P: m6 {
12. val=val+d(x(n),x(1));* J0 H$ \6 F( N: s- J. x- G
    
13. if m_val>val/ E, I* o8 \* z- D8 O
    
14. m_val=val;3 @' A, j+ c: A# I2 [+ \; Z2 {& U\" {
    
15. m_x=x;! g! c9 K0 O& M3 R7 K+ o
    
16. end- b  B7 E: T- O4 h/ r6 D3 C2 m
    
17. else: P; C6 S: w2 e, r4 X+ D. g
    
18. for j=i:n, f7 R) f' a6 w
    
19. t=x(i); x(i)=x(j); x(j)=t;& u* s( ]) O% P% h4 R
    
20. tsp_backtrace(i+1);8 p# H( k% y1 ?* m
    
21. t=x(i); x(i)=x(j); x(j)=t;
    ! ~5 x( S# [& G  r
22. tsp_backtrace(i+1);
    3 ]6 \$ b  i7 E
23. end
    . ~3 U; x% r5 }$ l6 ?% U
24. end
    . e( E# U. `4 K\" r9 P) ]
25. end

复制代码

下面是个小例子。。。

1. global d;8 `7 z+ M\" c8 T4 B: n3 o- W2 ?6 m
   
2. global x;) K\" }: W+ a- X  G' b4 u% H
   
3. global n;
   0 p7 x- V1 f' d3 f3 l$ n! e7 j6 a
4. global m_x;
   0 U  @2 c, u8 L3 m0 v0 ~( X
5. global m_val;4 v4 k7 i4 A+ R+ T+ c8 {
   
6. d=[0 1 3 5;( P: R. J, `6 Z5 E8 H7 b5 a2 j
   
7. 3 0 2 1;/ H, J  Y6 c8 W& H
   
8. 8 3 0 5;$ m) _' l/ g9 J/ |
   
9. 1 7 3 0];
   / U+ j6 J- h$ [$ A  g) v) u) c
10. x=1:4;  v# F! g/ D+ {; _# Y
    
11. n=4;
    2 B, j0 Y. i2 \2 x5 [
12. m_x=x;
    \" b) c% G: r6 y
13. m_val=inf;
    1 [6 w! r, d: g) F5 o7 ~- {
14. tsp_backtrace(1);

复制代码

李——建辉

尽力而为，无愧于心         103774

nutswang

练练手不错。不过对于规模稍微大点的问题，精确算法的时间消耗就相当严重了，即使使用c。

chenyuanyuan

以前做过 禁忌搜索

fif1fds00712

过来看看！

tankadozmy

插入代码后缩进的格式全不见了。。。。不怨我哈~~~~