查看: 2509|回复: 0

数学建模--图与网络（2）

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2018-10-30 11:25 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

最大流：

注意Matlab 中的最大流问题是必须是单源和单汇问题，因此这里需要构建虚拟的源点S和汇点G。
clc,clear
a = zeros(9,9);
a(1,[2:4]) = [20,20,100];
a(2,[5 6 8]) = [30,10,40];
a(3,[7 8]) = [10,50];
a(4,[5:8]) = [20,10,40,5];
a([5:8],9) = [20,20,60,20];
a = sparse(a);
[b,c] = graphmaxflow(a,1,9)

最大流拓展：最小费用最大流

仅仅是在求得最大流之后进行对最小费用的求解：

clc,cleara = zeros(5);a(1,[2 3]) = [10 8;a(2,[4,5]) = [2 7;a(3,[2 4]) = [5 10;a(4,5) = 4;a = sparse(a);[b c] = graphmaxflow(a,1,5)

最大流量为11

自定义Matlab代码：

最小费用求解' j! A9 a' I$ G! A4 S" v/ f

2 {$ I9 b9 W; I: u$ `. z' Y+ pLingo:
9 c7 v  L. V! O/ q3 ^# B9 M3 _& i
2 p, N& }$ K) ~$ k' u2 S% l( \model:7 r* D  M9 v# ?7 O/ y
sets:5 R$ Q9 A: A& v
nodes/s,1,2,3,t/:d;
+ _: J0 F( P' [# i( b1 ?arcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
+ a0 A. E  I  e& h% H9 Jendsets: w% `1 `9 |6 Y( ~( M( `
data:7 r6 E* E+ |, r9 t4 G8 i
b = 4 1 6 1 2 3 2;0 A9 X3 @/ W/ `% W, v! H8 t
c = 10 8 2 7 5 10 4;: S& H" |" P3 w' m0 _9 U6 q! d
d = 11 0 0 0 -11;
) u" ^* [0 ?1 o3 R# U! Venddata% z' }$ `0 ?9 M1 S- _" _
n = @size(nodes);0 T$ T4 H0 `# _8 l2 _
min = @sum(arcs:b*f);
% J& v- w7 }) h# w@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));' [4 n- ?: l  ^! S; l& Y/ O  \
@for(arcsbnd(0,f,c));" \/ H$ G* `% ~5 r' U
end
6 r! \6 W) Q; g0 K6 K/ U7 R# X1+ l* T9 z6 n& [9 T0 p- b
23 W9 T1 {. W' w* ?7 r' ~; a/ i( F
3
7 `" h( m- }" ^4
8 A5 R! {5 {$ ~6 g50 r& U7 t0 j# N0 m# t! m/ h
6
* F: Z, b7 X5 n. B9 A7
0 ^  S+ k$ r. [6 Q) x/ P8
1 x' U1 Y6 {% d* r  [# P96 b4 z' a* m7 Z* n4 Q
101 D- V0 R! C( Y4 c& D0 w
11+ l  g8 c+ c/ I7 g
12' P( \1 ^5 |; W$ i5 X
13
1 }, a8 B5 {7 S: \141 _: P5 E+ Q2 _4 O! H, I* j" t
154 X, q6 G! F; b% l* m( d
Matlab实现：' C5 X5 }* s3 B% y* q. u5 T
, \/ B( v: Q# j& d$ b2 a
- R( E& D% v+ |; _4 Q
n = 5;5 t7 v, ^' Q. B7 N, g+ M: Q
%弧容量
3 ]9 Q( \( w% `) O+ _/ V/ wa = zeros(5);
! B# H0 a9 X# Z6 }4 Q, Y" Ia(1,[2 3]) = [10 8];, C+ U. Q. U+ h+ {6 W" u' x" B5 P
a(2,[4,5]) = [2 7];: |0 Z# m, q, i. a# R
a(3,[2 4]) = [5 10];
; [$ P3 f) F7 J7 Q# ka(4,5) = 4;6 i( ?) V- O; M5 d0 W% S3 o0 Q
C = a;& W8 r5 H( h( k; A- T
%C = [0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0];+ ?0 S& O, z5 [1 ~1 l- q7 D. Y4 V' c
%弧上单元的费用% ^- n6 i. {. {5 ]2 I
a(1,[2 3]) = [4 1];
3 W7 ?, _2 m, c; l( D) Z: x. m' H! ma(2,[4,5]) = [6 1];
( O) K" d1 g' O7 s4 Ha(3,[2 4]) = [2 3];+ [# p/ I/ O# X' N
a(4,5) = 2;
/ [( q  p8 f% m  }b = a;
4 w( y3 s$ I5 f+ S" l9 ^%b = [0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0];
# ?5 o" A1 y2 P( E%wf表示最大流量。wf0表示预定的流量值8 Q! n* L1 p8 n2 L# t
wf = 0;. R' W3 D5 M: H2 C: d8 [( v" m
wf0 = Inf;1 @1 K. D4 a" [4 p0 T# Q- N  w* W, p
%取初始可行流f为零流
, _8 {2 c$ M7 ^8 Jfor i = 1:n$ p+ o# T6 B  M- G! W
for j = 1:n
% Z( p+ e- ^* T- E       f(i,j) = 0;; ~4 q5 P2 i! R( k: E( R
end
) m; d- R$ Q; K5 V! Gend
4 y/ f2 c# j% z, |while (1)
$ ?. ]  |1 ?( t$ N) `- x4 G# l %构造有向赋权图
: I: J. h9 A* j4 P# V3 z! K for i = 1:n
* W' A7 p  B. w; T8 g; M       for j = 1:n" F4 T6 C5 l1 [/ u5 Q/ ^5 A
         if j~=i
' S1 g/ R- p$ y$ k% l             a(i,j) = Inf;
# P' t) k+ `) m5 W- S          end
7 Y; z: B! f$ m+ y1 e       end; F0 ?- D1 g% \. y, ^! U& @& S7 {
end8 E8 A* K7 z0 ?
for i = 1:n. f% f' N' O' [& O1 W, t3 X  d) U
      for j = 1:n3 r0 ?2 U% r  g/ _8 \) F+ z9 ]
         if C(i,j) > 0 && f(i,j) == 0: {7 m' }0 o4 a( E/ T
            a(i,j) = b(i,j);
' m9 H; F! S3 G, ]! d          elseif C(i,j) > 0 && f(i,j) == C(i,j)
/ A; p8 O8 h: j* y7 G; }             a(j,i) = -b(i,j);
) F( ]/ P1 n3 {          elseif C(i,j) > 0
5 `" I5 `% c8 T9 y2 {" i, d             a(i,j) = b(i,j);: D$ l2 E6 ], s& U
            a(j,i) = -b(i,j);
8 ~/ x9 l5 D7 x; L! H) \          end
: J: g. S6 y& u8 l$ ?( m       end6 Z& ]4 _5 L* x7 j& F7 D
end
3 w: p! o! K% z  h %使用ford算法求最短路，赋初值& l  E. M6 T* F" o1 ~
for i = 2:n
1 ]1 }- I+ O! b6 Z       p(i) = Inf;
  k) y1 L, u& ^8 Q$ u       s(i) = i;# `' Q( t+ w+ N
end
) F2 _' n. U8 F: A %求有向赋权图vs到vt的最短路,赋初值; g' ^; O' [9 u' O
for k = 1:n
+ }! J- G( W* p       pd = 1;# b& }" n1 N+ h8 m5 Q
      for i = 2:n
$ j2 c. j) j  q# B0 D; h5 R          for j = 1:n2 B% I3 Y( m* u
            if p(i) > p(j) + a(j,i)# F- I' n" P' U5 m) [
                  p(i) = p(j) + a(j,i);* \  I/ @& Q  V: m5 Y& D. o, t- P
                  s(i) = j;
1 t+ r9 R9 t  h) X                   pd = 0;2 ^- O0 s4 o) W* U  f% [& E
            end. _3 X3 ]" z1 A' i
         end
' f/ O+ O: C9 j& M       end
$ u8 h' L. f" }* @$ V       %求最短路的Ford算法结束
2 A# m7 c$ R! i9 \  n, }7 z0 `       if pd
2 c' L5 ]! a. }$ I0 c, v. t# X          break;
4 L+ @5 ?+ `" L5 `' d% y7 W       end' A7 u2 U' [% I) V# `# R
end  e3 K4 }" r3 P) Z8 g) @  ?
%不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n7 F6 r( [$ Z8 J
if p(n) == Inf
5 L0 n7 |: s% {/ u) w3 l' w       break;
# F4 y# \0 @/ G3 y5 {  Y end+ D3 d; f: ^! B+ L9 ^7 U
%进入调整过程,dvt表示调整量: F* ?, s! r" K3 @
dvt = Inf;2 _8 B7 a  R* K/ W4 |% q" A
dvtt = Inf;
  }- h& U2 c' c t = n;
, M  ]0 v  [) u+ Z0 d+ t' [* ~ while(1), p2 I9 w3 B$ H, w9 l4 d* Q
      if a(s(t),t) > 02 s8 i6 Q  p. s1 q6 d- P
         %前向弧调整量
3 d  M0 q# g3 Q: q* E/ m          dvtt = C(s(t),t)-f(s(t),t);8 |+ Y) F* L0 p3 y* G
         %后向弧调整量
8 ]+ a) `7 w; m9 g5 i/ k, _7 R       elseif a(s(t),t) < 0
1 c1 A; M$ z" j7 }4 O          dvtt = f(t,s(t));, o/ t6 T7 [+ w/ a4 ~5 t
      end
2 j6 i+ M. K8 l& m5 p4 f( z       if dvt > dvtt
0 c7 M, I8 |5 O' C          dvt = dvtt;( n1 A: p! n3 Q
      end5 n4 r- A8 _  q, G$ [; C. L% H
      %当t的标号为vs时，终止计算调整量
. X+ w4 b8 `1 b$ {& z( S$ x6 [* ?       if s(t) == 1# j2 H! l7 T6 L8 p
         break;
. \  m- s9 b2 {       end3 i" d4 q) H: i4 K
      %继续调整前一段弧上的流f  z/ s& n7 e$ E2 T4 f7 B8 ^7 J# R( `
      t = s(t);
% _3 P6 Q1 s* K4 d' Z2 [* j end
: p) p1 @8 z& t0 [8 |+ S+ ? pd = 0;
& w' G& }* y9 m0 [ %如果最大流量大于或等于预定的流量值
4 O  t' w, Q+ {* G: {9 Y) L6 e if wf + dvt >= wf0
0 A2 \- ?' r- V: J       dvt = wf0 - wf;
5 H: Q' W. t/ ?. N; q       pd = 1;0 p, s3 ~- I" t4 o9 P
end: ]5 L/ R2 g  F" g1 \0 W/ w
t = n;) f7 `1 h1 D" @4 @
%调整过程# D2 o- S( Q8 |& a- Y6 l7 n$ V
while(1)+ ?( H1 @4 i8 L% }
if a(s(t),t) > 0
' N4 m( N! B- z& \* c4 Q- I       %前向弧调整
$ x. F3 d2 y2 _' h5 u" _       f(s(t),t) = f(s(t),t) + dvt;
5 ]" P+ |" \# R: { elseif a(s(t),t) < 09 E9 c5 [: a/ R: K' m0 q% U
      %后向弧调整/ T" ~" `, |' G/ `# a, _: R
      f(t,s(t)) = f(t,s(t)) - dvt;3 M2 j, k* v$ I: @: T7 v
end / |  e$ G- G6 R% `. ~
%当t的标号为vs时，终止调整过程9 _3 O, z- \) v. _
if s(t) == 10 L* p$ J9 d5 R3 e" F: W+ z
      break;3 d! ?) j9 z3 D
end9 B4 O( {! y2 ~  k  \9 k6 H( |% J
t = s(t);
$ x! C# N4 K- _/ J$ c  \+ V end7 T0 d1 N; ?1 j6 _/ ~
%如果最大流量达到预定的流量值
# L: M# M' G/ ]! X if pd5 ~( U  V8 @/ Z% O$ j8 c1 C5 d
      break;
& C7 |/ \1 C. o' V8 y( \4 g end+ ]. @  n2 ?4 v- X2 W! {
%计算最大流量7 R$ c6 Y: l/ W
wf = 0;) [8 |& A  e! w4 ?7 e/ L
for j = 1:n5 h5 O! H( F* P* P. Y# M0 m
      wf = wf + f(1,j);
9 [! N2 h/ W" T5 }# i( C end2 }( f, J8 I/ i6 B/ Q4 v: R
end
* C+ \. ]( A) h" H& S$ i" w%计算最小费用! r' w  f" J  l; Z; `
zwf = 0;
7 z' t/ q- x& n+ J8 ufor i = 1:n
% D, z  Y! k3 G$ X& w5 |# f for j = 1:n  n, g" Z: z& T  K; P. e' \! G
      zwf = zwf + b(i,j)*f(i,j);# b: K& z/ s4 Z& l) z
end8 A3 \$ H  }4 c2 t7 z) _
end9 _) u& i7 ^3 d  X. ^" R' f
%最小费用最大流. G  G' z6 n0 i3 N
f
$ }+ j9 G/ D! F! o. {- N) c%最小费用最大流量
& ]0 T( F% a& B* o: G# e% Ewf
1 J  ~: k1 ^; i8 ]: a- ^3 B1 T%显示最小费用
3 T9 g/ j9 v9 M/ {0 s" Z6 E) {zwf
1 d  A# A- h- j- A' x1) g" y1 y- z- v! E# Q5 b3 n
23 z# k" }) j7 S0 `  y
3* a! u  Y7 i8 N- F
4
# _4 k! j; k0 J/ i: d* Q' i; ]6 X5. f% [' q& y3 ~
6  V3 E8 E& d! L6 x4 m
7
5 O$ f( q, [( s; @8- q5 W1 d6 T. v; E& w% F6 H
9/ A. O4 _" B% ~# B9 n2 m
109 F: _4 K4 y1 t+ G3 V
11
1 s- M% P/ I4 Z5 S12
8 }* w( F+ g8 A13
9 N8 Z  a/ c; K! m; n  I  |: d5 r14
) ?3 E( \- E% y# {" y3 D15
6 R1 d: g; R2 R* N16) O8 F: C. G) X' y5 a
172 W& r# k/ A2 N$ `! U* E# o% Y
18  J5 @' }$ r  w7 Q" s3 C- w
19) `2 k2 J% g; W: u  R9 ], o
20
5 a0 G" C8 _+ ?2 ~7 H# [+ X8 K21
, F: c0 t4 D- F' n22  w& N& o2 Y* E3 d/ Z/ t  M9 V+ \
23" U% b1 D- s9 ]* M; v" L2 s: p
24; ?' ?. t, }% x- R
25
# o& z1 M7 d" D0 Q5 @; @5 r$ E26
- d3 o2 P  d" ]. ^" _27
3 d7 k( C  I: E2 e% Y( a# d28
; P4 ?+ D' H4 u- d1 T7 J29
7 i4 W! u0 w, X) g0 ^$ m30$ q% Z/ _3 ]7 z# f; {! @8 H
31
- Y' t9 B& ?5 d$ N$ H8 z, n# y7 u32
+ F0 l+ }+ m2 b3 {8 s( `& S33
6 T) F$ ]# _5 g# C34
! Q! \2 e9 Z& ~& g5 _3 x35! {5 w! g. s4 }- R% ?3 {8 F3 Y
36$ E+ E' P3 D* l7 Y
37
) C6 |- O" |) L) b387 T  D" O, E- O! g2 n' C3 O" |2 p# n
39/ G6 ~4 L( B0 h: _+ j" u: |- J/ d- A
40
7 }/ ?1 ~" [* G* {: \, t417 h2 G. V3 x9 ^: t
42
8 k. @) y$ a2 B43; @; N" m5 M, _9 T; Y$ P0 X8 O
44
5 P9 s; i3 P- Q7 _% @4 S' C451 X- A3 Z0 j/ H0 M3 E+ G
46  s( \& p9 ~! m$ Q  _, F( O
475 _: k, s8 u9 ^% [1 z
48
8 a5 E( [; u0 K* y+ D" H49
* c4 }- i* p! r# @, K, s6 v& W50
6 M$ `; B1 o, z! R" w' v) w51/ h" x( H5 `' p! b. L, [& _
52
# I0 Z1 d" c" [* _: R6 m+ L: v53( v, R4 P1 y* V! N
543 m1 W1 h6 i+ }  @6 F
55
, Q* @  X! x/ T% K8 L56
/ U+ ^0 A5 A' k1 \  c57
7 w4 B1 ^( p6 J% j& D/ _( Q58
) R( r. r+ i- @$ D59% x+ t8 q& m! c, j1 @/ z7 Q+ \  B
60
7 W2 B/ @5 f( p1 ?, p+ M61# ~7 _: |0 u; H7 p
62; D' L* o% h) J+ X1 S
63' S7 U% }# U5 b3 g: j, u
64
, w0 U; P0 y* X: w! j, s5 a65. A) v- N$ [- \% t1 j
66
) ~+ {( z' Q+ U( \) q% K" m67
# U& x- j# S, K, @: E& \68
/ V$ k% O1 r% l69
& l) c+ K; N* I& U' r7 R6 a! f# `4 x70
( C5 u: f7 S5 z; d0 c+ w718 i& P6 n% R7 W  s( m/ q
72$ `0 K) L/ b) q8 S" z
73$ g* ~6 m1 `  O; l) I' `+ z
742 u/ ?! u, Q/ V2 R/ S* ^. e+ N
75
6 P) E8 g8 k4 T1 P& C, @! b76
% O4 H+ ~; P8 Y9 [  h! \77
% [: H) S7 y$ P0 I780 A' X; K9 C& v6 \
79
- r" `9 e7 j/ g: ?' ~9 q80
& m) u9 @6 i3 R6 {8 `2 X813 r' u4 O0 V8 C9 g) m
82
: L) i% ~1 F& l6 @. G' s8 G83) E7 B8 k+ z0 \; ^" L* s( f
84
3 l2 @1 ]/ p/ _  K9 W85
, d* V3 H5 d1 S: p# Z' n5 V2 |8 M9 I86
) f2 z, K" A9 ~87  j7 h1 x2 ?" U, y
88: f8 H0 t& i/ n8 |" s% ]
89
" i0 k1 |- ^1 S9 l% \) S90" c9 U6 r& m6 X, q: j# }$ }
91
  |5 E4 T( z3 t# R& W92
8 q, n1 a- x7 r, O+ U& p93# @2 l+ A& {8 [
947 j( ~( R, t/ h2 K. Y
959 w6 Z' y0 y! z7 P
96( ]) q! p" d- T0 G2 w, ]# Z9 s5 W
972 T+ C( ~/ @# U2 q, a; s' n
98& ^0 L/ `) W  ]3 v
995 A: E5 j! e7 ?/ c" c  O7 H
100+ F3 b3 w- G! I$ \
101
4 U* }: k- T) w4 w5 G- p9 e8 l102* m+ [2 j  }) Z6 U9 t# q/ R  F& C
103
) h& d: _7 o$ @! ~- H/ S104$ C" }# }2 G1 [; }, i  T. a; m
105
9 Y9 d1 G! H' I/ @& [1 u# _. _106
8 h) M+ f, L$ ~# d* K& ]6 d/ s107
% D7 ~) H  C1 x  |8 {# A108
# U' w9 D( @; g5 B1098 c" K0 n# `/ [7 M6 D: u
110
: y( G( Q: Y, W: G7 x4 V1 Y9 d111- K3 E  ~' V, v# e2 v+ E# W! m) n
1120 f: V1 U) c0 c6 C# F
1134 O7 {7 R$ x$ D8 s; M$ `3 B* f
114
, W0 c" o$ J" Q* \8 L0 M1151 i/ Z# C* a& Y6 _' Q& `7 y
116
  O3 E0 n5 e% |: O1173 h% Y$ A5 o' P" D
118
) x0 J; L) H/ V2 B' g119/ b" T' G+ M1 w+ f, H; P: l" y3 V
120
! A% D& ?1 n: J9 E. Q: y* {1212 [9 i4 |' ~2 }$ b7 w( U
122  \& u+ ~  x2 r; Z& j( `- A
1237 q6 R( F- m  B% S3 j) e" T5 v
1240 d4 C, b; u% V4 k" T& @* E9 K
125, y4 N; \7 H6 q2 X- r9 q
126+ \/ D; W* {3 {# y0 [, v! t. y1 x
127
0 B  b, R9 z( i( [) ?0 C128
& i4 K2 n6 T! d129
4 I. _1 t/ T: a, J+ d1302 c! e  ^! |# z  j9 M+ @; q: v
1313 k% |! u( a% y) h  N  H) m2 k
132! [' y: h/ g& i1 |
133, d2 c/ Z( G) e( d$ P6 R0 {3 @
134
7 ?/ f# Y3 l1 Z, J7 t4 l$ n0 q* b9 d135$ k; v, e* ~4 q, t+ J& W
136
" o# J4 F% }6 x$ w; H1374 Z. s6 c# c* {+ o3 P" t* E  Z4 G
138: m) t1 P0 P0 l: k6 W: L( z
139( g) @9 f- X* n5 t
140! U2 z  s9 o8 J* d3 C8 X
匹配问题：- w1 J8 |2 H; w2 T9 {
# E! B! S& m3 `# h
最大匹配：
4 o1 j8 O& U0 F; o) N+ D
5 Q+ \7 K3 i5 N8 ]
代码实现：

m = 5;
n = 5;
A = [0 1 1 0 0;1 1 0 1 1;0 1 1 0 0;0 1 1 0 0;0 0 0 1 1];
M(m,n) = 0;
for i = 1:m
for j = 1:n
%求初始匹配M
      if A(i,j)
         M(i,j) = 1;
         break;
      end
end
%仅含一条边的初始匹配M
if M(i,j)
      break;
end
end

while (1)
%记录X中点的标号和标记
for i = 1:m
      x(i) = 0;
end
%记录Y中点的标号和标记
for i = 1:n
      y(i) = 0;
end
%寻找X中M的所有非饱和点
for i = 1:m
      pd = 1;
      for j = 1:n
         if M(i,j)
            pd = 0;
         end
      end
      if pd
         x(i) = -n-1;
      end
end
pd = 0;
while(1)
      xi = 0;
      for i = 1:m
         if x(i) < 0
            xi = i;
            break;
            end
         end
         if(xi == 0)
            pd = 1;
            break;
         end
         x(xi) = x(xi)*(-1);
         k = 1;
         for j = 1:n
            if A(xi,j)&&y(j)==0
                  y(j) = xi;
                  yy(k) = j;
                  k = k + 1;
            end
         end
         if k > 1
            k = k - 1;
            for j = 1:k
                  pdd = 1;
                  for i = 1:m
                     if M(i,yy(j))
                        x(i) = -yy(j);
                        pdd = 0;
                        break;
                     end
                  end
                  if pdd
                     break;
                  end
            end
            if pdd
                  k = 1;
                  j = yy(j);
                  while(1)
                     P(k,2) = j;
                     P(k,1) = y(j);
                     j = abs(x(y(j)));
                     if j == n+1
                        break;
                     end
                     k = k+1;
                  end
                  for i = 1:k
                     if M(P(i,1),P(i,2))
                        M(P(i,1),P(i,2)) = 0;
                        else
                              M(P(i,1),P(i,2)) = 1;
                        end
                     end
                     break;
                  end
            end
         end
         if pd
            break;
         end
      end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
最佳匹配

代码实现：

n = 4;
A = [4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1];
M(n,n) = 0;
for i = 1:n
L(i,1) = 0;
L(i,2) = 0;
end
%初始化可行点标记L
for i = 1:n
for j = 1:n
      if L(i,1) < A(i,j)
         L(i,1) = A(i,j);
      end
end
end
%生成子图Gl
for i = 1:n
for j = 1:n
      if L(i,1) + L(j,2) == A(i,j)
         Gl(i,j) = 1;
         else
            Gl(i,j) = 0;
      end
end
end
%获得仅含Gl的一条边的初始匹配M
ii = 0;
jj = 0;
for i = 1:n
for j = 1:n
      if Gl(i,j)
         ii = i;
         jj = j;
         break;
      end
end
if(ii)
      break;
end
end
M(ii,jj) = 1;
for i = 1:n
S(i) = 0;
T(i) = 0;
NIS(i) = 0;
end

while (1)
for i = 1:n
      k = 1;
      for j = 1:n
         if M(i,j)
            k = 0;
            break;
         end
      end
      if k
         break;
      end
end
%获得最佳匹配M,算法终止
if k == 0
      break;
end

%S = {xi}
S(1) = i;
jss = 1;
jst = 0;
while(1)
jsn = 0;
%选择NL的值
for i = 1:jss
      for j = 1:n
         if Gl(S(i),j)
            jsn = jsn + 1;
            NIS(jsn) = j;
            for k = 1:jsn-1
                  if NIS(k) == j
                     jsn = jsn - 1;
                  end
            end
         end
      end
end
%判断NL(S) = T ?
if jsn == jst
      pd = 1;
      for j = 1:jsn
         if NIS(j) ~= T(j)
            pd = 0;
            break;
         end
      end
end
%如果NL(S) = T  计算al的值
if (jsn == jst) && pd
      al = Inf;
      for i = 1:jss
         for j = 1:n
            pd = 1;
            for k = 1:jst
                  if T(k) == j
                     pd = 0;
                     break;
                  end
            end
            if pd && (al > L(S(i),1) + L(j,2) - A(S(i),j))
                  al = L(S(i),1) + L(j,2) - A(S(i),j);
            end
         end
      end
      %调整可行点标记
      for i = 1:jss
         L(S(i),1) = L(S(i),1) - al;
      end
      %调整可行点标记
      for j = 1:jst
         L(T(j),2) = L(T(j),2) + al;
      end
      %生成子图Gl
      for i = 1:n
         for j = 1:n
            if L(i,1) + L(j,2) == A(i,j)
                  Gl(i,j) = 1;
                  else
                     Gl(i,j) = 0;
            end
                  M(i,j) = 0;
                  k = 0;
         end
      end
      %获得仅含Gl的一条边的初始匹配M
      ii = 0;
      jj = 0;
      for i = 1:n
         for j = 1:n
            if Gl(i,j)
                  ii = i;
                  jj = j;
                  break;
            end
         end
         if(ii)
            break;
         end
      end
      M(ii,jj) = 1;
      break;
      else
         for j = 1:jsn
            pd = 1;
            for k = 1:jst
                  if T(k) == NIS(j)
                     pd =0
                     break;
                  end
            end
            if pd
                  jj = j;
                  break;
            end
         end
         %判断y是否是M的饱和点
         pd = 0;
         for i = 1:n
            if M(i,NIS(jj))
                  pd = 1;
                  ii = i;
                  break;
            end
         end
         if pd
            jss = jss + 1;
            S(jss) = ii;
            jst = jst + 1;
            T(jst) = NIS(jj);
            else
                  for k = 1:jst
                     M(S(k),T(k)) = 1;
                     M(S(k+1),T(k)) = 0;
                  end
                  if jst == 0
                     k = 0;
                  end
                  M(S(k+1),NIS(jj)) = 1;
                  break;
            end
         end
      end
end
MaxZjpp = 0;
for i = 1:n
      for j = 1:n
         if M(i,j)
            MaxZjpp = MaxZjpp + A(i,j);
         end
      end
end
M
MaxZjpp

zan