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

最小费用求解
- p7 F% G8 C+ w1 T1 g1 |) ?
2 N1 |% q% D  CLingo:
8 E& \: m4 k" w& i! {# r7 n* \& Z
2 c- p, |! p' f+ Amodel:1 e! ?' {3 }' N0 \
sets:3 s/ ^$ B4 |. z& r
nodes/s,1,2,3,t/:d;6 K% d6 Y$ _' p9 G* }" w6 ?
arcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;* l& L# _) k) p. e' ?
endsets- z" ^4 ?- M  u! \
data:
+ V% F6 e3 s3 `* M8 J4 e+ {$ C: ?b = 4 1 6 1 2 3 2;
1 g$ i7 E' C0 I# T8 Dc = 10 8 2 7 5 10 4;
" K0 W% J" Y6 S% U: L( u+ td = 11 0 0 0 -11;. g$ \$ x3 n: X: k" o2 ?( A. i; w. @
enddata: B* X/ y8 m& V* x3 I7 x
n = @size(nodes);7 g% W0 o/ d/ ?
min = @sum(arcs:b*f);5 M& h9 y! ?4 c4 q/ y& `% `
@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));3 t" u3 A) y/ ]3 x. k  |2 \
@for(arcsbnd(0,f,c));
6 x/ C7 [* o9 u+ P( F1 W. B0 y9 Nend: ?! E: ~* G' Y* Y5 `: ]  z) I+ u7 x* l
13 h  _0 |4 T" ~+ T0 t' B6 o+ f
2- d2 k. l4 s/ y5 E( V- m  H
3
) Q/ Q% L% g! F2 u- u; A4 F  a4
' s% C( V8 \8 l8 @+ ^/ O0 R- \5! S/ n9 O$ K9 U5 Q
6
+ ]4 }1 u+ b- K/ F0 r7
" b. G9 C, C6 ]. {8
% L! y0 k) e% {( ~9
/ \" A8 P2 F) j" f+ i. \# }10
9 L# \4 K, m! b5 D11
1 q5 I5 a) W8 G0 J' _12
) P, V" U/ ^* V- j* F) P8 \# r; J. p13
# g* q$ Y* i, e- L14
$ E7 q* x, j2 i' l2 _: ^0 ]15; `5 q' t8 W7 v" T2 v
Matlab实现：
6 n3 O* W+ N: g8 P7 |3 b7 a( a& q+ k  j3 p% d, r" c3 q% T' G
- H- T! c. ]8 Y. a4 }5 x' W
n = 5;$ y0 b, W* O% U( V! |4 m
%弧容量6 O0 I, {. v: J* P1 c
a = zeros(5);
# x/ K" J5 |# p4 e# f4 Ea(1,[2 3]) = [10 8];& ~: \9 `# b* x- e: d
a(2,[4,5]) = [2 7];" {9 }2 q2 E/ Q  p( M# m! B
a(3,[2 4]) = [5 10];5 a" M- I# g, \4 ]# I" u
a(4,5) = 4;+ {$ u! U7 x- C! l) W  n; J6 a
C = a;" k1 ^# o% O: _- ?% e2 l( G: 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];
% W7 |& _. A$ {: J4 k; n6 ^' V%弧上单元的费用% E5 u- _0 M* A
a(1,[2 3]) = [4 1];
# p! n' x6 J, k" Ka(2,[4,5]) = [6 1];  {* p/ [4 v2 `$ n2 m
a(3,[2 4]) = [2 3];
/ e8 u  K% R+ f& W6 H+ Ka(4,5) = 2;
) m+ C8 t! C4 [; _/ Z2 Vb = a;
( A2 l& P: l4 k& Y7 T4 x0 p/ ]. g%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 v# n8 e, ^7 ^! q$ C
%wf表示最大流量。wf0表示预定的流量值
3 E" s9 `) f5 B8 U- zwf = 0;. n- t1 ]! H  H6 ]# @6 R
wf0 = Inf;
( t. }3 \1 r( f; Y3 @%取初始可行流f为零流2 ?  d- L+ I5 O8 T& C
for i = 1:n$ G5 L! t- o- X
for j = 1:n  G: w. S5 q6 i" V' }1 J: {
      f(i,j) = 0;3 g. ^: S" V4 S( o6 t) v$ U0 d2 u
end
$ x# M0 \! z; r/ Q% |7 vend
8 o) e: Q' b8 A7 [while (1)( q( ^0 X% `. a( ?( z
%构造有向赋权图
* a! p$ n0 G" W: a2 @2 y for i = 1:n
6 `7 q; z& W9 B9 ^4 M0 n. p       for j = 1:n4 V. }- g! w3 R, O  K# l3 v
         if j~=i
! r+ S' n# ]1 s; O5 d+ d             a(i,j) = Inf;
1 {$ ]( P8 z- ], V( e- g  ^7 X          end
! p. J" X9 \, @7 w* H+ k  v  X2 r       end
& b. e: s7 A+ l* V; e end+ l; Q" B; f" J' P! G! E, D
for i = 1:n5 u% l2 H% ~! R$ k8 s6 Z
      for j = 1:n
( W5 O- {; Y2 ]8 P! x          if C(i,j) > 0 && f(i,j) == 0% u+ K3 s) x; Z" _
            a(i,j) = b(i,j);3 R4 I% A" q# B" M
         elseif C(i,j) > 0 && f(i,j) == C(i,j)6 [" i) ^/ _+ u% S* d
            a(j,i) = -b(i,j);1 z3 r& c, }  s* h( f% u0 i# L5 p# M
         elseif C(i,j) > 0
6 A! W$ q2 @6 L+ \$ Q             a(i,j) = b(i,j);( ^0 u% h1 C4 c
            a(j,i) = -b(i,j);- t  P( x& d7 A8 p
         end( I1 L& U  u5 a3 o+ G0 K4 c+ N
      end
  @- f$ _7 F4 o  l: d end
( E# Z% B# [3 [6 f1 V8 b- o %使用ford算法求最短路，赋初值$ b* [8 f" V5 b4 Z- L: t9 K/ ^
for i = 2:n5 {! [: Z& \' p
      p(i) = Inf;3 ~% A1 I, \2 ?+ Z- G
      s(i) = i;
  \  h0 i3 Q6 }. @6 } end
, n* S+ H- s9 Y9 c) \5 z %求有向赋权图vs到vt的最短路,赋初值; P) s8 A- D' [# _
for k = 1:n
& j! m  R; U  \0 A5 V7 s+ ]       pd = 1;+ Z! n# z# v5 k8 \
      for i = 2:n
* G5 F6 t# ^, G0 ?- y1 j0 x! ~          for j = 1:n- `6 ^9 b  y; @! X
            if p(i) > p(j) + a(j,i)
$ V# Q8 P% ^: y4 L2 Q( u8 U                   p(i) = p(j) + a(j,i);
& `, @7 z( h# @8 `1 p  W, A$ i                   s(i) = j;  s. B7 M) e8 {% \- ~
                  pd = 0;# _3 g) s* G! P  {3 O
            end8 S( l- y& y+ `8 A0 A; w: D
         end/ V; ?  R$ ^) p1 E) D- N
      end
3 B; @" q; q- @4 a! @% e       %求最短路的Ford算法结束
4 y" I5 W! R8 G( U" Y       if pd
% A5 `* k* v* H/ F          break;2 E5 k+ l8 r" [* U! Z+ p: a
      end- R7 h' k; @7 U$ }& y7 ?' j+ J8 T
end  b0 S6 ^1 G0 P" q; t) N( T) V" ?
%不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n0 R% O5 K  p; t: @  ]* T
if p(n) == Inf8 O/ m6 d: c9 q. @" \
      break;
8 S( j9 _6 b1 r- G6 J' |' N end' N) ]* [- H( H- m, b" f* x
%进入调整过程,dvt表示调整量0 X) b  U. E$ e# \6 M2 E% |0 m8 {+ q
dvt = Inf;* q2 `" s. F# S9 m: }+ w8 R( M
dvtt = Inf;
& \2 W1 ]4 ^! E+ L t = n;* ^4 l8 O1 G8 F  J; r* j
while(1)
- x$ ?" i* W( T3 o       if a(s(t),t) > 0
, v/ e6 N, C+ a* {$ ?- o          %前向弧调整量2 \* c' V7 d' a
         dvtt = C(s(t),t)-f(s(t),t);0 p  }. W) h  H' l- p
         %后向弧调整量
5 i) F+ m, m3 X8 u/ T1 H. P" c$ v       elseif a(s(t),t) < 0/ v  h4 c5 O; @& ]" `' S
         dvtt = f(t,s(t));0 K* I6 v4 B1 D% X2 D8 p" U& M5 ^
      end
5 z- |& j! U/ U6 z( K% y       if dvt > dvtt) I6 {) i- n4 G
         dvt = dvtt;9 t, N1 J" T& k% ^' q, v. [1 j
      end
- j9 K. b3 y- r3 c+ b3 j# ~       %当t的标号为vs时，终止计算调整量
7 X$ t  v% t+ b) `4 H3 O8 `, V$ A       if s(t) == 1! F6 H8 z# `" g
         break;
7 d  U, z7 C! C6 P9 S1 S' _       end/ ]) S5 ?3 t- w
      %继续调整前一段弧上的流f+ w' U  J+ @! M, {
      t = s(t);2 P  ~8 a* W6 W2 j. m
end
- n' J4 `) E: _4 Z2 a+ p( I pd = 0;
" O1 A! }  z7 I" z9 l3 D %如果最大流量大于或等于预定的流量值4 H8 b% V, t+ w7 x6 o
if wf + dvt >= wf0
/ Y" G# s7 `& B7 k8 U- B; F4 X. R8 z       dvt = wf0 - wf;
: ^( y7 t7 ]6 X9 \$ z, Q; }       pd = 1;
. f3 |  O( |, J7 g* d; I end
8 m( _3 s# V% E2 c) U t = n;) B$ _! Y: O. ~% U. l2 i
%调整过程% J* R0 Y8 ^+ a1 B6 A: X
while(1)0 f, ^. p( G3 m4 o2 W" x
if a(s(t),t) > 0/ \3 D6 A$ L  `" H5 k/ C3 g" {7 l, i: D9 g
      %前向弧调整% I( Y+ X2 S6 C, Y. G2 c, H" v
      f(s(t),t) = f(s(t),t) + dvt; $ W% u8 w$ l3 ]3 u
elseif a(s(t),t) < 03 B8 x( w0 M. u# H- Z& m
      %后向弧调整
8 A  D/ q; t% a$ Q       f(t,s(t)) = f(t,s(t)) - dvt;
5 [) O. Y* q; {( \( Q  m5 g end 0 w9 Z, L  ?$ M4 ~/ y
%当t的标号为vs时，终止调整过程/ K& n- i9 u2 c
if s(t) == 18 `6 d, V3 K4 I: X
      break;0 g+ }5 k" r; D, z
end" G  G1 k8 p/ R2 g9 v
t = s(t);
4 `% j: i2 j; w' n- y# n9 Y end
2 U) H9 `" k3 K9 G, x/ B4 R9 \- k# t %如果最大流量达到预定的流量值3 y% B( H% A- e: \
if pd' ?; G, [& H8 v# P
      break;' d0 U3 [. _7 ]5 {+ D
end
& ?' l, L5 P* m* d. [9 c %计算最大流量* m* R* l' y1 p* n' |
wf = 0;( ^! O" \, u1 W/ n" N
for j = 1:n: I* P7 a, g  X# ^. Z: Z! f5 V
      wf = wf + f(1,j);
5 [- K' e0 P6 O5 C end
& U6 B0 H' L* _2 ?1 [end( R( I$ `, x8 C5 y% r
%计算最小费用
" }5 A' L8 q& N' w$ ]7 _zwf = 0;
' D; T6 Y( R8 k- b" Sfor i = 1:n
, B; i! k( b' x+ x+ C for j = 1:n/ M9 ^- l- w7 x( a
      zwf = zwf + b(i,j)*f(i,j);" V8 i( \/ f2 F
end- j6 j4 k9 w& n) q( u
end3 m/ E: ~  z" M
%最小费用最大流
5 z) h( m# T0 _; D( r) V) f. wf! ~7 @* q! H; o. t* u1 f+ W
%最小费用最大流量) q( i, V5 L- r, M+ W
wf+ h7 Z. a$ G7 T# J+ K# _, I
%显示最小费用. E, E6 [; ^5 @
zwf( l' k8 f/ z4 z8 I) O) w- |( {
1
8 a+ }. [8 I! y1 `" o2 q25 w& b3 H4 Q6 [3 X6 |4 x: j: j
3$ G9 K# m6 B3 j8 E0 j1 {* e
4
6 z2 K) B. [& m# ^* V9 \5
  F. {# ]9 n& c3 ^% u, K6; Y" S% g# u0 Q  l$ y- I6 ]
7& S; x6 q7 i1 r! r/ {9 N6 ~, \
8- h3 t5 {& i# [- z" p
9
  W3 ?6 c' h8 M* {1 I- a- V/ P10
9 b* G: L; Y- I+ o/ w5 y. X11
, Z6 l# K! d0 [$ \12
$ r5 D: E1 P* T; V: h  H134 I8 b& \- k' V$ ?$ Y  H4 Y
14. R! o! B% _/ |1 b
15' l# X5 f* u( q5 y! u2 {1 L. @: A6 q
168 Z% C: G0 E' N1 Y: }
17
$ H6 e% Y7 V2 S' B18
) T0 [* C" i! J6 \; m) I7 Z- i8 m7 j193 b; B' m' ~( R5 g& g8 ~$ V3 s
20: h8 k3 P' W% _  X! M& w
21* z, T9 F$ F3 V* U1 R: d5 ?* S
22
% H. x% N* \+ l+ ~/ Y  _$ _( S; l! O23) G0 A1 d/ N8 d! l5 s4 B
24
0 W, Z5 `( T1 @0 m, s, k; {3 n8 f25
$ `3 Z/ d, N  m1 k% e3 d26
7 l" F7 O* P+ d. g7 L: ^: J8 G27# G" P" Q* x" t! O& x1 n
28( @1 I$ x5 m5 ^8 \$ Z
29) Q9 ]# I- J- T9 I& d) x# ]0 g$ X
303 X/ z" D* Y. V8 C0 T2 V$ R! M
31
9 Z8 S' Q7 i& B1 c2 H7 ^32
3 `" h5 h' ]- H% ?  @33
; e$ _8 g5 e  u: k# t34
1 {1 p+ H$ n1 I( N5 l* F" R35% g1 N) Y$ f* v* k9 m1 ^! Y
36
. b, Z5 ^  ~2 E! D' R, F37" k5 Q8 G3 q7 Z9 o' e- ~
38
9 ^' Q  Y% w! g1 x  `8 b+ b+ W1 W39
! ^+ d) s' w; T* A- T: d40( ^$ p  {# _3 {$ `2 l' H5 ~8 M* W
41
( M5 e% j) n' ^( j+ T5 u42
2 L7 L0 a) G! y4 @" D4 M43
$ g5 o. m1 D' m( B( u; q44
' P! k9 i9 A9 S) \9 D45! x. Y$ I8 s, X9 g; ^
46
/ u$ g1 f/ f5 W9 r7 \" r( v( e47
3 f- t: T" |+ ~( Q48' T( k' K" s! [$ Q5 h: q  q" k* G
49
/ M4 |. T$ |- t* \1 r! @50
0 s7 k- C9 @! F! C( g51* u; |$ N% q. H( r' ?8 @; B
524 [! l! R5 x" ?% U$ z/ V7 p
534 X4 R/ [4 w0 w. W7 e
54' U9 Z: O3 u1 o8 s' Z
55# Q7 ]+ U1 E5 m) M% {7 k% D7 D& q/ S
56
% U* m2 {, r0 s& V# j577 @- L5 R# j  @
58
* X- Q9 f/ s$ R3 K0 N2 M: F0 a59$ e1 N0 V$ S9 E$ C
608 z. m% w/ L2 B3 `2 m& u
61; M9 T4 R$ c, p/ I
62( K1 d! x9 Z) X2 Q
631 W% K5 |8 K' W; u& E3 z
64
/ G, y) }5 }6 v3 C65
' x' y: B* D/ N667 |% |& [* x) \6 V& k" ?; w) J
67
# {; L& I1 _  R) S1 }9 O68
) G% u6 Z+ t+ ~4 G. u69
2 C( Q* u: Z6 L: s705 S" w, E3 d5 \/ n
71
; F0 z: i! |! w9 Y72" s/ x5 m+ s0 A2 E) O# R& g
73
! U. Z4 y1 o: Y6 L5 b0 r' ?( d0 ?747 p' X: c5 o2 k  S" W0 Q4 [
75
) ~  `9 @2 \! a) j763 e' b3 A! _% `6 q
77
. ~% F0 W9 n. k" q- _5 l781 N  k; e  O& M
79# V. z/ r# N1 u/ A, b+ L
80
0 ~  ?- \) h: r& I5 i, Q& T- J2 v812 d- p2 U  r% F$ y1 P3 A+ q) X5 H
82
! _7 J9 w* l2 J; Y+ m) e83
' c0 R& n' z& C) ^84
- V6 {7 T/ |, K6 m( V85
% r* \4 T3 f/ y1 X1 u: F: o* K86: t6 I$ A4 l2 H( P: i3 X
87
0 \  P* }: k" k7 D+ b88
/ k  G* X; y1 K. ?89- F* p. V' d4 E
90) z, Z* u) D! l* B  o- N- P
91
  d. l% Y3 O' q/ k6 E& y! U9 f! v92
+ J4 J$ v' z3 g& N. B7 g93
. d* V7 D, Z( Z) n94
# H! ^3 A  p& L* a2 ^, |95# m7 K. o6 d: p; c! I
96
# B# H6 {1 g  s5 U$ e8 V' q97
! f: \2 K, F* A' g. _98
4 L5 X( b5 K: P4 j( Y99
! H7 s5 C6 [, S* `% H! T% W100+ U  ^# O4 I" q3 M& p, C
101
8 M  t) m: q2 s) t3 e3 r, L102  [5 o1 v+ l! S* A- k5 J- \
103+ H  c# N7 ^7 J" J
104
% c8 @" C0 {4 k+ b9 P: w105
  l: p6 Q! O5 d  I106/ f" R! D+ f5 M2 V+ n
1078 x: Z4 {# a: Y7 b6 C6 o7 ?- g( w
108) i) |* @4 H* I) Y
109
. u! `+ m& S, A  K' A& u9 {110
) Q; z: z6 K1 H# ]5 ~5 X111
" A* _* w0 M$ W! p8 V112
: a* s! r% U# A5 b% x1139 r& W1 Y! U) m3 t' k0 {7 k
114
6 L& Z$ P" Q* {1157 U* A  d# ~6 U' K8 `! f: n
116
0 u% V' t8 j8 ~, ?1179 ?8 v  l2 }" f0 Y3 R
118  Z8 m( L+ O; }3 B0 a; U& B
119& s+ C: {( ~3 A) n; T2 C8 G
120
) ~- ]0 J& H5 e1210 X  W# z2 {4 [, T/ o1 c; _
122
) C+ J! s/ h( ?( p& w  e( F123' @9 j: E( \* `8 l
124" C" a: U9 g! z/ g" [# g
125
2 z% L, o9 x7 V7 T126( F6 \9 k9 y4 H4 z0 w
1274 d$ r: E' {, Q2 Z, J
128
: A0 i: I9 c- z4 E129
  U+ n( Z/ M! ?) t3 ^8 |130
% z* D) z  N2 p1 P- Y131
( P, s+ y9 {, N! D5 F' d132
) y, L+ O" q" Z* H) L$ m1 V133. U  b$ I( p+ G  J, }$ S# P. K* q
134) b* F: Z  z$ d# r  B5 t# o: L! `
1350 e; P/ x! y& o; f/ a
136  g- v. q! k& n* X5 [
137
% h2 E/ ~8 _$ {- j; t  h+ J1 T138
& U9 A4 [, ?0 d9 @# B) M# G139
$ w3 g0 I9 @* B/ @140
+ Y. h( D8 @* n匹配问题：
8 w7 K) S. R% c: c6 _  i" p) Q! P  o4 @! B* i! L& e
最大匹配：
8 u- c5 z8 t# }+ t& i, R) p
7 m3 k5 D* C0 p! l
代码实现：

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