查看: 2465|回复: 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代码：

最小费用求解! q# R$ \7 e- w1 J( z# e) \  W
0 R" e$ ^7 R2 @' v& p8 x6 V% z
Lingo:) t1 P' q2 Z3 |% R" Z

1 K8 a% I( V/ j4 S" F3 D! I9 Dmodel:
5 i( V& X5 `# B: Dsets:7 Q) V% R' l  D
nodes/s,1,2,3,t/:d;
5 }0 S/ I) B# m  }$ ~0 Q$ narcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
& f4 Y# m6 k; \8 X5 u9 {endsets: }& F$ |; S2 @$ B3 N* P  f- \5 I
data:
+ V+ ]  v0 @9 E& ?& ?+ xb = 4 1 6 1 2 3 2;4 ~# x" V+ @* w, j  y9 x
c = 10 8 2 7 5 10 4;. C3 S$ |7 a$ A7 t
d = 11 0 0 0 -11;; K! x1 x3 e7 O
enddata- _3 a! K  c2 }" i' P
n = @size(nodes);! P; l. K. A8 |, U' L6 Q
min = @sum(arcs:b*f);) N9 f" u& @# |$ \
@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));; u% K8 y2 L- ?2 f6 Y" a
@for(arcsbnd(0,f,c));
- ~) W2 E( H- x. F* P5 O- @  }- ]end
: _. I) X* {, p2 m/ ]+ i1% o) E# y' V2 X0 `% D- Y# u) c7 E
2
5 o- q  R: s5 z3
  w, d( N4 I5 L5 O- ~+ Q' ?4 y4
; n* L, l' F8 |5! E, t; f4 v/ x, D2 J8 ?
6* A4 N# r. \9 _/ i4 i: ~! n
7) p& \/ N! r: \& [
8
% [2 V% O9 y9 ]5 K: k7 w9
) S' x* u+ W3 j2 v: ]7 H$ o107 X- X7 Q5 O4 U3 O
11
3 e( |0 h7 P% t# b4 `9 }2 K7 ?12: J' ~( u1 S  Y/ ?% U
13
6 E( b9 i6 B4 j14
& Y! p7 U' X! ^9 Z8 ^1 t- I15, D! o3 h  |3 @# e3 q
Matlab实现：1 P9 c0 d+ X' \+ I9 T* C/ b
- m+ ]! J" T" r% Z! R5 _0 t- a$ f
0 Y! K, ^1 v" H" R. i. v
n = 5;' r1 M( f3 n, G% u0 p. e
%弧容量5 F3 A1 X1 }$ s  M8 k
a = zeros(5);
3 k" i0 R* }* e" Ca(1,[2 3]) = [10 8];$ @% W4 I( O6 H$ [! Q( m" d6 E
a(2,[4,5]) = [2 7];) P- V( O* c7 \+ r1 H" ?
a(3,[2 4]) = [5 10];
7 h1 E/ C& t4 y4 W$ V. z& a4 Sa(4,5) = 4;  c+ ~5 g3 I: g5 Q
C = a;$ n, o) G. U* c0 r
%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];5 p/ b8 ~) w! _/ |) D9 O8 \
%弧上单元的费用
. e4 j8 t3 {) ?# ka(1,[2 3]) = [4 1];
% D5 Y4 e2 h! d( ra(2,[4,5]) = [6 1];. }; c( ?8 {+ d) c9 z+ j, @
a(3,[2 4]) = [2 3];
, _; l6 O/ {& qa(4,5) = 2;
+ m/ @: P7 W* B! L5 s# I- e3 ~' w* {9 mb = a;
$ W. ^# s" z7 U( |3 A+ K$ |%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];
# C4 P- o7 L* _%wf表示最大流量。wf0表示预定的流量值9 T3 j( S& f3 `& \5 ]9 ^2 C) x
wf = 0;
& P7 m( m9 E# s0 G1 F7 q6 Fwf0 = Inf;. s0 B3 p8 `4 x4 v
%取初始可行流f为零流8 Q9 a6 R, Q6 P' u5 @7 |
for i = 1:n# ~2 Z7 R2 d7 u: y$ s
for j = 1:n
, k- v6 i  F0 L8 n2 g0 [7 |       f(i,j) = 0;. L9 p" I3 I0 f% s: E
end+ j3 e, i: ]' ^' K
end# ^; x" q( n9 L5 P3 C+ ^- U, g& o$ D
while (1)
4 d7 \" {& n5 Q% D, Q, e- [3 o$ v %构造有向赋权图3 R3 h/ g& E8 J* j, G$ R. p
for i = 1:n( n4 e( R6 y3 ^# \/ K2 F
      for j = 1:n9 a* l& b' T! K8 B# E+ W- i8 Q
         if j~=i9 h# k3 B! h/ b8 r. z! Y; o: e. S
            a(i,j) = Inf;
/ P% n% ~8 _9 r0 O4 y/ q* p          end4 \4 I. J$ ^9 f) Z/ ~# \. V
      end) y. k- ]7 W4 D) a( F0 D; V! j
end
' G2 ^; X# n8 }+ [7 w, P1 q for i = 1:n
5 D) w; N; p: m7 f, U       for j = 1:n- \& S8 H2 T( J9 k# V
         if C(i,j) > 0 && f(i,j) == 0, E# [- g) x) x2 z4 V, I
            a(i,j) = b(i,j);
8 Y% `3 X! L8 r2 U( k% }' f( z% |          elseif C(i,j) > 0 && f(i,j) == C(i,j)+ S0 s  X2 r: [) X8 {
            a(j,i) = -b(i,j);
0 e4 Y. s8 j: l8 O0 R: n4 u          elseif C(i,j) > 0  N- B4 _9 x6 t) |1 N3 Q+ \
            a(i,j) = b(i,j);, o0 |. H0 G' a. t: f6 q# X
            a(j,i) = -b(i,j);
7 m7 k( F4 ^& c' L  p/ x) U# Q          end
& R/ ?# v+ `! n7 l3 }1 F* W5 L       end
6 f5 ]  r# ^! _8 n! n5 o- u& G7 p end8 K% G8 q- @1 m
%使用ford算法求最短路，赋初值
( Y: ~+ Y' C9 Z! m for i = 2:n
. n4 w5 A, \* t2 Z& a5 k$ n       p(i) = Inf;1 b1 f9 v4 O4 t; D7 C3 d) u
      s(i) = i;7 J, \3 _6 G3 a- X% e3 n' r# V* {% ~
end
  y# C5 ?  E# w# c# N9 j %求有向赋权图vs到vt的最短路,赋初值
+ G. X3 B; X: z; ]; @2 w& A for k = 1:n  u: `: f: t& y
      pd = 1;4 E9 l) e9 i: J; q* P# a
      for i = 2:n
' G  V' f& [/ l) w- Y          for j = 1:n
& \$ g2 b- y9 {0 x+ M             if p(i) > p(j) + a(j,i)
5 ?* p& ]! {2 g" f( |! U; Y                   p(i) = p(j) + a(j,i);% |9 ~# n. o% v3 g
                  s(i) = j;
5 s4 N2 H8 B5 D. k5 s                   pd = 0;
. b+ L; s& n4 R$ |& H/ n' u3 @( o             end
5 H, s, ]/ ?$ Z* y, l4 W9 k          end; f) y" r+ u7 E% q( i
      end9 r* t9 N6 M. p0 k) F! d
      %求最短路的Ford算法结束/ [1 J7 z% ]' y( _- w7 d' c9 t' u1 i
      if pd3 L2 q' {& K+ l* F3 i8 Q6 d
         break;
0 d" ^, W: C4 B% }$ f# }+ }       end
, B! }# l" c1 u  Q, \5 Z end) F; Y8 e: ]% U
%不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
: j: k* W7 K7 f$ ~ if p(n) == Inf
% ]0 W& y" n) ~" d+ o) V6 V7 i       break;
' X! l7 ?- g" ~7 Q' \ end
6 R1 u8 w. t& W4 ~: k$ n/ s %进入调整过程,dvt表示调整量
  v; E9 b2 }0 k dvt = Inf;+ l5 T( g% X$ m- \" H2 N. q
dvtt = Inf;
8 E# |0 ~& ?4 u. A t = n;
! Z  E. b# b6 ?0 [: I- K( O while(1)9 i) e+ ]5 p; F6 q, s  T; A6 a) n
      if a(s(t),t) > 0
6 V. M" ]$ t% t1 n9 j# X; s          %前向弧调整量% d* n2 G" W- j# s: @
         dvtt = C(s(t),t)-f(s(t),t);
3 V' g' f2 o2 U( S          %后向弧调整量
* p( U" F/ A4 B9 {5 Y       elseif a(s(t),t) < 0
. R6 G5 L, x; s+ j5 d. z2 r          dvtt = f(t,s(t));
0 g, {: |5 V9 j6 s/ V. N       end
% n# ]+ s3 y1 L* i3 i       if dvt > dvtt
% T3 J  t& q3 Q0 d8 _          dvt = dvtt;
- E0 [$ `+ p6 n; }& z* m       end' d. @: g, I( T% \3 ]
      %当t的标号为vs时，终止计算调整量8 j5 f/ f' m$ z2 z( M
      if s(t) == 1
) m. m- Q3 g4 `. O& {9 Y# ~          break;
( J1 ~: S+ K9 S, [6 {5 R1 b3 ~       end) x1 g% O. N4 E/ Y2 W# i
      %继续调整前一段弧上的流f- T3 i. I: ?1 i/ n: `1 {; L
      t = s(t);
9 G7 u1 Y* W  U3 t end
& f: v7 t) D& p9 w; U9 Y" Z pd = 0;
6 ?* R  J$ L; T2 Y/ k %如果最大流量大于或等于预定的流量值
* O! Z, V1 ]+ v! _; `3 o% ^ if wf + dvt >= wf0
$ F+ j  Q( o( X2 v5 P: p3 \       dvt = wf0 - wf;
3 D' Y- z; \6 j       pd = 1;
; s9 I# ?7 q6 {# Q4 i+ B6 G end' D! v, O& Y$ A
t = n;7 W: n! q" d- V5 |8 X+ V
%调整过程* y8 W. P% e* G$ r
while(1)
0 K$ b6 c# w4 Z# ~, |; ^$ u if a(s(t),t) > 01 I1 |- w6 S' C4 a# E5 t
      %前向弧调整7 B% k0 G* p0 a/ N$ ~
      f(s(t),t) = f(s(t),t) + dvt;
( ~+ {0 O7 G, Y+ f3 T2 s+ S" o7 x elseif a(s(t),t) < 0  B) x9 R+ u  E! b( I) Y( C  `
      %后向弧调整6 @9 I7 Z( b% R; t; k! D" w
      f(t,s(t)) = f(t,s(t)) - dvt;
* \, m! z7 d8 k" A9 e. o end # K$ X- M* j- a! d' d  @% B
%当t的标号为vs时，终止调整过程
* l2 @! z( j! a$ V8 N4 s1 W if s(t) == 1+ \$ ^# [, w2 |, `- V
      break;( W5 v/ O6 X, V" Y7 {# U6 D
end1 M# Y) I1 n  x& ?$ V/ S& |
t = s(t);
. U. {0 v* z; F5 @, ~2 v  d end
- q8 c& R4 W# K, v6 J %如果最大流量达到预定的流量值
) N9 {( |# F; w7 x if pd8 \; S* `0 ^( U( b& E1 F* q
      break;# [6 j' v4 U: z( T- ^& M7 X
end
/ p0 e$ ^8 e( v %计算最大流量
2 }1 X4 F$ R( B4 u9 e wf = 0;& h2 x3 V% Y" \* d$ h0 U0 V
for j = 1:n# P9 r& ~$ C3 l4 \7 d
      wf = wf + f(1,j);4 s1 G5 ]8 t. b! j
end$ b' y" h# q( n0 C' b
end+ `: A  A' @2 `6 f
%计算最小费用3 x- U' `; }. ]: G( g
zwf = 0;4 h) F3 u! j+ g4 `1 ?9 z
for i = 1:n1 z: j( [  q* {
for j = 1:n
% ^7 b( v/ R0 x$ g: b       zwf = zwf + b(i,j)*f(i,j);
9 t+ g  \! z. E/ T! ^$ U end* ^5 K* ^2 U- v1 T
end
' ~2 N2 V, {- U& z) Q) B%最小费用最大流+ C+ T# H( q* t8 f
f
/ A3 g. [  A" @( U, t%最小费用最大流量
; ^8 j+ Y+ }4 D  |+ Gwf
6 B+ a! P5 Q1 R# n1 k%显示最小费用
( J% D8 q* r& I# M' Dzwf9 w/ K( [8 C5 _/ [! U* D0 G
1
0 v6 e, ]- A# v7 F" Y, p3 x2
( ~# [/ p' p9 W# c! K  r3
" m* B; ^; {0 w2 Y& b: X4) R( A" h5 d1 ^8 ~4 Q, e1 P) b" i
5
5 v+ I. K- D' T0 I4 Q' y68 d) X4 g5 m- L! G
7
' t& ~. o+ E9 ~1 j& [+ r3 f8" e- p" a# i9 p4 l* ~/ w6 n8 m
97 J6 k4 N  P7 w
107 b% X8 M0 ~# E5 `
114 V" L8 q. Z7 J
12
8 y; o) p0 R9 R3 S9 n" s4 u* _2 n13
( v, L5 h1 l7 H5 R, r14" H8 C7 z- l# \: ]1 e, _. G
15: Q5 ^! P6 G3 a  L2 {, l. f
16
6 x; h8 {+ b: H& ^6 @0 ?6 a/ }179 R. o* J' c5 }  J( {1 d! U9 n% A  B
18
  m* J0 A6 e6 A19
- P/ h( Y; Z& D  ?- B, m' Q- y20
$ V& v6 J" y$ [21
' B  k, Q, M* f5 m3 O22
+ s- u3 l1 u9 Y5 _23
$ q0 @; I" o" m# h7 Y249 _0 k$ R% ~% e+ A4 Q  v) P2 p! Z8 V* w
25
* R1 p* O/ K: X/ u26
  F; g* o; S) v7 `5 E' ]' ^% ^27
# f9 B% g/ ^1 T6 a2 ~6 }" l& D) ^& c28
0 r) q( M; J2 a1 ?* G$ C3 d# ~298 o  x2 ]! l/ O; P  n
30
4 ^) r, S2 X, Q3 T31" i3 {' _  `# T" ~4 |) b
32
) @1 s6 X" X0 Y" x33) k  E+ V$ I. x
34
- H$ v( q! C$ s35
& @4 ]- G" B1 M: P( o, u# H7 H  C36% \, V; b; ]; U; y+ |. `
374 ^, P9 n. _2 W) D  I
38- s  O" Z1 t6 h3 W
39
. M9 R# t. F3 y" }- v+ o40/ `+ u' p/ }; Z' U2 D! Q( ~1 u9 N
412 H- g$ I) O" u: l6 N3 [3 k6 T
42
' y6 {1 c( q- S6 k436 i. {8 [; _+ R3 Y4 O3 @; \
44
$ j" e: ?% A0 ~45
: E/ _% S6 a# j. Z9 D0 U46: S& m5 C( j! r. h6 V. B
47
7 q6 Q' i  f4 n6 B4 z48. o/ O6 v" P% B- ^+ B
49
3 `3 J; S/ l9 T- R! g, ~# g3 H+ }$ e% B50
' p. K5 |/ u/ E) e  w0 a" k51
0 K' s' [1 T, c/ ~. H! \: m52# ]0 F' a! W5 ^! e5 t) \3 ~
538 y% w# H0 }# Y8 s$ T1 J: V
54
  h* v# A5 N( m) o8 J55
5 r. o  H+ @6 D1 A1 Q& J7 @56
5 ?  |4 l/ c; A3 `; A57
7 Q: q: m3 N' e- N' j583 y- H9 f3 E0 S9 k* M4 X
59# C: k7 R" b. @3 N0 y
600 e, a! {! C, h5 h
61
& a' C, \' ?) [4 f, J0 ]62
, G$ L7 w% @! O6 T) R5 M63
6 E/ u* O/ P! Q64& r( H9 W' R5 J8 D, J1 R2 J% l' j
65
8 `) @0 g! e2 H# t$ P66
, A1 F0 n. h# k# N- _; @675 c7 W  [0 f5 S$ ~% G/ O/ s
682 R8 d" p4 G* c
69) H, P( D# A: S
70
% d6 v# ?7 s! r. l# h% B71
- g3 D% X, g. G) v72
3 {# z' Y, m5 L4 P73
! Z$ B$ h3 ^$ B74
, w5 I$ j2 G: u75
- {1 ?7 }/ I0 `' X! u) z- t76
0 Y7 M+ [4 ]$ u# V770 O% Z7 S+ i. ]# h' Y
78
# B$ H% i3 ?3 m79
! F. d4 R+ T7 K  F7 ?. a) X5 ]1 H802 `  C! Z2 Y" O5 s
81
  }$ d2 |0 A1 A7 M7 j7 w82% e- ~) K6 a! c# w1 `7 D( [4 a
83
1 Z0 `' ?' O' q6 v, X& O" U84
' M9 Y! P; i7 z% t85, w1 w1 {& C" \; E8 q; I- W
86
* S5 E( N5 L6 f/ n; \9 s- w87
; z1 L# R4 m' g) O6 I! M1 Q3 f88
$ v& U4 [7 M/ ]" C$ r89
+ B, }& Q; |! Q% n0 V90
, l/ U6 |) O% O" r1 ^4 F& S91
% G: F7 p5 e! }5 F( G: N92
7 b# L0 I, x  T; n7 r. F93$ K% E9 c3 n! I' x/ y1 A
94
/ v9 Z- M, o2 V0 Y95, X6 U7 m/ G8 E
96
6 D- }% r" L; I& D' g) ]97: s. j: u8 Q# q+ D1 ~$ Z) z
98: y- E0 \0 ^! C( K
99
6 b7 ?4 R- s3 L9 L% S+ q+ ~100, ~* f; }- i$ {. j. c0 c& [3 C
101/ S( s4 D) ], f- k
102
) }# n3 e  F; w# Y( l& B103% t. ?+ q5 I8 d' o% Q
104' n0 e5 e+ E% R4 p  U3 c3 A
105
+ h7 b* k  y+ ]: X3 s106
) {) F& ~: y- c3 o: ~: A9 n107/ k/ Q, k, K5 Q" \: J! `
108
- }7 Q8 m+ A1 J7 E4 a3 O# k, o109
4 g8 x3 o% V5 ^. z+ c: V110
' h7 I5 h$ L  i5 Y111
$ _$ v* R& y1 A  U1121 W; M( c0 v4 R0 Y9 k
113
# x0 y2 K2 B9 r; u; m& m+ z114
: h# P9 f1 u, [1150 S8 G# A( }$ f3 q
116
6 h) U1 }  e7 D  r117
- Z. `4 t" N1 Q2 z( h2 C/ t118
* R# U- j  S! ^1194 i( R3 V7 Q7 S
1202 Z' J% l7 }$ F2 t+ [1 Q: h- x
121
/ ]$ v' I$ ]3 X, `# L- n8 Q6 [122
" i. @% O- N, {. G9 G123
6 T! D" O# d! K124
1 d  h! I4 ]0 f7 K; l125
; P, K+ n& _$ b0 _0 `126+ V" s7 U/ Q; `% ]. \
127$ _1 i5 w8 Q: P3 x. e
128
' r  P+ T6 j8 s- Q5 x/ e+ p129
% q* L$ g+ `1 y# h1309 F2 ^) g1 T) X& z' _
131
3 @+ l% z, e( `: {. Y' _132
! q1 v5 a5 ~: V) Z) Z& Q2 q( g1332 k3 ^! P  t4 S1 S: F1 L# {
134
* K5 H# U: S& j9 F2 Q/ r7 a+ f135
6 m! Z2 ?( d, V2 V8 s136
5 ]( U. P" T0 M6 K8 g137
; |* r/ o5 S, N' {1 c138' @9 a- a. o: t5 M9 b
139% H% a8 d2 F5 @/ X$ b0 ^# }
1405 R$ T4 H6 v- U+ x9 ]( C( t
匹配问题：8 a  g' R4 S8 L2 T

, D. U( ~+ ~- }* N3 y. _4 R! C) u- ^最大匹配：& r, M3 J" R0 U# ^1 S8 \% D+ @: @
2 }( I2 W8 h+ _* Y+ p2 }

代码实现：

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