Luận văn Nghiên cứu phát triển một số thuật toán giải bài toán lập lịch

CHUaNGill A " JIII..? MO IDNH MANG VAN TAl. . & i1NGDVNGVAo HAl TOANV!N TAl Trangch1A1ngnaychUngta kMo satmQt56cdslJ chity€u ala 1116lUnhmt;tngv4nuii , trangaochungta coxetatfumQt56thu4ttodn rim lu6ngC1ICat;litrh1mt;tngtJ4nuii va mQtvai tlngd\lng cUanO.Sau hit chungta se dung11161Unhva ph1ldt1gpooptim lu6ngaJC at;litrh1 ffit;lngv4nuii tlao~c timphtbngan qtc bih1banaduchobai todn . tI~nuii. ... , ., A I. BAI TOAN Md DAU Ok d6thicohuangvacotrQngs6lamohinhti~ndvngcho nhi~u ngdvngcoSlJdi chuy~ntrongm<)tIlli}.ng(net).Saudayla m()tvidvminhhQa. Xet d6 thi co htrlng,lien thongtronghinh (Hl),bi~udi~n m()tIlli}.ng6ngd§.nm<)tlo~iluuch~t. a 2 J z LUllchit d1i<JCkhdingu6ntita din ndidn sadvngla z.Ok dinhhaynodec,d,b vae cOth~xemla cactr~mtrungchuy~n. Ok ~nh cohudngbi~udi~ncacduOng6ngd§.nluuchit cuah~ th6ngvachifOhuongcualuuch~tphaidi.cac nhan(cacs6) ghi trencaca}.nhchobi~tkha~ng cungclp (v~nchuy~n)cua6ng d~n.B~iitoand~tfa la haydmcachd~crJcd~ihoaI1J(;1ngluucM't coth~v~nchuy~nd1J(;1cti1ngu6nadin dkh zvarinhfagiatrj / 25 e1.J.e d~ieuaeachv~nehuy~nay.DftyIam~tvi d'l bi~udi~nd~e dU'did~ngm~tm~ngv~ntai (transportnetwork). " . II. ~NG V~NTAl. 2.1Dinh IDa. ng M~t m~ngv~ncli (transportnetwork)G =(V,E)voiV lat~p h<1pcaedinh vaE la t~ph<1pcaeeung, la m~tdo thj hihlhuong, cotrQng56,li~nthongrheacaedi~uki~n: i) COdungm~tdinhtrongG =(V,E),gQilanguOneungd'p,la dlnhkhongco~nhvao. ii) Codungm~tdinheuaG =(V,E), gQiladinhthunh~nhay dich, ladlnhduynh§tkhongco~nh ra. m)caetrQng56C 11euacae~nh co hudng(i,j)d~egQila kha n~ngeungd'p eua(i,j)hayla luOngehuy~ntai tr~n~nh (i,j)tit dinhi dtIi dinhj,C ii lam~t56khong§m. iv) D6 thj vo huongtrt1ngUngvoi ~ng G = (V,E) Ia do thj nh~nd11<1eb~ngeachbequahuongtr~ncae~nh . llinh tr~nlam~t~ng v~ntaLNguonIaavadichIaz. Kha.n~ngeungd'p tr~n~nh (a,b)la Cabb~ng3vatr~n~nh Cbcla2. M~tluOngchuy~nta.iF trongm~t~ng v~ntaiG dU<1edjnh nghIaIad~il\i(/ngb~ngt6ngcaeluongehuy~ntai tr~nm8i~nh (cohuang)khongV\t<1tquakha.n~ngehuy~ntai ala nhung~nh do.Hemnua,phaigia.thitt th~mr~ngl11<1ngmam~tdlnhv nh~n taival\i(/ngxua'taititdinhv phaib~ngnhautr~nt§tcl caedlnh khongphailadinhnguOnhaydich. 2.2f)jnhnghia ChodothjcohudngG=(V,E).~t ell Iakhan~ngehuy~ntai eua~nh huuhuang(i,j).M~tluOng(haym~tdongehuy~ntai)F trenG lam~tphepgallm8i~nh hftuhuang(i,j)m~ts6khong§m FIirhea: i) 0 ~Fil ~CiivoimQi,j . 26 ii) Voi m6idinhj (kh6ngphailangudnhaydkh) L Fij =L Fji (1.1). . 1 1 Trongd6t6ngd~cliy tr~nmQidinhi voigiathi~tlan~u (i,j)kh6ngphaila m~tc~nhthi Fij =0 Ta gQiFiilam~tludng(chuy~ntai)tr~nc~nh(i,j)tit i d~nj. Voi m6idlnhj tagQi: L Fij. 1 la lU<ingchuy~ntai vaochodinhj va L F..J1. 1 ' lalU<ingtaixua'tratit dlnhj. Tinh chit bi~udi~nb~ngphUdngtrlnh (U) dU<icgQila SlJbaa roanlU<jngchuy~ntai tr~nludng. Trongvi d'Str~n: cae phepgall : Fab= 2, Fbc= 2I Fez= 3, Fad= 3, Fck:=1, Fde= 2, Fez= 2 xacdjnh m~tlu6ngtr~nm~ng. Xemdongtai vaodinhd taco Fad=3 trongkhi dongxua'tratitd la Fck:+F de =1+2=3. I-nnh sauxuit pharotit ~ng cho trongvi d'Str~nminh hQa ludng(chuy~ntai)vitan~ucua1Il4ng.C~nhdU<icdanhnhanX,vne'u x la lU<ingtai vaodinhvay la hilng tai xuit phatra titdinh. 27 al... . .2 Trong vi dq nay, IU<;1ngcli xu~tra tit nguOna Ia Fab+ Fad=2+3 b~ngIU<;1ngh~pvao euadfchz : Fez+ Fez= 3+ 2 vi cl 2d~ub~ng5. Djnh Iy sanehoth~y ke'tquaIt/ll11gxwfttit ngu6n 11/{1ngnhQpvaochodfch z nayIu~ndung. z a lu6nbang 2.3Djnh 11 N€u F lizmQtlu6ngchuylntdi (hiLmtdi)trongmQtmq.ngv4ntd~ ItlQ'ngxudttit a lu6nbang11lI,1ngnhQpvaocooz. Nghiala: L Fai = L Fiz.. 1 Chungminh: ~t V Iat~pcaedlnh.Tae6: L (L Fij) = L (L FiJ je V ieV je V ieV trongkhim8itOngkepla : L Fe eeE trong06E lat~ph<jp'caeqnh. Baygio, 0=L (L FiJ .. L F;J jeV ieV ieV . 1 28 - (1;Fiz"LFzJ+(1;FIz"L FaJ+ 1; (LF1j"L FP) ieV ieV ieV ieV jeV ieV ieV (j "*a,z) = L FIz" L Fai je V ieV VI FIi = 0 = Fai voi mQii eV va theo djnhnghla ta co : L Fii .. L Fji =0 nlu jeV \ {a,z} ie V ieV 2.4Djnh nghia Cho F la rn~tluOng(ehuy~ntai)trenrn~trnangv~ntaiO. Oia tri eualu6ngb~ng: F = L Fai = L Fh ie V ieV Trongvi dl1trengiatri euaF ill 5. 2.5Phatbi~u1mtoantren~ v~ uii: , Baitoantrenrn~trnq.ngv~ntaicothephatbi~unhusau: Chom~ngv~ntai0, haydrnluOng(ehuy~ntai)cogiatri Ionnhit trongO.Nghiaill trongtit cl caeluOngehuy~ntai tren0, haydm lu&ngehuy~ntaicogiatri Ionnhit. BaitoandrnluOngehuy~ntaiaJ.ed~itrenrnq.ngv~ntai co nhieu ungdl1ngthtJetl nhuvi dl1sau: Vi d1}: M~ngcaetr~rnbornnujegiiia2 thanhph6A vaB duqeeungca.'p nudetit 3 rn~ehnguOn uoela wi,w2,w3.Khan~ngthunh~neua h~th6ngtrunggianduqctho trencaee~nh.Caedinhb,e,dla cae tr~mbdmtrunggian. 29 b 6 4 A wl w2 w3 DOthi tr~nchuaphiiiIa m~hlnh mq.ngv~ntai vi conhi~u nguOnvaovanhi~udfchnh~n.Chungtacoth~chuy~nm~hinhh~ th6ngnaythanhm~hinh mq.ngv~nt:HtUdngdUdngb~ngcach choth~mvaom"t nguOnph~(gia:supersource)va m"t dfchph~ (dkhgia: supersink)voikhanangcuacq.nhtUdngungla m"tllic;1ng v~cungIon.Thuongbi~uthikhan~ngthu.. nh~nv~cungIondo b~ngiatrj M. b a .It A \111 2 2.6tat cAt. DuOngtmglu6ng.Djnhly Ford..FulKerson Djnhnghia: Chomq.ngv~ntai(G,V)codinhnguOns vadinhdfcht.Ta gQilat clt(x,x')la m"teachphanhoq.cht~phQpcaedinhV cuamq.ngthanh2 t~pX vaX'=X\V , trongdodinhngtiOnthu(kt~pX condinhdfcht thu"c t~pX'.Khan~ngthongquacualatcAt(X,x')la 56: 30 c(x,x')= L Ctj ieX,jeX' M"t !atc~tc6khan~ngth~ngquanhonh~tdrlQcgQila !atc~tht;p nh~t. M~nhat!:. Gid trj cUa1T1QiluAngF trong1TU;1ngloonnM hdnhot;'fcbd:ngkhdndng tMngquaala latcdt(X;X')tUyY trongnO: F 5 c(X;X'). H~quii : Gid trj luAngchU')inuIi C1/CdQitrongm(lngkMng4JtbltquO.kM ndng tMngquacudmQt'fatcdth{!pnhdt. FordvaFulkersonchungminh~nggiatrj luOngcv.cd~itrong~ng dungb~ngkhan~ngth6ngquacualatc~th~pnh~t. Gia si1F la m"t lu6ngtrong~ng G=(V,E).Tit m~ngG dv.ngd6 thj G'=(V,E')trongd6 t~ph\1pcaccungE' va caetrQngs6tr~ncaeeungd~e nnhtheoquit~esau: a)N~u(i,j)thu"eE voi F(i,j)=0 thi (i,j)thu"eE' voi trQngsfSla~j. b)N~u(i,j)thu"eE voi F(i,j)=Ctj thi (j ,i) thu"e E' voi trQngsfSla F(i,j). c)N~u(i,j)thu"eE voi0 < F(i,j)< ~j thi (i,j)thu~E' voi trQng s61aCj .. F(i,j)va0,i) thu"eE' voitrQngsfSF(i,j). CaeeungcuaG' dOngthOiding la eungeuaG d1iQegQila cung thu4n, caeeungcon~i gQila cungnghich.DOthi G' d~e gQila do thi t~nglu6ng. Gia si1P =(5=i<J,i 1, , i Ie=t) Iam~tduongdi tit 5d~nt trongdo thit!1ngluOngG'.GQi0 lagiatrj nhonh~teuacaetrQng56euacaeeung tr~nduongP CJtr~n.Ta:>caydv.ng.lu6ngmoiF* tr~n~ng G theoquyt~e: { F(i,j) +8 F. (i,j) = F(i,j) - 8 F(i,j) nln(i,j)thu~cP vaIacungthu~n n~u(i,j)thu~eP va Ia eungnghjeh nlu(i,j)khdngthu~cP 31 C6 th~ki€m chungd\!;1cF* la luongtrongm~ngva F* =F +o. C3chbie'nddi luOngrheac6ngthucnaygQila t~ngluOngdQcrheadu'Ong P.TagQiatbYngtdnglu6ngF l1z111QiatfJngai tit ngu6ns dena£Cht tr~na6 thila tdnglu6ngOF. llI.nruA T ToAN TIM LUONGVAN TAl CUe BAl.. .. . 3.1Djnh 'nghia: ChoF la m"t luOngtrong~ng v~ntai G-(V,E) co dinhnguOns, dkh la dinh t. M"t luOngv~ntai cvc d~itrongG la m"t luOng chuy€ntaicogiatri Ionnh§'t.Trongtru'Ongh<lpt5ngquat,co th€ c6nhi~uluOngchuy€ntaic6cunggiatrj Ionnh§'t.Saud~ychung taduaram"tthu~troandmm"tluongevcd~i. y tlidngth~t toaDv~cln ban demgian nhu sail: chungta b~td~ub?ingm"t luOngnaod6 va l~pdi ~p ~i vi~ct~nggia tri cua' luongchode'nkhi khongth€ t~ngduqcnua.Ke'tquanh~ndUQcchfnh laluOngevcdq.icftndID. LuOngb~tdftuc6 th€ chQnla luOngtrongdo IUQngchuy€n la o. Nhu v~ym"t ludngchuy€n tai ban dftuc6 th~dUQckhdi tq.O b?ingeachgall bandftula chot§'tcl cacgiatri Fii=0 voi mQidinh I vaj. ~ t~nggiatri cualudngdaco,chungtaphaidmdu'Ongtit nguOnvaosde'ndkh t vat~ng iatrj cualudngdQctheaduongnay. D~,th§yludngnayrheacacgiathie't.cuabai roannhungkhong ph:Hla ludngc~ndill,vi kill d6 khongc6 IUQngluuch§'tnaotit nguOnsde'nt. ChotmJCm"tludng, chungtaco th€ cli tie'nsaocholudng moitit sde'nt lagiatrjd1i</C~ngleDsovoi ludngdac6.Di Dillen, dBtie'nnayphairheamanmQiyellcftucuagiathie'td6ivoi m"t luOngchuy~ntaL~c bi~t,ntu luOngnh~pv?wm"tdinh b§'tky (trusvat)d\J(/ct~ng iatrj haybi giam giatri thi ludngxu~tratit dinhd6clingphaidu<lct~nghaybigiamm"teachtUdngung. 32 Phuongphapdmml>tluOngevedq.idti<JCb~td~ub~ngluOng cogiatri 0 vaCattitn li~nti€p ehodtn khi ml>thamt6iuudu<;1e thanhl~pnhuv~y. Thu4ttoonMaxFlow: begin Khltitq,o: bdtadubanglu6ngcogidtrj O. far i c V do far j € V doF(ij) =0 Dung=False; ~ whilenot(Dung)do if (TIma1l(1ca1liJnguY:nglu6ngP) then(uY:nglu6ngdQctheoP) dse Dung=TruE; end; ~ dm dU<;1ed1iJngt~ngluOngtrongOF co th~dungth~t tmindm kitm theoehi~url>nghaydm kitm theoehi~usauba:td~u ticdinh s .FordFulkersonsUdv.ngthu~ttoangall nhan dm luOng e1.jedq.inhusau: 3.2Tht4t toanFord..Fulkerson BLEdtadubang mqtlu6ngchdpnhQ.na1l(lctrong 7Tl(Ing,co thi! ludng cOgid tri o. . B2.TIm a1liJnguY:nglu6ngbangcachgdnnhiin chocaetIlnh. M6i ainhtrongkhi thtlc~ thu4ttodnloon thuQc1 trong3 trQngthai: * Ch1iacOnhdn. * CO nhiinch1iaxet. * CO nhiinad xet Nhdnala mqtainhg6m2 phdnthuQC1JWtronghaid4ngsau: [+P(i),s(i)] ~c [..p(i),s(i)] DQng[+p(i),E(i)]chira la cdnuY:nglu6ngth£ocung(P(i);)vdi G(i)la l71l;fngldn Mdt co thl tdngtheocungnay. DQng[~P(i),E(i)]chi ra la cdngidm lu6ngtheocung(i , P(i) ) vdi G(i)la l71l;fngldn nlu1tco thl gidmtheocungnay. 33 Dflutienchic6aiM ngu6ns lit atl(fcgannhdn00a6 lit nhdn cht/axet,conmQiainhcon14icht/ac6nhdn. Tt'(s chungtagannhdnchocaeainhk ~ vdin6va nhdnala ngu6ns khia6£fathanhnhdnan.xet. Titp theo, tit m6ialnhk c6 nhdncht/axetchungta 14igan nhdnchotdtcdcaeainhchtlac6nhdn~ vdik va nhdna1adinhk £fa thanhan.xet. Quatrlnhat/1lC14P14ichoah1khi: + HoQczaafcht trClthanhc6nhdn. + ho<iczatdtcdcae01nha~ c6nhdnvazanhdnad xet nhungt vtinkMngc6nhdn. Trangtnli1ng1u;tpthtlnhdtchUngta rimatl(fcatftngtdnglu6ng cOntnIi1ng1u;tpthll2 chungta kMngrimatb;fcatftngtdnglu6ng(n6i cachkhdczachungta ad rima141Clu6ngC1/CaQi) McSikhirimat/1lCatftngtdnglu6ng, chungtasetdnglu6ngtheo a11iJngama1lt;1ca6,saua6 x6atatcd caenhdnva vdi lu6ngmill thu atlQ'Cchungta 14i.stld¥ngeachdanhnhdntrencaeainhat rimatldng tdnglu6ng. ThuQ.ttodnketth1i.ckhid6ivdiluAnghi?nhanhchungta khOng rim atlQ'CatlCJngt1ing lu6ng. 3.3Phddngphap~ng ludnglu6ngvQ.ntii hi~nhanh ChotntJcm~tluOngv:)nt:HF cO2eachdi cli titn no: each1la dmm~tduong5=Xb Xl, ..., Xn= t tU s dtn t sao eholuOngdQctheom6icungtrongdu<1ngdo la nho hdnsovoi kh:i n~ngthu n~n ( FIc-1,It< CIc.1,It)voi mQi k giua1va n..1LuOngcOthi dtl<leamt~ngtr~nmOicung trongduClngdo bhngeachlamevctiiu giatri CIc-1,It.. FIc.1,Itvoi mQik giua1 va n..l , saoeho khi luongda d1iCJet~ngthl dQctheotoaDb~driOngco It nhft'tm~teung thul)edudngdo taco : FIc-l,k= CIc.1,Itva khongcon cungnaocOthi t~ng. 3.411n1tVcgallnhanrlm duCJng~ng lu6ng. 34 lhuroc ~'indPad:- :1; p[i],E.{i]la nMn cUadlnh"11Odei. vf la danhsdchcaedlnhc6nhdnchttaxet. C[iJ[j] la kM ndngtMngquacUacung(ij) td ~j la cacdInh ala d6tN. F[i][j]la lu6ngc/wylnuii tT~cung(i,j)tit i dht j. begin pfs]= S j E.{sJ=Mi M la gidtTjt'6cUngldn. PathFound=TRUE., whilE(Vf kh6.crdng)do begin Ldyi tit t4PVT for (j th~ct4PV\vf) do begin if (C[i][j]>0)&& (F[i][j]<C[i][j])then begin p[jJ=i; E.[j ] = nUn{E.(I],C[iJ[j] , F[i][j)}; vf =VT u {j};//11Q.pj vaodanhstich // cticdInhc6 nhdn. if j =t then thOOt end; if (qi][j] >' 0)&& (F[i]U] >0)then . begin p[j] =, ~ G(j ] =min {E.[i],F[i][jJ}; VT = VTu {j}; //11Q.pj t'ao //sdchcticdlnh.c6nhdn. if j =t thenthOOt end; end; end., PaxhFound= FALSE; end; 35 ~ ~6iCfmr dinp'1116 3.5Thti tQcding lu(,us -"-- _.~ hU~.._.Jng. Thti tQcT3DILFlow; begin j = pet]; i=t; tang= f.(t ]; while(i 1=5)do begin if 0>0)thenF[i]U] = Ffi][j] +tang; else begin j = ..j; F[i]U].. tang; end; i = j ; j = p[i]; end; end; 3.6Thu tQcMaxFlow(Ford..Fulkerson). { for ( i E V) do for (j E V) doF[iJU]=0 II KhltitQ.oluAng0 Dung= TRUE; do{ Find_Path;IlclmattitngtitngluAng if (PathFaund)thenTang_Flow II trit node5 elseDung = FALSE; } while(Dung TRUE~ "LuAngc¥caQitrang1I1IJng1i.zF[i][j], (i,j) E V' " latcdt~p nMt 1i.z(VT, V\VT) " }; 36 Vi dv.xetm~ngv~ncli sau: s 5 t Va hinh sauminhhQam~tlu6ngtrong~ng: 9 3.J t ffinh tr~ndayminhhQam()tlubnghi~nhanh.Tr~ndb thj co2duongtitsde'nt la (s,A,c,t) valubng(s,B,D,t). ~a~: Trang mQtmdngvt;intd~neutrbl a1liJngai tit nguAndenainh aich comQtCtJnhcungcdpady htlhngWi hay~t cq.nhrdng theohtlhngtpu1:J lid thi luAngvt;inchuylntheoa1limga6 la C1/Caq.i. Tr~nc:k lubngv~ntaiquacaeduong(s,A,C,t)va (s,B,D,t), d~ucochuaeungvatrongd6coeungkhan~ngthu nh~n.Vi v~ylubngdQetheehaicungnaykh6ngth~cli tie'ndUQe nua(theom~nhd~tr~n). 37 Tr~nd1iC1ng(s,A,D,t)co kha n~ngthu nh~ncuam6i cung trongd~ngthl IanhdnIu6ngtaihi~nhanh.TdngIannhfttco thi t~ngIu6ngla 1vi Iu6ngtai tr~ncungkhongthi Vli<;1tqua3. Ktt quasaukhi t~ngIu6ngnaynhusau: s 3.3 t Saucli titn nay,kttquanh~nd~c cho tdngcua Iu6ng chuy~ntaitU5lend~ 6. each 2 :COnhungdtiJngkhacmaIu6ngco th~cli thi~n dUQcnhu trongIu6ngchuy~ntiB ban d~uta khaosat duong (s,B,A,D,t).Ktt quat~ngIu6ngrheaduongnayla : 3.3 s t Ngaycl trongt:ntOnghClPkh6ngco duongmalu6ngchuy~n tiHtrendo co th~cM titn d~c,ding co th~co nhungphridngphap khacd~cli titn lu6ngtUngu6nsdtn dicht. Vi dq.sauminhhQadieunay B t 38 Trongdo thj nay:kh6ngcoduongnaotits dtn t maluong chuyintaico thi caititn.Nhungntu luong(X,Y)dUC1cthugQnl~i thl luOngtitX dtn t c6 thi t~ng.Bu truchovi~cgiaml~ng nh~p vaochoY titSde'nY c6thi t~ng.Dodotadat~ngluOngtitsde'nt , varheadoluOngchuyintaicuachungtat~ngtit4 l~ndUC1c7. s t Chungtat6ngquathoa2phuongphapnaynhusan: GiasUc6mOtduongtits de'ndinhY, mOtduangtitdinhX de'nt va mOtduongtitX de'nY voi giatti luOngchuy~ntiHla s6 duong. Khi d6luOngdQctheoduangtitX de'nY coth~c6th~du~c rutgQnlq.i(giamdi) vacacluOngtitX de'nt vatitsde'nY c6 th~ d1i<lct~ngcung56IU<Jng.LUC1ngayIagiatti nhonha'tcuaIuongtit X de'nY vahi~ugiUakhan~ngthunh~nvaluOngchuy~ntai trong cacdudngtitsde'nY vatitX de'nt. .. 3.7PhAncai~t thutttoantr~n. Xet~i th~t toandan~utr~n(Jday: Thu tIIc MaxFlow (Ford..FuIkerson). 1.{ 2. 3. 4. 5. 6. 7. 8. 9. far ( i c V) do far (j €! V) doF[i]U] =0 II KhlfitQ.Olu6ng0 Dung=TRUE; do { Find_Path;Ilclmd1litngtdngludng if (PathFaund)thenTang_Flow II tril nodes elseDung=FALSE; 39 10. U. 11 13.}; } whiL< . e(Dung TRUE); "Lu6ngate d(zitTangffl(,1ngld F[i][j], (~j) fE V" " latctit~p Mdt ld (VT,V\VT)" Ph~~chu yiu cua th~troanla l~nhd dong 567.Khi m~t nodedadU<;1cd~tvaom~tdu'Ong~ng ludngno khOngth~dU<;1cnoi rt)ngd~dungvaom~tdti1ngt~ngludngkhac. Khi caid~t,chungtadung: 1).M~t mcingeaccd hi~u(flags)onpath[node]chi dinh mt)t nodethu~chaykhOngthu~cvaomt)td1iCJng.Day nayding chi djnh nhungnodenao la nodescu6i cuam~td1iCJngsaccho co th~khai tri~nb?ingeachct)ngthemnhungnodek~voi no. 2). Dayendpath[node]d~chi djnh m~tnodeco phciila node cu6icunghaykhOngcuam~td\iJng t~ngluOng.Voi mOinodetren mt)tduongt~ngluOng th~t roanphciigiu l~inhunggl nodetniOc no trendti<Jngt~ngluOngdo vachi~ucuacung. 3).Day precede[node]tro din nodetruacnodedo trendudng t~ngluOngcuano va 4)Dayforward[node]co gi3.trj TRUE niu va chi niu cungdi titprecede[node]din node. S).Dayimprove[node]chi dinh s61u<;lngmaluongchuy~ntai toi nodeco th~duqct~ngdQctheeduongt~ngludngcuano. Th~t loan rim m~tiIufJng tanglu6ng trI s iIt!D.t Dba'saw liGan cooendpath[node],anpath[node]gid trj FALSE 00imQinode. endpath[s] =TRUE; anpathfs]=TRUE; II Tinh lu6ngCIJcaq.itit s ma cdea1Jilngddn co thl chuylntdi. improoe[s]=tdng cde C[s][node]trro tOt cd cde ainh node. while((anpath[t] FALSE) && ( t6ntq.i~t nodend 00iendpath[nd] TRUE) { endpath[nd]= FALSE; while(t6ntq.inodei tlu3a(anpath[i]FALSE) && i L 40 adjacent(nd,I) = TRUE)&& (f[ndlfi]< C[nd][i]»{ II dOngtil nd deni co tM tdng,aQ:ti tltlO a11CJng onpath[i]= TRUE; endpath[i]=TRUE; precede[i]= nd; forward[i] TRUE; x =C[nd][i].. f[nd][i]; improve[i]= (improve[nd]<x)? im[rove[nd]: x; }1/ while(tdntQ.inodei thOa(on- while(tdntQ.imQtnodei saocoo (onpath[i] FALSE) && adjacent(i,nd)= TRUE) && (f[i][nd]> 0 » { // dOngtil i aenndco tM gidm,aQ:ti tlCtoatlltng onpath[i]= TRUE; endpath[i]= TRUE; precede[i]= nd; forward[i]= FALSE; improoe[i]= (improve[nd]<f[iJ[ndl)? imrooe[nd]: f[i][nd]; }II (tdntQ.imQtnodei saocoo (onpath[i] FALSE) && }II while(onpath[t]- if (onpath[t]= TRUE) "TIma1lt;fcatlltngtdnglu6ngtits dent"; else 'I Lu6ng~ hanhLa lu6ng C1JcdQ£'; Ngaykhi dmdU<jcduongt~ngludngtits de'nt, tacoth~xacdjnh duangt~ngludngMi : x = improve[t]i nd=t; whil£(nd1 s) { preLl= precede[nd]; (forward[nd]= TRUE) ? (f[pred][d]+= x) : (f[nd][Pred]..=x); nd= pred; }II whil£ 41 Xetv£d\lCItrangtr~ vaimt,lngtJ4nwi sau: 3 5 s t M,1ngMY g6m6 111M,l1aMsdtit0 aen5.DUngmatTQn~ bilu dihl ta co matTQndq.ng Ke'tquakhi thvehi~nehUdngtrlnhtaco : Ke'tquaChuongtrlnh TIm Lu6ngCveDq.iTrongM~ngV~nTai = 000--- BaitminM~ngV~nTaibiiudi~nd~id~ngmatr~nk~: 0 1 2 3 4 5 ####I####~###~#~##~######~#~#~##### 0 I 0 5 4 11 0 0 0 21 0 0 5 31 0 0 0 41 0 0 0 51 0 0 0 0 0 0 3 6 0 0 2 0 0 0 4 0 0 3 0 0 0 42 s A B C D T s 0 5 4 0 0 0 A 0 0 0 3 6 0 B 0 0 0 0 2 0 C 0 0 0 0 0 4 D 0 0 0 0 0 3 Ktt quat~ngluOngIftntha: 1 0 1 2 3 4 5 """I'~"""""'~"""""""""""""""'""", 0 1 (5,3) 1I (3,3) 21 31 ' (4,3) 41 Ktt quat~ngluOngIftntha:2 0 1 2 3 4 5 """I""""""""""""""""""""""'~'""", 0 1 (5,5) 11 (3t3) (6,2) 21 31 (4,3) 4 I (3,2) Ktt quat~ngluongIftntha: 3 0 1 2 3 4 5 """~"""""""""""""""""""""",,,""" 0 I (5,5) (4,1) 11 (3,3) (6,2) 2I - (2,1) 3 I (4,3) 4 1 (3,3) BangKtt Qua: 0 1 2 3 4 5 """I"""~""""""""""'" 01** 5 1 ** ** ** 11** ** ** 3 2 ** 21** ** ** ** 1 ** 31** ** ** ** ** 3 41** ** ** ** ** 3 Giatri lu6ngCtJCd~iF = 6 43 3.8MOtvai ~ dQIlgcuachudngtrinh ~n. 3.8111n~d\Jn~vaobai tminv~ntai. M~tvi d'l thu~e16pe:k bai tmine6 th~gi~iiquy~tnhu m~t bai roanehuy~ntai la bai roanv~ntai trongIV thuy~tqui hoq.eh tuyin tfnh. Cho St.SzI-ISm va Tl, Tz J-ITn la 56caengu6nva caedkh trldnglinggiuacaethveth~eungbanchit sedUJeph§.nph6i.M8i Si e6m~tngu6neungd'p hifu hq.nla Ai va m8idkh e6m~t56nhu eftuhifu hq.nla Tj . HdD.Quae6 m~tchi phi la ~j tr~nm8i ddD.vi thveth~khi mu5neunge~ptitSi de'nTr Trangth~hi~nddD.gi:in nha'tkhonge6 vi~ehq.neh~v~56lUdnghangph:ii eungtip tit St de'nTj ,ngoaivi~eph:iitranhvi phq.mcaerangbu~eMi A vaBj. Bai roand~tra la ph:iiph§.nph6inguy~riv~tli~utitngu6n d~ndkh nhuthe'naod~ehora t5ngchi phiv~nehuy~nla nho nha'tmakhongVUQtquanhudu ti~pnh~neuam~tdkh vakhong vuqtquakh:i n~ngeungca.'peuam~tnguOn. Bairoannaye6th~dU<;lekh:iosat nhulabairoandmluOngt:ii e6- chi phiC1jeti~ueuagiatri C1jedq.itrongmq.ngtronghlnh (ill). C~pthli tV (x,y)n6i v6i m8ieunge6V nghialax lakvhi~u kh:i n~ngtie'pnh~nva y la chi phi eho m8i ddD.vi. 44 Ntu duC1ngv~nchuyenchuyentit Stdtn Tj kh~ngdu'Qc phep(bi c1m)thl vai c~pi, j cungn6i trtdngungsedu'QCbequa(x6a di hayc6 thechovaon6 m<}tchi pmcvcIan).TuongtIJ ntu c6 m<}t giai h~ntr~nve kh6i htQngv~nchuy~ntit Stdtn Tj thl kha n~ng tie'pnh~nhftuh~nd~c n6i vai cungthich h<;1p.Trong tru'Ongh<;1p nayc6 the x:lyra t1tcl nguOncungc1psekh~ngdii cho nhu ca.u. DUthe'naodi ch~ngnila,loi giaicuabai tminchuy~ntai sedu'QCbe di vi~ctim tdng56c\jcd~imathaybhngchi pmcvcti~u. Sa d1lngphUdtlgphapdm luOngc\jc dq.ichungta tim dUcJc phUdngan banda.uchobai roanv~ntai: Vi d1l: . Xetbairoanv~ntaitimmillchipm: Duavemq.ngv~ntaivaimatr~nkenhtisau: Mq.ngv~ntait\t1ngungvrn.b~iroan 1 2 3 4 5 6 7 8 """1,"""""""""""""""""""""""""", 110 210 310 410 0 0 300 .300.300.300 0 0 0 150150 150 150 0 0 0 250 250 250 250 0 0 0 0 0 0 0 100 45 B1 B2 B3 B4 100 125 125 350 AI 3 6 7 8 300 A1 6 9 7 5 150 A3 12 8 n 9 250 51 0 0 0 61 0 0 0 71 0 0 0 0 0 0 0 0 0 0 125 0 125 0 350 0 0 0 Ke'tquathu~ttoanFord..Fulkerson TIm Phutnlgan DduTi~ncuaBTVT. ===== 000== Ke'tquaphftnph6ibuoc:1 1 2 3 4 5 6 7 8 ~ I """"""""""""""""""""""""""""""""""""".. 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Ke'tquaphanph6ibuoc: 2 1 2 3 4 5 6 7 8 ~~~..~I """"""""""""""""""""""""""""""""" 0 100125 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Ke'tquaphanph6ibuoc:3 1 2 3 4 5 110 0 0 100 125 210 0 0 0 0 310 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 125 0 0 0 0 0 0 ~~~~~~~~~................................................................................................ 6 7 8 75 0 0 0 0 0 0 0 0 11 0 0 21 0 0 31 0 0 41 0 0 51 0 0 61 0 0 71 0 0 110 0 21 0 0 31 0 0 41 0 0 51 0 0 61 0 0 71 0 0 46 410 0 0 0 0 510 0 0 0 0 610 0 0 0 0 710 0 0 0 0 Ktt quaphftnph6ib~c:4 1 2 3 4 5 6 7 0 0 100 0 0 125 0 0 75 0 0 0 ~~~~~~I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~",,~~ 8 110 0 0 100 125 75 0 0 21 0 0 0 0 0 50 0 0 310 0 0 0 0 0 0 0 4 I 0 0 0 0 0 0 0 100 51 0 0 0 0 0 0 0 125 6 I 0 0 0 0 0 0 0 125 710 0 0 0 0 0 0 0 Ke'tquaphftnph6ibuOc: 5 1 2 3 4 5 6 7 ~~~~~~~~,~~~,~~~,~~,~~~~~,~~~",~~""~,~~~~~~~~~~,~,,,~ 8 110 0 0 100 125 75 0 0 2I 0 0 0 0 0 50 100 0 310 0 0 0 0 0 0 0 4 I 0 0 0 0 0 0 0 100 51 0 0 0 0 0 0 0 125 6I 0 0 0 0 0 0 0 125 7I 0 0 0 0 0 0 0 100 Ktt quaphftnph6ibuoc: 6 1 2 3 4 5 6 7 8 ~~~~~I~~~~~~~~~~~~~~~~~~~~~~'~~~~~~~~~'~~~~~~~~~~~~~~'~", 11 0 0 21 0 0 31 0 0 41 0 0 51 0 0 61 0 0 71 0 0 0 100 125 75 0 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 250 0 0 100 0 125 0 125 0 350 47 Suyraphtidnganevebienband§.udmd~ ehobairoan: T6ngChi Pill euaPhtidngan : 5900' 3.8.2Ung dv.ngV3.0Bai toanprumcdng: Ne'um = n va ne'ucaebi~uthi euaA va B illn hi</td1i</ex m 1acaenhanvienva eongvi~ethi eungm~tmohinh nhuv~ytatie'p e~nva nh~ndll</ebai roanphaneongddngian,trongdo m ng\iOise dll</egallvoi m eongvi~esaoehon~ngsuit hoq.td~ngdq.thi~uqua nha't(trongtI1.1dngh</pnayUiila d~do gia tti hoanthanheongvi~e khi gallehong\iOi lameongvi~ej). Kha n~ngtie'pnh~nd1i</ed:)t ehob~ngdonvi. Trongbairoanphaneongvi m6inhanvienchi co th~lam m~tvi~eva m6ivi~echi dll</CthtJchi~nMi m~tnguai.Ne'um~t ngtiOinaodokhongth~lamduqem~tvi~en3.0dothieunglienke't 48 BangKe'tQua: 1 2 3 4 5 6 7 8 .I............................ 110 0 0 100 125 75 0 0 210 0 0 0 0 50 100 0 310 0 0 0 0 0 250 0 410 0 0 0 0 0 0 100 51 0 0 0 0 0 0 0 125 610 0 0 0 0 0 0 125 710 0 0 0 0 0 0 350 B1 B2 B3 B4 100 125 125 350 AI 300 100 125 75 A2 150 50 100 A3 250 250 giuachungcoth~boqua.Khi m()tngtt(jinaodokhongth~lamm()t vi~cnaodothlcungn6ichungtacoth~chochiphila m()thhngso' khal&nn6i 2 dlnhdo.TrongtniJngh\1pnhubaitoanv~ntai co nhungndic~n(nhuc~u)l~ikhongco th~co hangd~nh~n(cung khongdtid.u),thi tUmgungtrongbaitoanphancongnay,cungco nhungvi~ckhongcongu)ith\jchi~n. ~;;;;;;;~;;;;;;;;;;;~~;;;;;;;; III ~;;;;;;;;;;;~;;;;~;;;~;;;;;