Ầ
Ụ Ụ
PH N PH L C Ph l c 2 ụ ụ
Bài toán lu ng c c đ i ự ạ ồ
ạ ị ồ
ạ ồ
ấ ụ ề ứ ự ạ ấ
ầ ườ
i gi
ườ
ồ ị ươ ụ ớ
ườ ứ ố
ọ ầ ể ố
ẫ ở ầ ả ồ ị ố
ươ tàu ch d u vào b ch a.
Cho m ng G=(V,E). Hãy tìm lu ng f* trong m ng v i giá tr lu ng val(f*) là ồ ớ l n nh t. Lu ng nh v y ta s g i là lu ng c c đ i trong m ng ạ . ồ ấ ư ậ ẽ ọ ớ . Ch ng Bài toán nh v y có th xu t hi n trong r t nhi u ng d ng th c t ẳ ự ế ệ ư ậ ể ộ ả ng đ l n nh t c a dòng v n t i gi a hai nút c a m t b n h n khi c n xác đ nh c ủ ữ ậ ả ấ ủ ị ạ ộ ớ i c a bài toán lu ng c c đ i s ch cho ta các đ giao thông. Trong thí d này l ồ ụ ự ạ ẽ ỉ ả ủ ồ ờ ng ng c a dòng giao ng xe đông nh t và chúng t o thành ch h p t đo n đ ỗ ẹ ươ ủ ạ ấ ứ ạ ộ ng ng v i m t thông xét theo hai nút đã ch n. M t thí d khác là n u xét đ th t ứ ế ộ ng ng v i các cung, đi m phát h th ng đ ng ng d n d u, trong đó các ng t ể ươ ệ ố ố ớ có th coi là tàu ch d u, đi m thu là b ch a, còn các đi m n i gi a các ng là các ố ể ữ ể ứ ể t di n các ng. ng ng v i ti nút c a đ th , kh năng thông qua c a các cung t ệ ớ ế ứ ủ C n ph i tìm lu ng d u l n nh t có th b m d u t ầ ừ ể ứ ở ầ ả ng: Đ nh lý: ủ ể ơ ng đ ấ i đây là t ầ ị ươ
ồ Các m nh đ d ệ ồ ươ ạ
ồ
ầ ớ ề ướ (i) f là lu ng c c đ i trong m ng. ự ạ (ii) Không tìm đ (iii) Val(f)=c(X,X*) v i m t lát c t (X,X*) nào đó. ng tăng lu ng f. ắ ộ
ủ ậ ạ ắ ọ ỉ c đ ượ ườ ớ ộ
(Ta g i lát c t (X,X*) là m t cách phân ho ch t p đ nh V c a m ng ra thành hai t p ậ ạ X và X*=V\X, trong đó s˛ X và t ˛
ơ ở ể
ặ ằ 0 (ta s g i X*.) ự ấ ả
t c các cung b ng c l p sau đây cho đ n khi thu đ ồ ế lu ng trên t ắ ầ ừ ồ i b ặ ạ ướ ặ ự ạ Đ nh lý trên là c s đ xây d ng thu t toán l p sau đây đ tìm lu ng c c đ i ồ ậ ị ể ẽ ọ lu ng nh v y ư ậ ồ ạ ố ớ c lu ng mà đ i v i ượ ồ
ườ
ng tăng P đ i v i lu ng hi n có, ố ớ ườ ệ ồ
ườ
ng P. ự ạ ắ ẹ ể ấ
c mô t trong m ng: B t đ u t là lu ng không), và l p l ng tăng: nó không còn đ c l p tăng lu ng B ồ (Ford – Fulkerson): Tìm đ tăng lu ng d c theo đ ọ ồ ị trong ả ủ ụ trong th t c ủ ụ ả ượ ệ ậ
ướ ặ ồ Khi đã có lu ng c c đ i, lát c t h p nh t có th tìm theo th t c mô t vi c ch ng minh đ nh lý trên. Thu t toán Ford-Fulkerson đ ứ sau đây: Procedure Luongcucdai; Begin
ng tăng lu ng P> then ồ
If < Tìm đ < Tăng lu ng d c theo P> Stop := false; While not Stop do ườ ồ
ọ Else Stop := true; End;
158
Đ tìm đ ồ ậ ế ể ườ
ề
ị ậ ề
ạ ắ ầ ừ ồ ế ồ ị ồ
i bài toán lu ng c c đ i trong m ng. Thu t toán b t đ u t ự c nào đó trong m ng (có th b t đ u t
ườ ạ ườ ậ ể ắ ầ ừ ồ ể
ỉ ệ ự ẽ ậ ng tăng lu ng. Đ tìm đ ồ ỗ ỉ
( )ve
( )p v+
ạ ư
( )ve
ộ ồ - ỉ ve ( ), ( ) ầ ứ ầ ấ
ư ạ ầ ượ ứ ể
ả ầ ầ ượ
ấ ả ư
ừ ộ ỉ ề ớ ư ỉ
t c các đ nh còn l ỉ ủ ỉ i gán nhãn cho t ư
ở
ỉ
ấ ả ỉ c l p l ẽ ượ ặ ạ ỉ ng h p th nh t ta tìm đ ỉ ư ồ ứ ấ
ợ
ứ ự ạ c đ ượ ườ
c l i tăng lu ng theo đ ồ ượ ạ ử ụ ượ
ườ
ồ
ng tăng lu ng có th mô t nh sau : ng tăng lu ng trong G(f) có th s d ng thu t toán tìm ki m theo ể ử ụ đ nh s trong đó không c n xây chi u r ng (hay tìm ki m theo chi u sâu), b t đ u t ầ ắ ầ ừ ỉ ề ộ t sau ng minh đ th G(f). Ford-Fulkerson đ ngh thu t toán gán nhãn chi ti d ng t ế ườ ự ấ lu ng ch p đây đ gi ạ ể ả lu ng không) , sau đó ta s tăng nh n đ ẽ ượ ậ ng tăng lu ng ta s áp d ng ụ lu ng b ng cách tìm các đ ồ ồ ằ ẽ ph ng pháp gán nhãn cho các đ nh. M i đ nh trong quá trình th c hi n thu t toán s ươ m t trong ba tr ng thái: ch a có nhãn, có nhãn ch a xét, có nhãn đã xét. Nhãn c a ủ ở ộ m t đ nh v g m hai ph n và có m t trong hai d ng sau : [ ] ho c [ặ , ộ p v ]. Ph n th nh t +p(v) (-p(v)) ch ra là c n tăng gi m lu ng theo cung ồ ả ỉ ặ (p(v),v)( cung (v,p(v)) còn ph n th hai ch ra l ng l n nh t có th tăng ho c ớ ấ ỉ c kh i t o nhãn và nhãn c a nó gi m lu ng theo cung này. Đ u tiên ch có đ nh s đ ở ạ ỉ ủ ồ ỉ ấ ả t c i đ u ch a có nhãn. T s ta gán nhãn cho t là ch a xét, còn t ừ ạ ề m t đ nh v có các đ nh k v i nó và nhãn c a đ nh s s tr thành đã xét. Ti p theo, t ế ẽ ở ủ nhãn ch a xét ta l t c các đ nh ch a có nhãn k v i nó và nhãn c a ề ớ ạ ư i cho đ n khi ho c là đ nh t tr thành đ nh v tr thành đã xét. Quá trình s đ ế ặ ở ỉ ẫ t c các đ nh có nhãn đ u là đã xét nh ng đ nh t v n có nhãn ho c là nhãn c a t ủ ấ ả ầ ặ ng tăng lu ng, còn trong c đ không có nhãn. Trong tr ợ ườ ượ ườ ng tăng lu ng (t c là i đ tr ng h p th hai đ i v i lu ng đang xét không t n t ồ ạ ườ ườ ứ ồ ồ ố ớ ng ng tăng lu ng, ta l lu ng đã c c đ i). M i khi tìm đ ườ ỗ ạ ồ ồ i s d ng phép t c các nhãn và đ i v i lu ng m i thu đ c, sau đó xoá t tìm đ ớ ồ ổ ớ ấ ả ng tăng lu ng. Thu t toán s k t thúc khi nào đ i v i gán nhãn các đ nh đ tìm đ ố ớ ồ ẽ ế ậ ể ỉ ng tăng lu ng. lu ng đang có trong m ng không tìm đ c đ ượ ườ ồ ả ư ể ồ ạ Hai th t c tìm đ ủ ụ ườ
Procedure Find-path;
e [v] là nhãn c a đ nh v;
ng tăng lu ng ườ ủ ụ ồ
˛ V;
ư
ủ ả ˛ { Th t c gán nhãn đ p[v], ˛ ủ ỉ VT là danh sách các đ nh có nhãn ch a xét ; ỉ c[u,v] là kh năng thông qua c a cung (u,v),u,v f[u,v] là lu ng trên cung (u,v), (u,v V); ồ
;
} BEGIN p[s] := s ; e [s] := +¥ VT := {s}; Pathfound := true; While VT<> {} do
BEGIN
159
VT ;( * l y u t ấ ừ T *) V
¨ {v};(* n p v vào danh sách các đ nh có nhãn *)
u (cid:220) For v˛ V do If (v ch a có nhãn) then ư Begin If (c[u,v] >0) and (f[u,v] < c[u,v] ) then Begin P[v] := u ; e [v] := min {e [u],c[u,v]-f[u,v] };
ạ ỉ
VT:=VT If v = t then exit;
End Else
If (c[v,u] > 0) and (f[v,u] < 0) then
Begin P[v] := u ; e [v] := min {e [u] , f[u,v] };
¨ {v};(* n p v vào danh sách các đ nh có nhãn *)
VT:=VT ạ ỉ
If v = t then exit;
End;
End;
End;
160
ng tăng } ườ ậ ồ
PathFound :=false; End; Procedure Inc_flow ; { thu t toán tăng lu ng theo đ Begin v := t ; u := t ; tang := [t]; while u <> s do begin v := p[u];
if v > 0 then f[v,u] := f[v,u] + tang else begin v := -v; f[u,v] :=f[u,v] –tang; end; u := v ;
ể ệ
lu ng v i giá tr 0 *) ở ạ ắ ầ ừ ồ ớ ị
end; Procedure FF; { th t c th hi n thu t toán Ford_fulkerson } ậ ủ ụ Begin (* kh i t o b t đ u t For u ˛ V do
V do f[u,v] :=0;
˛ V > ự ạ
ạ T , V\ VT) > ắ ẹ ấ
For v ˛ Stop := false; While not Stop do begin find_path; If pathfound then Inc_flow Else Stop:=true; End; < Lu ng c c đ i trong m ng là f[u,v], u,v ồ < Lát c t h p nh t là (V End;
161
Ch ươ ươ ng trình ph c v cho vi c h c t p và gi ng d y v ệ ạ
ng trình sau đ ề ả c xây d ng b ng công ự ạ ạ ồ ụ ụ ươ ọ ậ ượ ự ằ
ng trình: Ta xây d ng ch ng trình sau là ch bài toán tìm lu ng c c đ i trong m ng. Ch c l p trình Delphi. ụ ậ Các ch c năng c a ch ủ ươ ứ ự ươ ứ ng trình bao g m nh ng ch c ồ ữ
c th c hi n ng v i t ng ví d c th . ụ ụ ể ớ ừ ệ ứ t thu t toán Ford – Fulkeson. ự ị
Tóm t
ườ ử ụ i s d ng n m v ng đ ắ ữ ượ ậ c thu t
ể
ệ ạ
năng sau: * Tóm t ậ ắ * Hi n th các b ướ ể t thu t toán Ford – Fulkerson : ậ ắ Ch c năng này có m c đích giúp cho ng ụ c khi đi vào các thí d c th . ụ ụ ể c th c hi n c a bài toán: ệ ủ ụ ằ ể ứ toán tr Hi n th các b ị Do ch ươ ứ ứ ả
i s d ng hi u rõ h n v thu t toán. ụ ụ c gi ướ ậ t các b ế ơ ề ị ể
ậ ặ
ướ ự ướ nh m m c đích ph c v cho vi c d y và h c môn Toán r i ờ ng trình ọ r c nên ch c năng vi c hi n th chi ti ụ ụ i bài toán ng v i t ng thí d c ệ ạ ớ ư th giúp cho ng ườ ử ụ ể C u trúc d li u và cài đ t thu t toán: ấ C u trúc d li u: ấ
i d ng t p đ nh và t p c nh. M i đ nh đ c l u theo c l u gi ữ ướ ạ ậ ạ ỗ ỉ ậ ỉ ượ ư
Đ th đ ủ d ư
L_TypeDinh = record
Ten:String;
ToaDo:L_TypeToaDo;
MucKichHoat:Byte;
end; Trong đó:
ữ ệ ữ ệ ồ ị ượ ư c u trúc c a m t Record nh sau: ộ ấ
tên đ nh (m t đ nh là V - Bi n Ten có ki u String , l u gi ể ư ữ
0,V1,…) ặ ị to đ x, y c a m i đ nh có ủ ữ ạ ộ
- Bi n ToaDo có ki u L_TypeToaDo, l u gi ể ỉ ư ỗ ỉ ế ế
ư ộ
x,y:integer;
c u trúc c a m t Record nh sau : ủ ấ L_TypeToaDo = record
end; Bi n Muckichhoat có ki u Byte l u gi ể ứ
ế ư
ữ ứ ộ ể ỗ ỉ ỉ ố ế ạ ị ỉ
m c đ kích ho t c a đ nh (m i đ nh ạ ủ ỉ có 4 m c kích ho t khác nhau), bi n này dùng đ xác đ nh đ nh đ u, đ nh cu i, đ nh ỉ ầ h p…. ẹ
162
T p c nh c a đ th cũng đ ượ ư ủ c l u theo c u trúc c a Record, c u trúc c a ủ ấ ấ ạ ậ ủ
c l u tr nh sau: m i c nh đ ỗ ạ ượ ư
DinhDau,DinhCuoi:Integer;
TrongSo:L_TypeChiphi;
ồ ị ữ ư L_TypeCanh = record
ư ư
Bi n DinhDau có ki u Integer, l u gi Bi n DinhCuoi có ki u Integer, l u gi Bi n TrongSo có ki u L_TypeChiPhi, l u gi ch s đ nh đ u c a c nh . ữ ỉ ố ỉ ch s đ nh cu i c a c nh . ữ ỉ ố ỉ ư ữ
end; trong đó : - ế - ế - ế c nh đang xét. Ki u L_TypeChiPhi là m t Record có d ng nh sau : ạ L_TypeChiPhi = record
Gia:real;
kntq:real;
end;
ầ ủ ạ ố ủ ạ ả ạ ể ể ể ể ộ ủ giá và kh năng thông qua c a ư
ậ
ph n trên , thu t toán Ford –Fulkerson đ ở ượ
ườ ặ ằ c cài đ t b ng ng tăng lu ng) và Inc- ồ
ầ cách k t h p 2 th t c Find-Path (th t c gán nhãn tìm đ Flow (th t c tăng lu ng theo đ Cài đ t thu t toán: ặ Nh đã trình bày ư ế ợ ủ ụ ủ ụ ồ
ườ Đây là ph n cài đ t chi ti t theo ngôn ậ ủ ụ ng tăng). t c a thu t toán Ford – Fulkerson (vi ế ủ ậ ầ ặ ế
ng l p trình Delphi): ữ ậ
163
procedure L_find_path(var L_G1:L_typedothi);
{
thu tuc gan nhan tim duong tang luong:
L_p[v],L_nhan,L_e[v] la nhan cua dinh v;
L_v la danh sach cac dinh co nhan nhung chua xet;
164
}
VAR x,y:integer;
ok:boolean;
a1,b1,k1,l1:real;
t,t1,i:integer;
BEGIN
for i:=0 to L_G1.sodinh-1 do
L_p1[i]:=-1;
L_p1[0]:=0;
L_nhan[0]:=true;
L_e[0]:=vocung;
L_v:=[0] ; L_v1:=[0];
L_pathfound:=true;
While L_v<>[] do
Begin
ok:=true;
x:=0;
While (x<=L_G1.sodinh-1) and (ok=true) do
Begin
If x in L_v then ok:=false
Else
165
x:=x+1;
End;
L_v:=L_v-[x];
For y:=0 to L_G1.sodinh-1 do
If L_p1[y]=-1 then
Begin
L_giatri(L_G1,x,y,t,a1,b1); {a:=c[x,y],b:=f[x,y]}
L_giatri(L_G1,y,x,t1,k1,l1); {k:=c[y,x],l:=f[y,x]}
If (a1>0) and (b1 Begin L_p1[y]:=x; L_nhan[y]:=true; L_e[y]:=L_min(L_e[x],a1-b1); L_v:=L_v+[y]; L_v1:=L_v1+[y]; If y=L_G1.sodinh-1 then Begin exit; End; End 166 Else If (k1>0) and (l1>0) then Begin L_p1[y]:=x; L_nhan[y]:=false; L_e[y]:=L_min(L_e[x],l1); L_v:=L_v+[y]; L_v1:=L_v1+[y]; If y=L_G1.sodinh-1 then Begin exit; End; End; End; End; L_pathfound:=false; end; procedure L_Inc_flow(var L_G1:L_typedothi); { tang luong theo duong tang } 167 var x,y,t,t1:integer; tang,a,k:real; s,s1,s2,s3,s4:string; ok:boolean; begin x:=L_G1.sodinh-1; y:=L_G1.sodinh-1; tang:=L_e[L_G1.sodinh-1]; ok:=false; while x<>0 do begin y:=L_p1[x]; L_giatri(L_G1,x,y,t,a,L_b); {a:=c[x,y],b:=f[x,y]} L_giatri(L_G1,y,x,t1,k,L_l); {k:=c[y,x],l:=f[y,x]} if L_nhan[x] then L_G1.dscanh[t1].trongso.gia:=L_G1.dscanh[t1].trongso.gia+tang else begin L_G1.dscanh[t].trongso.gia:=L_G1.dscanh[t].trongso.gia-tang; ok:=true; end; 168 x:=y; end; end; procedure L_luongcucdai(L_G:L_typedothi; var L_G1:L_typedothi;var gt:real); { thu tuc the hien thuat toan Ford_fulkerson } var x,y,z,t,i,j,t1,t2:integer; a1,b1,f:real; ok1,stop:boolean; s,s1,ch,ch1,a:string; begin L_G1.SoDinh:=L_G.SoDinh ; L_G1.socanh:=L_G.socanh; setlength(L_p1,L_G1.SoDinh); setlength(L_nhan,L_G1.SoDinh ); setlength(L_e,L_G1.SoDinh ); setlength(L_G1.DSdinh,L_G1.SoDinh ); Setlength(L_G1.dscanh,L_G1.SoCanh ); for j:=0 to L_G.SoDinh -1 do L_G1.DSDinh[j]:=L_G.DSDinh[j]; 169 for j:=0 to L_G.SoCanh -1 do L_G1.DSCanh[j]:=L_G.DSCanh[j]; stop:=false; while not stop do begin L_find_path(L_G1); if L_pathfound then begin tam:=tam+1; if tam>1 then L_inc_flow(L_G1) else stop:=true; end; f:=0; for y:= 0 to L_G1.sodinh-1 do begin L_giatri(L_G1,0,y,t1,a1,b1); f:=f+b1; end; for y:=0 to L_G1.Socanh -1 do if L_G1.DSCanh[y].DinhCuoi =L_G1.SoDinh -1 then begin break; end; tam:=0; t2:=1; while (t2<=L_G1.sodinh-2) do begin if t2 in L_v1 then L_G1.dsdinh[t2].MucKichHoat :=3 else L_G1.dsdinh[t2].MucKichHoat :=0; end; t2:=t2+1; end; L_G1.dsdinh[0].MucKichHoat :=3; L_G1.dsdinh[L_G1.SoDinh -1].MucKichHoat :=0; end; 170 Giao di n ch
ệ
Hình d ng trình :
i đây là form chính c a ch ng trình, ng i s d ng có th t ươ
ướ ủ ươ c v s n m ậ ồ ị ượ ẽ ẽ ằ ở ồ ố ả ủ ế ế ị ể ể
ồ ị c đ th k t qu (n m ể ự ẽ ồ
v đ
ườ ử ụ
ph n đ th ngu n). Sau khi đã
ồ ị
ầ
t k t qu c a bài toán thì ta nh n nút Run trên thanh công
ấ
ph n đ th đích).
ồ ị ả ằ ở ầ ướ ấ i ng v i t ng bài toán c th đ
ụ ể ượ
ề
ơ ể ừ ớ i thu t toán b ng cách click đôi vào ậ i s d ng luôn n m v ng đ ph n d th đ ki m tra thu t toán (đ th đ
có đ th ngu n, mu n bi
ồ
c c a form, ta s đ
ẽ ượ ồ ị ế
ụ ủ
c trình bày khi ta nh n Notes.
Các b
c gi
ớ ừ
ả ứ
i s d ng hi u rõ h n v thu t toán, nó trình bày cách làm
Đây là ph n giúp cho ng
ậ
ườ ử ụ
ầ
c t
bài toán theo t ng b
ng ng v i thu t toán đã nêu.
ướ ươ ứ
ậ
i s d ng có th xem l
Ngoài ra, ng
ườ ử ụ
i c a form. Ph n này giúp ng
ầ ể
ạ
ườ ử ụ c thu t toán.
ậ ầ ướ ủ ằ
ữ ượ ắ Để i s d ng, ch ng trình này đã l u s n m t s thí d c
ư ẵ ộ ố fi i s d ng ch c n vào file ươ
ườ ử ụ ỉ ầ ụ ụ
open, sau đó ch nọ thu n ti n cho ng
ườ ử ụ
ệ
thu t toán, ng
th đ mô t
ậ
ả
m t ví d c n xem.
ụ ầ ng trình còn có ch c năng giúp cho ng
ứ ườ ử ụ ụ ớ
i s d ng t o ra các thí d m i ạ ậ
ể ể
ộ
ươ
i các ví d v a t o. và l u l ụ ừ ạ Ch
ư ạ c m t đ nh là V ỉ ồ ị ượ 0,V1,…. Tuy
ườ
i ươ ỉ fi ặ ị
ổ
ằ ể ổ ỉ Tên c a các đ nh đ th đ
ủ
nhiên ch
ng trình có ch c năng đ i tên cho đ nh, ng
ứ
s d ng có th đ i tên đ nh b ng cách vào Edit
ử ụ
rename sau đó đánh tên m i vào (xem hình bên).
ớ 171 Vi c đ i tên đ nh và xoá đ nh có th th c hi n theo hai cách, ng ệ ỉ i s d ng có th
ườ ử ụ
ầ
ỉ ể ự
ư ỉ
ỉ ặ ả ọ ồ ể
ệ
ổ
ồ
ch n đ nh r i ch n Edit nh cách trên, ho c click ph i vào đ nh c n xét r i
ch n các ọ
ọ 172
