Bài giảng Phân tích và thiết kế giải thuật

349 trang phuongnguyen 3591

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phân tích và thiết kế giải thuật", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_phan_tich_va_thiet_ke_giai_thuat.pdf

Nội dung text: Bài giảng Phân tích và thiết kế giải thuật

Mônh c:Phântíchvàthi tk gi ithu t Ch ng1 CÁCKHÁINI M C N B N 4
N i dung 1. Ki u d li u tr u t ng 2. quy 3. Phân tíchgi i thu t 5
1.Ki u d li utr ut ng • Mô t m tc utrúcd li utheocáctácv (operations) làm vi ctrên c utrúc d li uthì ti n l i h n là di n t nó theo nh ng chiti t thi công (implementation details). • Chúngtanêntáchnh ngkháini mv c utrúcd li ura kh i nh ngchiti tthi công. • Khim tc utrúcd li u c nhngh atheocáchnh v ytas cóm tki ud li utr ut ng (abstractdata type) hay ADT. M tki u d li utr u t ng là m tmôhìnhtoán h c icùng v inh ngtác v c nhngh atrên mô hìnhnày. 6
Vàithí d v Ki u d li utr u t ng • M t t p (set)làm tt ph pg mzero hay nhi uph nt . M tph nt không cphépxu thi nnhi uh nm t l ntrongt p. M t t p g m n ph n t cký hi u là {a1, a2, ,an},nh ngv trí c am tph nt trongm tt plà khôngquantr ng. • M t at p(multiset)làm t t pmàtrong ó m t ph n t c phép xu t hi nnhi u h n m t l n.Thí d ,{5,7,5,2} là m t at p. M t a t p có th có nh ngtác v sau: initialize (kh i t o) insert (thêm vào) is_empty (th a t pcór ng) delete (xoá) findmin (tìm ph n t bé nh t) 7
Vàithí d v Ki u d li utr u t ng(tt) • M t chu i (sequence)làm tt ph pcóth t c azero hay nhi uph nt ; cký hi ulà . V trí c a m tph nt trongm tchu i là cóý nghiã.M t chu icóth có nh ngtác v sau: initialize (kh i t o) length (chi u dài) head (ph n t u) tail (ph n uôi) concatenate (ghép k hai chu i) 8
Gi i m t bàitoán b ngADT th y íchl i c aki ud li utr ut ng,th xétbàitoán sau: Cho m t m ng(array) g m n s , A[1 n], hãyxác nh k ph n t l nnh ttrongm ng,v ik n.Thí d , n uA là {5,3, 1, 9, 6}, và k = 3, thì k t qu là {5, 9, 6}. Không d xây d ng m t gi ithu t gi i bàitoántrên. Tath dùngki ud li utr ut ng at p(multiset) v i các tác v : initialize(M), insert(x, M), deleteMin(M), findMin(M) 9
Suy ngh trên a t pM,tacóth vi t m tgi ithu tnh sau: Initialize(M); for i:= 1 to k do Insert(A[i],M); for i:= k+ 1 to n do if A[i]>FindMin(M) then begin DeleteMin(M);Insert(A[i],M) end; Trongthí d trên,tath yki ud li utr ut ng ã làm ngi nhóavi cxây d ng gi ithu tb ngcáchkhông b n tâm nnh ng chiti tthi cônghayhi nth c hóa. 10
Thicông m tki ud li utr ut ng Quá trìnhdùngm tc utrúc d li uc th hi nth chóa m tADT cg ilàthicôngki ud li utr ut ng.Trong s thi công này, ph n d li utr u t ng c hi nth c hóa b ng m t c utrúc d li u c th và ph ncáctác v tr u t ng c hi nth c hóa b ngcáctác v c th h n. Abstract Data Data Structure Operations Concrete operations 11
Thicông m tki u d li utr u t ng(tt.) Có th dùng m ng (array) hay danhsáchliênk t(linkedlist) thicông t ph p(set). Có th dùng m ng (array) hay danhsáchliên k t (linkedlist) thi công chu i. V iki ud li utr ut ng at pnh trongthí d tr c,ta có th dùng hàng icó utiên (priority queue) thi công. Và sau ó tacóth dùng c utrúc d li u heap thi công hàng i có utiên. 12
2. quy H th ctruyh i Thí d 1:Hàmtínhgiaith a N! = N.(N-1)! v iN 1 0!= 1 Nh ng nhngh ahàm quymàch anh ng i s nguyên cg ilành ng h th ctruyh i(recurrencerelation). function factorial(N:integer):integer; begin if N= 0 then factorial:= 1 else factorial:= N*factorial(N-1); end; 13
H th ctruy h i Thí d 2: S Fibonacci H th ctruyh i: FN = FN-1 + FN-2 for N 2 F0 = F1 = 1 1, 1, 2, 3, 5, 8,13, 21, function fibonacci(N: integer): integer; begin if N<= 1 then fibonacci:= 1 else fibonacci:=fibonacci(N-1)+ fibonacci(N-2); end; 14
M tcáchkhác:Tacóth dùngm tm ng ch anh ngtr s itr ctrongkhitínhhàmfibonacci.Tacóm t gi ithu t không quy. procedure fibonacci; const max= 25; var i:integer; F: array[0 max] of integer; begin F[0]:=1; F[1]:=1; for i:=2to max do F[i]:=F[i-1]+ F[i-2] end; 15
Chi nl cChia- -tr Nhi ugi ithu thaycóc utrúc quy: gi i m tv n gi ithu t g i chính nó m thaynhi u l n i phó v i nh ng v n con (subproblem)cóquanh ch tch v i nhau. Nh ng gi ithu t nh v ytuântheo cáchti p c n chia- -tr (divide andconquer): Gi ithu tphânrãv n thànhnh ngv n con, gi i nh ngv n con nàyvàk th pnh ngl igi i c anh ng v n conthànhl igi ichov n nguyênth y. Chi n l c này bao g m 3 b csau ây m i c p quy: phân chia (divide) tr (conquer) k t h p (combine) 16
Thí d : Xétvi cv chnh ngv chcáchnhau1 inchtrên1 câyth c:cóm tnétv cht i i n½inch,nétv chng n h n nh ng o n ¼ inch, nét v ch ng n h nn a nh ng o n1/8inch, v.v procedure rule(l,r,h: integer); /*l:left positionoftheruler;r:right Gi s th t c position mark(x,h) v m t oftheruler*/ v ch h n v t i v var m: integer; trí x. begin if h> 0 then begin m:=(1+r) div 2;mark(m, h); rule(l,m, h-1); rule(m,r , h-1) end; end; 17
Kh quy V n :Gi ithu tkhông quy th ng làm vi c h u hi u và d ki msoát h n1 gi ithu t quy. Làm cáchnào chuy n i m tch ngtrình quy thànhm tch ngtrìnhkhông- -quyt ng ng. Ph ngpháp: Cho m tth t c quyP, m i l ncóm tl nhg i quy nP, giá tr hi nhànhc acácthams vàcácbi nc cb cc tvàocácng nx p(stack) x lý sau. M i l ncóm ts quay v quyv P,giá tr c acác tham s và cácbi n c c b s ckhôiph cl i t cácng n x p. 18
Kh quy(tt.) Vi c i phó v i ach kh h i (return address) cth c hi nnh sau: Gi s th t cPch a m t l nh g i quy t i b c l nh K, a ch kh h i K+1 s cl ut i m tng nx p và s c dùng quay v m cth cthith t cP hi n hành. procedure hanoi(n, beg,aux, end); begin Thí d :Th t c if n= 1 then writeln(beg, end) else hanoi là m tth begin t c quygi i bài hanoi(n-1, beg, end, aux) ; toánThápHàN i writeln(beg, end); hanoi(n-1, aux, beg, end); end end; 19
3:writeln(beg,end); procedure hanoi(n,beg,aux,end: integer); top:= top+1; /*second recursivecall*/ /*StacksSTN,STBEG,STAUX, STN[top]:=n; STEND,andSTADDcorrespond, respectively,tovariablesN,BEG,AUX, STBEG[top]:=beg; ENDandADD*/ STAUX[top]:aux; STEND[top]:=end; label 1,3,5; STADD[top]:=5; var t: integer; /*savingreturnaddress*/ begin n:=n-1; t:=beg;beg:=aux; top:=0; /*preparation forstacks*/ aux:= t; 1; 1: if n=1then goto 5. /* translationofreturnpoint*/ begin writeln(beg,end); goto 5 end; top<>0 top:= top+1; /* firstrecursivecall*/ if then STN[top]:=n;STBEG[top]:=beg; begin STAUX [top]:=aux; n:=STN[top]; beg:=STBEG [top]; STEND [top]:=end; STADD [top]:=3; aux:=STAUX [top]; /*savingreturnaddress*/ end:=STEND [top]; add:=STADD [top]; n:=n-1; t:=aux;aux:=end; end:= t; top:= top – 1; goto add goto 1; end end; 20
S duy tcây quy Cách ngi nnh t duy tcácnúttrongm tcâynh phântheo th t n i là nh m tth t c quynh sau: //duy tth t n i(Inordertraversal) type link=node; node=record info: .; l,r:link end; procedure traverse(t: link); begin if t<> z then /*zisdummy node */ begin traverse(t.l); visit(t); traverse(t.r) end end; 21
Th t cduy tcâyti nth t (Pre-order) procedure traverse(t:link) begin if t<> z then begin visit(t); traverse(t.1);traverse(t.r) end end; Tr ckhikh quyth t cnày,tacóth lo i b l nh g i quyth haid dàngvìkhôngcómãch ngtrình isau nó. L nh g i quyth haicóth cchuy nthànhm tl nh goto nh sau: 22
Kh quy uôi procedure traverse(t:link); label 0,1; begin 0: if t= z thengoto 1; visit(t); traverse(t. l); t:= t.r; goto 0; 1: end; K thu tnày cg i là kh quy uôi (tail-recursion removal). 23
Bâygi ápd ng ph ngphápt ngquát,tacóth kh l nh g i quycònl itrongch ngtrình. procedure traverse(t: link); label 0, 1, 2, 3; begin 0:if t=zthen goto 1; visit(t); push(t); t:= t.l; goto 0; 3:t:= t.r; goto 0; 1: if stack_empty thengoto 2; t:= pop; goto 3; 2: end; Chúý: Doch có m t ach kh h i, 3,màlàc nh,nên takhôngph i nh i nó vàostack. 24
Ta có th lo i b vàiphát bi u goto b ngcáchdùng vòngl p while nh sau. procedure traverse(t: link); label 0,2; begin 0: while t<> z do begin visit(t); push(t.r);t:= t.1; end; if stack_empty thengoto 2; t:=pop; goto 0; 2: end; 25
M tl nn atacóth lo i b hail nh goto cònl i b ngcách dùngvòngl prepeat . procedure traverse(t: link); begin push(t); repeat t:= pop; while t<> z do begin visit(t); push(t.r);t:= t.l; end; until stack_empty; end; 26
Haivòngl pl ngnhaucóth c ngi nhóa nh sau: procedure traverse(t: link); begin push(t); repeat t:= pop; if t<>zthen begin visit(t); push(t.r); push(t.1); end; until stack_empty; end; 27
tránh anh ngcâycon r ngvàostack,tacóth s a ch ngtrìnhtrênthành: procedure traverse(t: link); begin push(t); repeat t:= pop; visit(t); if t.r z then push(t.l); until stack_empty; end; ây là ch ngtrìnhkhông quy hoàn ch nh duy t cây nh phân. 28
Kh hàm quy N uth t c quyPlàm t hàm,ta c n b sung vào qui t c chuy n i t ng quát m t s i msau ây: 1.Ti câu l nh có g n a ch kh h i,ta ph i khôi ph ctr Thí d : Hàmtính t h p hàm t stack;n u c nthì function comb(m,n: int):int thêm l nh s d ngtr hàm If (n=morm= 0) then return 1 này. else 2.Ti câu l nh return,c n a begin a:= comb(n-1,m); vào phátbi u nhtr bi u b:= comb(n-1,m-1); th c ili nsau t khóa return return (a+b); và c ttr hàm tr v này vào end stack. 29
int comb(int n, int m) n= n-1;m=m-1; goto L0; { L2: a=stackF[topF], topF = topF –1; int top, topF; b=stackF[topF],topF=topF –1; int stackN[100]; int stackM[100]; c=a+ b; int stackADD[100]; L3: if (top>0) int stackF[100]; { int a, b, add, c; n=stackN[top]; top= topF = 0; //stack initialize m=stackM[top]; L0: if (m==0|| n ==m) add=stackADD[top]; { c = 1, goto L3;} top= top –1; st else { // 1 recursive call // push theresult top= top+1 ; stackN[top]= n; topF= topF+ 1; stackF[top]= c; stackM[top]=m; if (add== 1) goto L1; stackADD[top]=1; else if (add== 2) goto L2; n= n-1; goto L0; } nd L1:// 2 recursive call return c; top= top+1;stackN[top]= n; } stackM[top]=m; } stackADD[top]=2; 30
3. Phântích ph ct pgi ithu t V i ph nl ncácbàitoán,th ngcónhi u gi ithu tkhác nhau gi i m t bàitoán. Làmcáchnào ch ngi ithu tt tnh t gi i m tbài toán? Làm cáchnào sosánhcácgi ithu tcùnggi i cm t bàitoán? Phântích ph ct pc am tgi ithu t: d oán cáctài nguyênmàgi ithu t ó c n. Tàinguyên: Ch b nh Th igiantínhtoán Th i giantínhtoán là tàinguyênquantr ngnh t. 31
Haicáchphântích Th igiantínhtoánc am tgi ithu tth nglà m thàmc akíchth cd li unh p. Chúngtaquantâm n: Tr ngh ptrungbình (average case):th igian tínhtoánmàm tgi ithu tc n i v i m t “d li unhâpthôngth ng” (typicalinputdata). Tr ngh px unh t (worstcase):th igiantính toán mà m tgi ithu t c n i v i m t “d li u nhâpx unh t” 32
Khungth cc as phântích B c1: ctr nghóad li unh pvàquy t nhki u phântíchthíchh p. Thôngth ng,ta t ptrungvàovi c -ch ngminhr ngth igiantínhtoánluônnh h nm t“c n trên” (upper bound),hay -dnxu trath igianch ytrungbình i v i m td li u nh png unhiên. B c2:nh n d ng thaotáctr u t ng (abstract operation) mà gi ithu td avào ólàmvi c. Thí d :thaotácsosánhtronggi ithu ts pth t . T ngs thaotáctr ut ngth ngtùythu cvàom tvài i l ng. B c3:th chi nphântíchtoánh c tìmracácgiá tr trungbìnhvàgiá tr x unh tc acác i l ng quantr ng. 33
Haitr ng h pphântích • Th ngthì khôngkhó tìmrac ntrênc ath i giantínhtoánc am tgi i thu t. • Nh ngphântíchtr ngh ptrungbìnhth ng òi h im ts phântíchtoánh cc uk , ph ct p. • V nguyênt c, m tgi i thu tcóth cphântích nm tm c chínhxácr tchili.Nh ngtrong th ct ,chúngtath ngch tính c l ng (estimating)màthôi • Tóml i,chúngtatìmki mm t cl ngthô v th i gian tínhtoán c a m tgi i thu t(nh mm c ích phânl p ph ct p). 34
Phân l p ph c t p H uh tcácgi ithu tth ngcóm tthôngs chính, N, s m ud li unh p mà cx lý. Thí d : Kíchth cc am ng(array) c s pth t ho ctìmki m. S nútc am t th . Gi ithu tcóth có th igiantínhtoánt l v i 1.N utácv chính cth cthim tvàil n. th igiantínhtoánlàh ngs . 2.lgN(logarithmic) log2N lgN Gi ithu tt ngch mh ns t ngc aN. 35
3. N (linear) 4.NlgN 5. N2 (quadratic) khi gi ithu t là vòng l p l ng hai 6. N3 (cubic) khi gi ithu t là vòng l p l ng ba 7. 2N m ts gi ithu t có th igianch ylu th a. M tvàigi ithu tkháccóth có th igianch y N3/2, N1/2 ,(lgN)2 36
ph c t ptínhtoán Chúngtat ptrungvàophântíchtr ngh px unh t. Khi phântích, b qua nh ngth as h ngs xác nhs ph thu chàmc ath igiantínhtoán i v ikíchth cd li u nh p. Thí d :Th igiantínhtoánc as pth t b ngph ngpháp tr n(mergesort )làt l v i NlgN. Khái ni m “t l v i” (proportionalto) Côngc toánh c làmchínhxáckháini mnàylà ký hi u – O (O-notation). nhngh a: M t hàmg(N) c g ilàO(f(N)) n ut nt ihai h ngs c0vàN0saochog(N) nh h nc0f(N) v i m i N > N0. 37
Ký hi uO Kýhi uOlàm tcách h u ích phátbi u c ntrên v th i giantínhtoánmà c l p i v i ctính d li u nh p và chiti t hi nth c hóa. Chúngtac g ngtìmc “c ntrên” l n “c n d i” c ath i giantínhtoántrongphântíchtr ng h px unh t. Nh ng c n d i(lower-bound )thì th ngkhó xác nh. 38
Phântíchtr ngh ptrungbình V i ki uphântíchnày, taph i - ctr nghóad li unh pc agi i thu t -tínhgiá tr trungbìnhc as l nm tphátbi u c th cthi. -tínhth igian tính toán trungbình c atoàngi i thu t. Nh ngth ngthì khó -xác nhth igianch yc am i phát bi u. - c tr nghóachínhxác d li u nh ptrongth ct . 39
Cáck tqu ti mc nvàx px Ktqu c am ts phântíchtoánh cth ngmangtínhx p x (approximate): nó có th là m tbi uth cg mm tchu i nh ngs h nggi md nt mquantr ng. Tath ng ý n cács h ngd n utrongbi uth ctoán h c. Thí d :Th igiantínhtoántrung bìnhc am tch ngtrình là: a0NlgN+ a1N + a2 Ta có th vi tl ilà: a0NlgN+O(N) V iN l n,takhôngc ntìmgiá tr c aa1hay a2. 40
Cáck tqu x px Kýhi uOchotam tcáchtìmrak tqu x px khiN l n. Do ó, thôngth ngchúngtacóth b qua m t s i l ngkhicót nt i m ts h ng d n u trongbi u th c. Example: n u bi uth clàN(N-1)/2,chúngtacóth b o r ngnókho ngch ngN2/2. 41
Phântích m t gi ithu t l p Thí d 1 Cho m t gi ithu ttìmph n t l n nh ttrong m t m ng1 chi u. procedure MAX(A,n,max) /*SetmaxtothemaximumofA(1:n)*/ begin integeri,n; max:=A[1]; for i:=2to n do if A[i]>max then max:=A[i] end N uC(n) là ph c t ptínhtoán c a gi ithu t ctính theothaotácsosánh (A[i]>max).Hãyxác nh C(n) trongtr ng h p x u nh t. 42
Phântích m tgi ithu t l p(tt.) Thaotác c n b n c ath t cMAXlàthaotácsosánh. T ng s thaotácsosánh c ath t c MAX chínhlàs l n thân vòng l p cth cthi: (n-1). V y ph c t ptínhtoán c agi ithu t là O(n). ây là ph c t p c a c hai tr ng h ptrungbình và x u nh t. Ghichú: N uthaotác c n b nlàphátbi ugán(max:= A[i]) thì O(n)là ph c t ptrongtr ng h p x u nh t. 43
Phântích m tgi ithu t l p(tt.) Thí d 2:Gi ithu tki mtraxem có ph i m iph n t trong m ng 1chi u là khác bi tnhau. function UniqueElements(A, n) begin for i:=1to n –1 do for j:= i+ 1 to n do if A[i]= A[j] returnfalse returntrue end Trongtr ng h p x u nh t, m ngkhông h có hai ph n t nào b ngnhau ho c m ngcóhai ph n t cu i cùng b ng nhau.Lúc óm t s sosánh di n ra m ikhithânvòng l p trong cth chi n. 44
i= 1 j ch y t 2cho n n t cn–1 l nsosánh i= 2 j ch y t 3cho nn t c n – 2 l nsosánh . . i= n -2 jch y t n-1 cho nn t c2l nsosánh i= n -1 jch y t n cho nn t c1 l nsosánh Tóm l i, t ng s l nsosánhlà: 1 + 2+3+ +(n-2)+(n-1) =n(n-1)/2 V y ph c t ptínhtoán c agi ithu ttrongtr ng h p x u nh tlàO(n2). 45
Phântích m tgi ithu t l p(tt.) Thí d 3 (Sotrùngdòngký t -stringmatching):Tìm t t c nh ng s xu t hi n c a m tkhuôn m u(pattern)trong m t v n b n(text). V n b nlàm tm ngT[1 n] g m n ký t và ki um ulàm t m ngP[1 m] g m m ký t . Ki um uPxu thi nv i dchchuy n (shift) s trongv n b nT(t clà,Pxu thi nb t ut v trí s+1 trong v n b n T) n u 1 s n – m và T[s+1 s+m]=P[1 m]. 46
M tgi ithu t ngi n nh t tìm t t c nh ng s xu t hi n c aPtrongTs dùng m tvòng l pmàki mtra i u ki nP[1 m]=T[s+1 s+m]v i m itr trong n – m+ 1 tr có th có c a s. procedure NATIVE-STRING-MATCHING(T,P); begin n:=|T|; m:=|P|; for s:= 0 to n – m do if P[1 m]=T[s+1, ,s+m] then print “Patternoccurs withshift” s; end 47
procedure NATIVE-STRING-MATCHING(T,P); begin n:=|T|; m:=|P|; for s:= 0 to n – m do begin exit:=false; k:=1; while k m and not exit do if P[k] T[s+k] then exit:=true else k:=k+1; if not exit then print “Patternoccurs withshift” s; end end 48
Gi ithu tNAIVESTRINGMATCHERcóhai vòngl pl ngnhau: - vòng l pngoàil pn–m + 1 l n. - vòng l ptrongl pt i aml n. Do ó, ph ct pc agi ithu ttrongtr ng h p x unh tlà: O((n – m + 1)m). 49
Phântíchgi ithu t quy:cáccôngth ctruy h i c nb n Cóm tph ngphápc nb n phântích ph ct pc a cácgi ithu t quy. Tínhch tc am tgi ithu t quy th igianch y i v i b d li unh pkíchth cNtùythu cvàoth igian ch yc anh ngb d li unh pnh h n. Tínhch tnày cmôt b ngm tcôngth ctoánh c c g ilàh th ctruyh i(recurrencerelation). d nxu tra ph c t p c a m tgi ithu t quy, chúng ta ph i gi i h th ctruy h i này. 50
Phântíchgi ithu t quy b ngph ngphápl p Côngth c1: M tch ngtrình quymàl pqua b d li u nh p lo i i m tph nt . H th ctruy h i c anó nh sau: CN = CN-1 +N N 2 C1= 1 Cáchsuyra ph c CN = CN-1 + N t p b ngph ng = C +(N – 1)+ N pháp l p: N-2 = CN-3 +(N – 2)+(N – 1)+ N . . . = C1 + 2 + +(N – 2)+(N – 1)+ N = 1+ 2 + +(N – 1)+ N =N(N-1)/2 = N2/2 51
Thí d 2 Côngth c 2: M tch ngtrình quymàtách ôib d li unh ptrongm tb clàmvi c. H th ctruyh ilà: CN= CN/2 + 1 N 2 C1 = 0 Cáchsuyra ph c t p: Gi s N= 2n C(2n) = C(2n-1) + 1 =C(2n-2 )+1+1 =C(2n-3 )+ 3 . . . =C(20 )+ n = C1 +n= n CN =n =lgN CN lgN 52
Thí d 3 Công th c3. M tch ng trình quy mà tách ôi b d li u nh p trong m t b clàmvi cnh ngph ixemxétt ngph nt trongd li unh p. H th c truy h ilà CN=2CN/2 +N for N 2 C1 = 0 Cáchsuyra ph c t p: Assume N= 2n C(2n)= 2C(2n-1)+ 2n C(2n)/2n = C(2n-1)/ 2n-1 + 1 =C(2n-2)/ 2n-2 + 1 +1 . . = n C(2n )= n.2n CN =NlgN CN NlgN 53
Thí d 4 Côngth c4.M tch ng trình quy mà tách ôi d li unh p thànhhai n a trong m t b clàmvi c. H th c truy h ilà C(N) =2C(N/2)+ 1 for N 2 C(1)= 0 Cáchsuyra ph c t p: Gi s N= 2n. C(2n)=2C(2n-1)+ 1 C(2n)/ 2n =2C(2n-1)/ 2n +1/2n =C(2n-1)/ 2n-1 +1/2n =[C(2n-2)/ 2n-2 + 1/2n-1 ]+1/2n . . . =C(2n-i)/ 2n-i + 1/2n – i +1+ +1/2n 54
Cu icùng,khii= n -1, ta c: C(2n)/2n = C(2)/2+¼+1/8+ +1/2n = ½ + ¼ + .+1/2n 1 C(2n)= 2n C(N) N M ts h th ctruyh icóv gi ngnhaunh ngm c khó khigi ichúng tìm ph c t pthì có th r t khácnhau. 55
Nguyên t cphântích ph c t ptrungbình tính ph c t p trungbình c a m tgi i thu tA,taph ilàm m t s b c: 1.Quy t nh m t khônggian l y m u (samplingspace) di n t nh ng d li u uvào(kích th cn)cóth có.Gi s không gian l y m ulàS ={ I1, I2, ,Ik} 2.Taph i nhngh a m tphân b xácxu t p trênSmàbi udi n m c ch cch n mà d li u uvào ócóth x yra. 3.Taph i tính t ng s tác v c n b n cgi i thu tAth chi n x lý m t tr ng h p m u.Tadùngv(Ik)kýhi u t ng s tác v c th chi n b iAkhi d li u uvào thu c tr ng h p Ik. 56
Phântích ph c t ptrungbình(tt.) 4.Ta tính tr trungbình c a s tác v c n b n b ngcách tính k v ngsau: Cavg(n)=v(I1).p(I1)+v(I2).p(I2)+ +v(Ik).p(Ik). Thí d :Cho m t m ngAcónph n t .Tìmki m v trí mà tr Xxu t hi ntrong m ngA. begin i:=1; while i A[i] do i:=i+1; end 57
Thí d :Tìmki mtu n t Gi s Xcóxu thi ntrongm ngvàgi nh r ngxácxu t nó xu thi nt i m tv trí b tk trongm ng là unhau và xácxu t m itr ngh px y ra là p=1/n. S l nsosánh tìmth y X n u nó xu t hi n t i v trí 1 là 1 S l nsosánh tìmth yXn u nó xu t hi n t i v trí 2 là 2 S l nsosánh tìmth yXn u nó xu t hi n t i v trí n là n T ng s tác v sosánhtrungbình là: C(n)= 1.(1/n)+ 2.(1/n)+ +N.(1/n) =(1 + 2+ +n).(1/n) =(1+2+ +n)/n= n(n+1)/2.(1/n)=(n+1)/2. 58
Vàichu i s thông d ng Có m tvàichu i s thôngd ngtrongvi cphântích ph ct pgi ithu t. Chu i s c ng S1 =1+ 2+ 3+ + n 2 S1 =n(n+1)/2 n /2 2 2 2 S2 =1+ 2 + 3 + + n 3 S2 =n(n+1)(2n+1)/6 n /3 Chu i s nhân S = 1+ a+ a2 + a3 + + an S = (an+1 -1)/(a-1) If0< a<1,then S 1/(1-a) Và khi n , S ti n v 1/(1-a). 59
Vàichu i s thông d ng(tt.) T ngchu i s i uhoà (Harmonicsum) Hn =1+½+1/3+¼+ +1/n Hn =loge n+ 0.577215665 c g ilàh ng s Euler. M tchu i s khácc ngr tthôngd ngkhiphântíchcác thao táclàmvi ctrêncâynh phân: 1+2+4+ + 2m-1 = 2m -1 60
Ch ng 2 Phântích ph c t p c a m t s gi ithu t s pth t và tìmki m 1
N idung 1. Vàiph ngpháp s pth t c n b n 2. Quicksort 3. X pth t d a vào c s 4. X pth t b ngph ngpháptr n 5. X pth t ngo i 6. Vàiph ngpháptìmki m c n b n 2
Nguyên t c v s pth t Xét nh ngph ng pháp s pth t m t t ptin g mcác m utin (record)cóch a khóa (key).Khóamàlàm tph n c a m utin, c dùng i u khi n vi c s pth t . M ctiêu: s p x p các m utinsao cho cáctr khóa c a chúng có th t theo m t quilu tth t nào ó. N u các t ptin c s pth t có th ch atrong b nh chínhthì gi ithu t s pth t c g i là s p th t n i (internalsorting). Vi c s pth t t ptin l u b nh ph c g i là s p th t ngo i (externalsorting). 3
Hainhómph ngpháp s pth t Chúngtaquantâm nth igiantínhtoán c a các gi ithu t s pth t . 1.M tnhóm g m 4ph ngpháp c n b n òi h i th i giantínhtoán t l v i N2 s pth t N ph n t . 2.Cácph ngpháp tiênti n h n có th s pth t N ph n t trongth igian ch y t l v iNlgN. M t ctính c a ph ng pháp s pth t là tính n nh (stability). M t ph ng pháp s pth t c g i là n nh khi nó b otoàn cth t t ng i c acác ph n t cùngtr khóatrong t ptin. 4
1.Nhómph ngpháp c n b n V inhómnày,cóhaiph ngpháp s pth t c ch n kh osát: -s pth t b ngph ngpháp ch n (selectionsort) -s pth t b ngph ngpháp chèn (insertionsort) V i m c ích t ptrungvàokhía c nhgi ithu t,ta s làmvi c v icácph ngpháp mà nó ch s pth t các m ng s nguyêntheoth t l n d n c a s . 5
S pth t b ngph ngphápch n Ý t ng: “Tr ctiêntìm ph n t nh nh ttrong m ng và hoán i nó v i ph n t ang v trí th nh ttrong m ng,vàr i tìm ph n t nh th nhì trong m ng và hoán inóv i ph n t ang v trí th nhì trong m ng, và c th cho nkhitoàn m ng ã c s pth t .” 390 45 45 45 45 205 205 182 182 182 182 182 205 205 205 45 390 390 390 235 235 235 235 235 390 6
Gi ithu t s pth t b ngph ngphápch n procedure selection; var i,j,min, t:integer; begin for i:=1 to N-1 do begin min :=i; for j:=i+1 to N do if a[j]<a[min] then min :=j; t:=a[min];a[min]:=a[i]; a[i] :=t; end; end; 7
Phântích ph c t p c aselectionsort Vòng l ptrong(tác v sosánh) cth chi n v i t ng s l nnh sau: (N-1)+(N-2)+ +1=N(N-1)/2 =O(N2) Vòng l pngoài cth cthiN-1 l n. Tính ch t1.1: Selectionsort th c thikho ngNhoán v và N2/2sosánh. Ghi chú:Th igiantínhtoán c aselectionsortthì c l p i v i d li unh p. 8
S pth t b ngph ngphápchèn Ý t ng : Gi ithu t xemxét t ng ph n t m t, chèn nó vào v trí úng c a nó trong nhóm các ph n t ã c s pth t r i. 390 205 182 45 45 205 390 205 182 182 182 182 390 205 205 45 45 45 390 235 235 235 235 235 390 9
Gi ithu t s pth t b ngph ngphápchèn procedure insertion; var i;j;v:integer; begin for i:=2 to N do begin v:=a[i];j:=i; while a[j-1]> v do begin a[j]:= a[j-1];//pulldown j:=j-1 end; a[j]:=v; end; end; 10
Nh ng l ý v gi ithu t insertionsort 1.Chúngtadùng m ttr khóa “c m canh” (sentinel) t i a[0],làmcho nó nh h n ph n t nh nh ttrong m ng. 2. Vòng l p ngoài c a gi ithu t cth cthi N-1 l n. Tr ng h p x u nh t x y rakhi m ng ã có th t o ng c.Khi ó, vòng l ptrong cth cthi v i t ng s l nsau ây: (N-1)+(N-2)+ + 1=N(N-1)/2 =O(N2) S b c chuy n= N(N-1)/2 S sosánh= N(N-1)/2 3.Trung bình có kho ng ch ng(i-1)/2sosánh cth c thitrong vòng l ptrong. Do ó,trongtr ng h p trung bình, t ng s l nsosánh là: (N-1)/2+(N-2)/2 + +1/2 =N(N-1)/4 =O(N2) 11
ph c t p c a s pth t b ngph ngpháp ch nvàph ngphápchèn Tính ch t1.2: S pth t b ngph ngphápch n th cthikho ng N2/2sosánh và N2/4hoán v trong tr ng h p x unh t. Tính ch t1.3: S pth t b ngph ngphápchèn th cthikho ng N2/4sosánh và N2/8hoán v trong tr ng h p trungbình. Tính ch t1.4: S pth t b ngph ngphápchèncó ph c t ptuy ntính i v i m t m ng ã g ncó th t . 12
2.Gi ithu tQuicksort Gi ithu t c n b n c a Quicksort c phátminh n m 1960 b i C. A. R. Hoare. Quicksort c achu ng vì nó không quá khó hi n th c hóa. Quicksort ch òi h i kho ng ch ng NlgN thaotác c n b n s pth t N ph n t . Nh c i m c aQuicksort g m: -Nólàm t gi ithu t quy -Nóc n kho ng N2 thaotác c n b ntrongtr ng h p x u nh t -Nód b l ikhi l ptrình(fragile). 13
Gi ithu t c n b n c aQuicksort Quicksortlàm t ph ng pháp x pth t theoki u “chia tr ”. Nó th chi n b ng cách phân ho ch m t t ptin thành haiph n và s pth t m i ph n m t cách c l p v i nhau. Gi ithu tcóc utrúc nh sau: procedure quicksort1(left,right:integer); var i: integer; begin if right>left then begin i:=partition(left,right); quicksort(left,i-1); quicksort(i+1,right); end; end; 14
Phânho ch Ph nthench t c aQuicksort là th t cphân ho ch (partition),màs p x p l i m ngsao choth amãn 3 i u ki nsau: i) ph n t a[i] c a v v trí úng n c a nó, v i m t giá tr i nào ó, ii) t t c nh ng ph n t trongnhóm a[left], , a[i-1] thì nh h n hay b ng a[i] iii) t t c nh ng ph n t trongnhóm a[i+1], , a[right] thì l n h n hay b ng a[i] Example: 53 59 56 52 55 58 51 57 54 52 51 53 56 55 58 59 57 54 15
Thí d v phânho ch Gi s chúngta ch nph n t th nh t hay ph n t t n cùng trái (leftmost )nh là ph n t s c a v v trí úng c a nó (Ph n t này c g ilàph n t ch t - pivot). 40 15302560107545653550207055 40 15302520107545653550607055 40 15302520103545657550607055 35 15 302520104045657550607055 nh h n40 sorted l n h n40 16
Gi ithu tQuicksort procedure quicksort2(left, right:integer); var j,k:integer; begin if right>left then begin j:=left;k:=right+1; //startpartitioning repeat repeatj:=j+1 until a[j] >=a[left]; repeat k:=k-1 until a[k] k; swap(a[left],a[k]);//finishpartitioning quicksort2(left,k-1); quicksort2(k+1,right) end; end; 17
Phântích ph c t p:tr ng h p t tnh t Tr ng h p t t nh t x y ra v iQuicksortlàkhi m i l n phân ho ch chia t ptin ralàmhai ph n b ng nhau. i u nàylàm cho s l nsosánh c a Quicksortth amãnh th ctruy h i: CN =2CN/2 + N. S h nh2CN/2 là chiphí c avi c s pth t hai n a t ptin và N là chiphí c avi cxét t ng ph n t khi phân ho ch l n u. T ch ng1, vi cgi i h th ctruy h i này ã a n l i gi i: CN N lgN. 18
Phântích ph c t p:tr ng h p x unh t M ttr ng h p x unh t c a Quicksort là khi t ptin ã có th t r i. Khi ó, ph n t th nh t s òi h i n sosánh nh n ra r ng nó nên úng v trí th nh t. H n n a,sau ó phân o n bên tráilàr ngvàvà phân o n bênph i g mn–1 ph n t .Do ó v i l n phân ho ch k , ph n t th hai s òi h i n-1 sosánh nh n ra r ng nó nên úng v trí th hai. Và c ti p t c nh th . Nh v y t ng s l nsosánh s là: n +(n-1)+ +2 +1 = n(n+1)/2 = (n2 +n)/2=O(n2). ph c t ptr ng h p x u nh t c aQuicksort là O(n2). 19
ph c t ptr ng h ptrungbình c aQuicksort Côngth ctruy h i chínhxác cho t ng s sosánhmàQuick sort c n s pth t N ph n t c hìnhthành m tcách ng u nhiên: N CN =(N+1) +(1/N) (Ck-1 + CN-k) 1 v iN 2 và C1 = C0 = 0 S h ng(N+1) bao g m s l nsosánh ph n t ch t v i t ng ph n t khác,thêmhai l nsosánh haipointergiaonhau. Ph n còn l ilàdo s ki n m iph n t v trí k có cùngxác xu t 1/N c làm ph n t ch t mà sau ó chúngta có hai phân o n v i s ph n t l n l t là k-1 và N-k. 20
Chúý r ng, C0 + C1 + + CN-1 thì gi ng h t CN-1 + CN-2 + + C0,nênta có N CN =(N+1) + (1/N) 2Ck-1 1 Ta có th lo itr i l ngtính t ng b ngcách nhân c hai v v i N và r itr cho cùng côngth c nhân v i N-1: NCN – (N-1) CN-1 = N(N+1) – (N-1)N + 2CN-1 T ó ta c NCN =(N+1)CN-1 + 2N 21
Chia c hai v v i N(N+1)ta c h th ctruy h i: CN/(N+1)= CN-1/N+2/(N+1) = CN-2 /(N-1)+2/N+2/(N+1) . . N = C2 /3+ 2/(k+1) 3 N N CN/(N+1) 2 1/k 2 1/xdx = 2lnN 1 1 Suy ra: CN 2NlnN 22
ph c t ptr ng h ptrungbình c a Quicksort(tt.) Vì tacó: lnN= (log2N).(loge2)=0.69lgN 2NlnN 1.38 NlgN. T ng s sosánh trungbình c aQuicksortch kho ng ch ng38%cao h n trong tr ng h p t tnh t. M nh . Quicksort c nkho ng2NlnNsosánhtrong tr ng h ptrungbình. 23
Kh quygi ithu tQuicksort Dùng ng n x p (stack)tacóth chuy nQuicksortthành m t gi ithu t không quy procedure quicksort3; begin push(left); push(i-1); var t, i, left,right : integer; left := i+1 end begin else left :=1;right:= N; begin stackinit; push(i+1);push(right); push(left); push(right); right:=i-1 repeat end; if right>left then end begin else i=: partition(left,right); begin right := pop; left := pop if (i –left)>(right –i) then end; until stackempty; end; 24
3. S pth t d avào c s Trong nhi u ng d ng, cáctr khóa có th là nh ngkhóa thu c m t t m h n nh nào ó. Các ph ng pháp s pth t mà l i d ngtínhch t s c a cáckhóa c g i là s p th t d a vào c s (radixsort). Nh ng ph ng pháp này không ch sosánh các tr khóa chúng x lý và sosánh các ph n c akhóa. S pth t d a vào c s coi cáctr khóa nh là nh ng s c bi udi n d ng h c s M và làm vi c v i t ngký s (digit) n l . V i h u h t m imáytính,th tti n l i làmvi c v i c s 2 (M=2), h n là c s th p phân(M=10). 25
Bit Cho m tkhóa cdi n t d i d ng m t s nh phân, m ttác v c nthi tlàtrích các t p bit k nhau t m t s . V I ngônng máy,các bit ctrích t s nh phânnh cáctác v nh “and” và“shift” trên các bit. Thí d : Ta có th trích hai bit u c a m t s 10bit b ng cách dùngtác v “shiftright”(d chsang ph i)8 bit r ith c hi ntác v “and” t ng bit v i m t n 0000000011. Trong ngôn ng Pascal, nh ngtác v trêncóth c gi l p b nghaitác v div và mod. 26
Làmvi ctrênbit Hai bit u c a m t s m i bit ctrích b i:(x div 256) mod 4. “d ch s x sang ph i k v trí bit” cth chi n b i: x div 2k “gánzero t t c tr j bit t n cùng ph i “ cth c hi n b i: (x div 2 k)mod 2j Trong gi ithu t s pth t d avào c s ,gi s ã t n t i hàm bits(x,k,j:integer):integer mà tr v j bitxu t hi n cách k bit k t m c bên ph itrong s x. 27
Gi ithu t s pth t hoán v c s Ph ng pháp c n b n c a gi ithu t s pth t hoán v c s (exchange radixsort)làxemxét t ngbit c atr khóa t trái sang ph i. Ý t ng: K t qu c a s sosánh gi ahaitr khóa ch tùy thu c vàogiá tr c a t ngbit t i v trí utiênmàchúng khác nhau ( c t tráisang ph i). 28
S pth t hoán v c s S pth t hoán v c s (RadixExchange Sort) Vi c s pth t t ptin cth c hi ntheo m tcáchgi ng nh thaotác phân ho chtrongQuicksort. duy t t tráisangph i tìmtr khóamàb t u b ng bit 1, duy t t ph isangtrái tìmtr khóamàb t u b ng bit 0, hoán v haitr khóa này, và ti p t c quá trình này cho nkhi hai con tr giao nhau. 29
procedure radix_exchange(1,r,b: integer); var t,i,j:integer; begin if (r>1)and(b>=0) then begin i:=1;j:=r; repeat while (bits(a[i], b, 1)=0) and (i<j) do i:=i+1; while (bits(a[j], b, 1)=1) and (i<j) do j:=j-1; swap(a[i],a[j]); until j=i; if bits(a[r], b, 1)= 0 then j:=j+1 ; radix_exchange(1, j-1, b-1);radix_exchange(j,r,b-1); end end; 30
S pth t hoán v c s (tt.) Gi s m ng a[1 N]ch a các s nguyên d ng nh h n232 (saocho chúng có th c di n t thànhcác s nh phân 31- bit). Thì l nh g i radix_echange(1,N,30) s s pth t c cho dãy. Bi n b theo dõi các bit t bitth 30(t n cùngtrái)cho n bit th 0(t ncùng ph i). Hình v sau âyminh h a s phân ho chtheobi udi n nh phân c acáctr khóa. M t phépmã hóa 5 bit cdùng cho khóa. 31
A00001 A 0 0001 A0 0 001 A00 0 01 A000 0 1 A0000 1 S 10011 E 0 0101 E0 0 101 A00 0 01 A000 0 1 A0000 1 O01111 O 0 1111 A0 0 001 E00 1 01 E001 0 1 E0010 1 R10010 L 0 1100 E0 0 101 E00 1 01 E001 0 1 E0010 1 T10100 M 0 1101 G0 0 111 G00 1 11 G001 1 1 G I 01001 I 0 1001 I 0 1 001 I 01 0 01 I I N01110 N 0 1110 N0 1 110 N01 1 10 L011 0 0 L0110 0 G00111 G 0 0111 M0 1 101 M01 1 01 M011 0 1 M0110 1 E00101 E 0 0101 L0 1 100 L01 1 00 N011 1 0 N0111 0 X11000 A 0 0001 O0 1 111 O01 1 11 O011 1 1 O0111 1 A00001 X 1 1000 S 1 0 011 S10 0 11 P100 0 0 P M01101 T 1 0100 T1 0 100 R10 0 10 R100 1 0 R1001 0 P10000 P 1 0000 P1 0 000 P10 0 00 S100 1 1 S1001 1 L01100 R 1 0010 R1 0 010 T 10 1 00 T T E00101 S 1 0011 X1 1 000 X X X Hình3.3.1 S pth t hoán v c s 32
ph c t p c a s pth t d avào c s Th i giantínhtoán c a s pth t hoán v c s s pth t N m utinlàNb. M tkhác,ta có th coith igiantínhtoán b ng v iNlgN vì n u cáctr khóakhácbi tnhauthì b ít nh t ph ilàlgN. Tính ch t3.1: S pth t d a vào c s c n trungbình kho ng NlgN s sosánh bit. N ukíchth c c a m nglàl yth a c a2 và các bit là ng u nhiên,thì chúngta k v ng r ng m t n anh ng bit u có tr là 0 và m t n a có tr là 1. Do ó h th ctruy h ilà: CN= 2CN/2 + N. Trong gi ithu t s pth t hoán v c s , s phân ho ch th ng d ph mvitrungtâm h n là trong inQuicksort. 33
4. S pth t b ngcáchtr n(mergesort) Tr c tiên,chúngtaxét m tquá trình c g ilàtr n (merging), thao tácph i h phai t p tin ã có th t thành m t t p tincóth t l n h n. Tr n Trongnhi u ng d ng x lý d li u, ta ph iduytrì m t t p d li ucóth t khá l n.Cácph n t m i th ngxuyên c thêmvào t p tin l n. Nhómcácph n t c ínhvào uôi c a t p tin l n và toàn b t p tin c s pth t tr l i. Tình hu ng ó r t thích h pcho thaotáctr n. 34
Tr n Gi s tacóhai m ng s nguyêncóth t a[1 M] và b[1 N].Tamu ntr n chúng thành m t m ngth ba c[1 M+N]. i:=1;j:=1; for k:= 1 to M+N do if a[i]< b[j] then begin c[k]:= a[i];i:=i+1 end else begin c[k]:= b[j]; j :=j+1 end; Ghichú: Gi ithu tdùng a[M+1] và b[N+1] làmph n t c m canh ch a haigiá tr l n h n m itr khóakhác. Nh chúng,khi m ttrong hai m ng ã c nthì vòng l p s a ph ncòn l i c a m ngcòn l i vào m ng c. 35
S pth t b ngph ngpháptr n M tkhita ã có th t ctr n,tadùng nó làm c s xây d ng m tth t c s pth t quy. s pth t m t t ptin nào ó,ta chiathành hai o n b ng nhau, s pth t hai o n này m t cách quyvàr i tr n hai o n l i v inhau. Gi ithu tsau s pth t m ng a[1 r], dùng m ng b[1 r] làmtrunggian, 36
procedure mergesort(1,r:integer); var i,j, k,m : integer; begin if r-1>0 then begin m:=(r+1)/2;mergesort(1,m);mergesort(m+1,r); for i:=mdownto 1 do b[i]:=a[j]; for j:=m+1 to r do b[r+m+1-j] :=a[j]; for k :=1 to r do if b[i]<b[j] then begin a[k]:= b[i] ;i :=i+1 end else begin a[k]:= b[j];j:=j-1 end; end; end; 37
ASORT INGEXAMPL E Thí d : S pth t m t A S m ng g mnh ngký t O R ch AOR S I T G N G IN T AG INORS T E X A M AEM X LP EL P AEELMP X AAEEGILMNOPRST X 38
ph c t p c a gi ithu tMergesort Tínhch t4.1: S pth t b ngph ngpháptr n c n kho ng NlgNsosánh s p b t k t ptinNph n t nào. i v igi i thu tmergesort quy, s l nsosánh c mô t b ng h th ctruy h i: CN =2CN/2 + N, v i C1 =0. Suyra: CN Nlg N Tínhch t4.2: S pth t b ngph ngpháptr n c n dùngch b nh thêm t l v I N. Ghichú:Mergesort thì n nh(stable)trongkhi Quicksort thì không n nh. 39
5. S pth t ngo i S pth t các t ptin l n l utr trên b nh ph c g ilà s p th t ngo i (externalsorting). S pth t ngo i r tquantr ngtrong các h qu ntr c s d li u(DBMSs). Kh i(block) và truy tkh i(Block Access) H i u hành phân chia b nh ph thànhnh ng kh i có kíchth c b ng nhau. Kíchth c c akh ithay itùytheo h i u hành, nh ngth ng kho ng 512 n 4096 byte. Cáctác v c n b ntrên các t ptin là - mang m tkh ira b m b nh chính (read) - mang m tkh i t b nh chính v b nh ph (write). 40
S pth t ngo i Khi c l ngth i giantínhtoán c a cácgi ithu tmàlàm vi ctrêncác t ptin,chúngtaph ixét s l nmàchúngta c m tkh ira b nh chính hay vi t m tkh i v b nh ph . M ttác v nh v y c g i là m t truy tkh i (block access) hay m t truy t a (disk access). kh i = trang(page) 41
X pth t ngo i b ngp.p.tr n(External Sort- merge) K thu tthông d ngnh t s pth t ngo ilàgi ithu t s pth t ngo i b ng ph ngpháptr n (externalsort-merge algorithm) . Ph ng pháp s pth t ngo i này g m 2 b c: - t o các run - tr nrun M: s trang (page) c a b m trong b nh chính(memory- buffer) . 42
X pth t ngo i b ngp.p.tr n(tt.) 1.Trong b c 1, m t s run có th t c t o ra b ng cách sau: i= 0; repeat readMblocks ofthefile,ortherest ofthefile, whicheveris smaller; sortthein-memory part ofthefile; writethesorteddata totherunfile Ri; i= i+1; until theend ofthefile. 2.Trong b c 2, cácrun c tr n l i. 43
Tr nrun Tr ng h p c bi t: Gi s s run, N, N < M.Ta có th dành 1trang c a b m cho m i run và dành ch b nh còn l i ch a m ttrang c a k t qu xu t ra.Gi ithu tph ntr nrun nh sau: readoneblock ofeach ofthe N files Ri into abufferpagein memory; repeat choosethefirstrecord(insortorder) among all bufferpages; writethetupleto theoutput, anddeleteitfrom the bufferpage; if the bufferpageofanyrun Ri is empty and not end-of-file(Ri) then readthenextblock of Ri into thebuffer page; until allbufferpages are empty. 44
Tr nrun(tr ng h p t ngquát) Tác v tr n là s khái quáthóa c a phép tr n hai ng (two-way merge) cdùng b igi ithu t s pth t n i b ng ph ng pháp tr n. Nó tr n N run,do ó nó c g i là tr n nhi u ng (n-waymerge). Tr ng h p t ngquát: V t ng quát, n u t ptin l n h n s c ch a c a b m N>M thì khôngth dành m ttrangtrong b m cho m irun trong b ctr n.Trongtr ng h p này, s tr n ph itr i qua nhi u chuy n (passes). Vì ch có M-1trang c a b m dành cho các u vào, s tr n có th ti p nh n M-1 runsnh là các u vào. 45
Tr nrun[tr ng h p t ngquát](tt.) Chuy ntr n utiên làm vi cnh sau: M-1 run utiên ctr n l ithành m t run chochuy n k ti p. R ithì M-1 runs s ctr ntheocách t ng t và c th cho nkhi t t c các run utiên u cgi iquy t. T i i m này, t ng s run cgi m i m t th a s M-1. N u s run ã c gi m inày v n còn M, m t chuy n n a s cth cthi v i các run c t ora b i chuy n u tiênlàm u vào. M ichuy n làmgi m t ng s run m tth a s M – 1.Các chuy n c l p l i nhi u nh c nthi t cho nkhi t ng s run nh h n M; chuy n cu i cùng s t o ra k t qu là m t t ptin có th t . 46
M tthí d c ath t ngo i b ngp.p.tr n Gi s : i) m t m u tinchi m v a m t kh i ii) b mchi m 3 trang. Tronggiai o n tr n, hai trang cdùnglàm uvào vàm t trang cdùng ch a k tqu . Giai o ntr n òi h i haichuy n. 47
a 19 d 31 a 19 g 24 g 24 b 14 a 14 a 19 c 33 a 19 d 31 b 14 d 31 b 14 c 33 c 33 e 16 c 33 b 14 e 16 g 24 d 7 e 16 d 21 r 16 d 31 a 14 d 31 d 21 m 3 d 7 e 16 m 3 r 16 d 21 g 24 p 2 m 3 m 3 d 7 a 14 p 2 p 2 a 14 d 17 r 16 r 16 p 2 T orun tr npass-1 tr npass-1 48
ph c t p c a x pth t ngo i Hãytính s truy t kh i (block accesses) c a gi ithu t s p th t ngo i b ng ph ng pháptr n. br : t ng s kh i c a t ptin. Trong giai o n t o run, m tkh i c c và ghi, em l i m t t ng s 2br,truy tkh i. T ng s run ban ulà br/M. T ng s chuy ntr n: log M-1(br/M) Trong m ichuy ntr n, t ngkh i c a t ptin c c m t l n và ghi m t l n. 49
ph c t p c a x pth t ngo i(tt) T ng s truy t acho gi ithu t s pth t ngo i b ng ph ng pháptr nlà: 2br +2br logM-1(br/M) = 2br( logM-1 (br/M) +1) t o run các chuy ntr n 50
6.Tìmki mtu n t Ph ng pháp n gi n nh t tìmki mlà l utr các m u tintrong m t m ng,và tìmki m m t m utin, duy t qua toàn b m ng m t cáchtu n t . type node=record key,info: integer end; var a: array [0 maxN] of node; N: integer; procedure initialize; begin N:=0end; function seq_search(v: integer,x: integer): integer; begin a[N+1].key:=v; /*sentinel*/ if x<= N then repeat x:=x+ 1 until v=a[x].key; seq_search:= x end; 51
function seq_insert(v: integer):integer; begin N:= N+1; a[n].key: =v; seq_insert:= N end; Note:  Tham s x c avào iphó v i tr ng h p nhi u m u tincócùng tr khóa. B ngcách th chi n t: =seq_search (v, t) b t u v i t =0, tacóth liên ti pcho t b ng v trí c a m i m u tincótr khóalàv.  N u s tìmki m th t b i,sep_search tr v tr N+1. 52
ctính c atìmki mtu n t (Ch ngminh) Tính ch t: Tìmki m tu n t c nN+1sosánh i v i m t s tìmki mkhông thành công và kho ngtrung bình N/2so sánh i v i m ttìmki m khôngthành công. Ch ngminh:  Tr ng h p x u nh t  Tr ng h p x unh t x yrakhi v là ph n t cu icùng c a m ngho c v khôngcótrong m ng.  Trong c hai tr ng h p,chúng tacól n l tC(N)=Nvà C(N)=N+1. 53
Tr ng h ptrungbình Gi s v có xu t hi ntrong m ng và có m txácxu t u xu t hi n t i m t v trí b t k nàotrong m ng. Và m i tr ng h p x y ra v i cùng xácxu t p = 1/N. Thì C(N)=1.(1/N) +2.(1/N)+ +N.(1/N) =(1 + 2+ +N).(1/N) =(1+2+ +N)/N = N(N+1)/2.(1/N)=(N+1)/2. 54
Tìmki mchia ôi(binarysearch) Ph ng pháp này function binarysearch(v:integer): integer; c áp d ngkhi var x, 1,r: integer; m ng ã có th t . begin 1:=1; r: = N; repeat x:=(1+r)div 2 if v r); if v= a[x].key then binarysearch:= x else binarysearch:=N+1 end; 55
ph c t p c agi ithu ttìmki mchia ôi H th ctruy h i c agi ithu tnày là: CN CN/2 + 1 Tính ch t: Tìmki m chia ôi khôngbaogi òi h i nhi u h n lgN + 1sosánhcho m t s tìmki mthành cônghaykhông thành công. 56
Ch ng3 Phântích ph c t p m t s gi ithu ttrên c utrúc d li u 1
N idung 1.Tìm ki m tu n t trên danhsáchliên k t 2. Cây tìm ki mnh phân 3. Hàng icó u tiên và heapsort 4. K thu t b m 2
1.Tìmki mtu nt trêndanhsáchliênk t  Tìmki m tu nt (sequentialsearch)cóth cth c hi nthôngquavi cdùngdanhsáchliênk t(linked list)bi udi ncácm utin trongt ptin.  M tl i i m: d làmchodanhsáchliênk tcóth t mà giúpchovi ctìmki mnhanhchóngh n. 3
Tìmki mtu nt trênm tdanhsáchliênk tcó th t . Qui c:zlànútgi trongdanhsáchliênk t. 3 4 7 21 Z type link=node node=record key,info:integer; next:link end; var head, t, z:link; i: integer; 4
Gi ithu ttìmki mtu nt trêndanhsách liênk t procedure initialize; begin new(z); z.next:=z; new(head); head.next:= z end; function listsearch(v: integer;t: link): link; begin z.key:=v; repeat t:= t.next until v<= t.key; if v= t.key then listsearch:= t else listsearch:= z end; 5
Gi ithu ttìmki mtu nt trêndanhsáchliên k t(tt.) function listinsert(v: integer; t:link): link; begin z.key:= v; while t.next.key<vdo t:= t.next; new(x); x.next:= t.key; t.next:=x; x.key:= v; listinsert:=x; end; Tínhch t: Tìmki mtu nt trêndanhsáchliênk tcó th t dùngtrungbìnhkho ngN/2 thaotácsosánhchoc s tìmki mthànhcônghay khôngthành. 6
Ch ngminh: V is tìmki mthànhcông, n ugi s r ngm im utin trongdanhsáchliênk tcóxácxu t b ngnhau(1/N) ctìmth y, s l nsosánhtrungbìnhs là: (1+2+ +N)/N=N(N+1)/(2N)=(N+1)/2. V is tìmki mkhôngthànhcông, n ugi s r ngm im u tintrongdanhsáchliênk thaynútk tthúc z có xácxu t b ngnhau (1/(N+1)) ctìmth y v trí saucùngc a quá trìnhtìmki m, s l nsosánhtrungbìnhs là: (1+2+ +(N+1))/(N+1)= (N+2)(N+1)/(2(N+1))= (N+2)/2. 7
2.Câytìmki mnh phân Trongm tcâytìmki mnh phân (binarysearchtree), t tc cácm utin v ikhóa nh h n khóat inút angxét thì câycon bêntráic anútvà cácm utin v ikhóa l nh nhay b ng khóat inút ang xétthì câycon bênph ic anút. 10 5 13 2 7 19 8
Kh it ocâynh phân M tcâyr ng cbi udi nb ngcâycócon tr bênph ich nnútgi z. procedure tree_init; begin new(z); z.1:=z; z.r: = z; new(head); head.key:=0;head.r: = z; end; 9
Tácv thêmvào Thêmm tnútvàotrongcây,tath chi nm ts tìm ki m(khôngthànhcông) nút ytrêncây, r ig nnút yvàov trí ngv inútgi z t i i mmàquá trìnhtìm ki mk tthúc. A S E Hìnhv minhh a vi cthêmnútP vào A R câynh phân. C H 10
Tácv thêmvào(tt.) procedure tree_insert(v: integer;x: link): link; var p: link; b; egin repeat p:=x; if v< x.key then x:= x.1 else x:= x.r until x=z; new(x); x.key:= v; x.1:= z; x.r:= z; /* create a new node*/ if v< p.key then p.1:=x /*p denotes the parent of the new node*/ else p.r:=x; tree p.r:= x end 11
Inracâynh phân procedure treeprint(x: kink) begin if x<>zthen begin treeprint(x.1); printnode(x); treeprint(x.r) end end; Vì m tcâynh phândi nt m tt ptin có th t ,vi cin ra cáctr khóatrongcâytheom tcách úng ns eml i m tdanhsáchcáckhóacóth t . 12
Tácv tìmki m type link=node; node=record key, info: integer; l,r: link end; var t, head, z: link; function treesearch(v: integer, x: link):link; /* search the nodewith the key v in the binarysearch tree x */ begin while v z do begin if v< x.key then x:= x.1 else x:= x.r end; treesearch:= x end; 13
Tínhch tc as tìmki mtrêncâynh phân Tínhch t: M ttácv thêmvàohaytìmki mtrênm tcâynh phân òih ich ng2lnNsosánhtrênm tcây ct orat N tr khóang unhiên. Ch ngminh: Chi udàil i ic a1nút:làs c nhc nduy tqua t nút yv nútr +1. iv im inúttrêncâynh phân, s sosánh cdùng chom ts tìmki mnút ythànhcôngchínhlàchi udài l i ic anút y. T ngt tc chi udàil i ic am inúttrêncâynh phân cg ilàchi udàil i ic acâynh phân. 14
Ch ngminh(tt.) Khichiachi udàil i itoàncâyv iN,tas cs sosánh trungbình iv im ts tìmki mthànhcôngtrêncây. Nh ngn uCNbi uth chi udàil i itrungbìnhc atoàn cây,tacóm th th ctruyh isau ây, v i C1 = 1 N CN =N +  (Ck-1 + CN-k) 1 S h ngNlàdo s ki nnútr ónggóp1vàochi udàil i i c am inút. S h ngth hailàdo s ki nkhóat inútr cóxácxu tb ng nhau tr thànhph nt l nth k trongcây, v ihaicâycon l nl tch a k-1 nútvàN-k. 15
Ch ngminh(tt.) k k-1 N-k H th ctruyh inàyr tgi ngh th ctruyh ikhiphân tíchQuicksort,vànó ã cgi icùngm tcách a l icùngm tk tqu . Do ó chi udàitrungbìnhc acâyN nútlà CN 2N lnN. Suyrachi udàitrungbìnhc am tnúttrongcâylà 2lnN. M ttácv tìmki mhaythêmvào òih itrungbình 2lnNsosánh trênm tcâyg mN nút. 16
ph ct ptrongtr òngh px unh t Tínhch t: Trongtr ngh px unh t, m ttácv tìm ki mtrêncâynh phâng mNkhóacóth c nNso sánh. Tr ngh px unh tx yrakhicâynh phânb suybi n thànhm tdanhsáchliênk t. Tácv xóa Vi cxoá m tnútr td n unút ykhôngcónútconhay ch có m tnútcon. xóam tnútcó haiconthì khá ph ct p:taph ithay th nó v inútcótr khóacaonh tk ti p(t cnútt ncùng trái c acâycon bênph i). 17
E A R C H N M F L Thí d :Tácv H xoá A R C N M P L 18
Thefollowing procedure istodelete thenode t from the binary tree x. procedure treedelete(t, x:link); var p,c:link; begin repeat /*searchfor the node tinthetree*/ p:= x; if t.key< z. key then x:= x.1 else x:= x.r until x=t; if t.r=zthen /*the nodet has no right child*/ x:= x.1 /*replace the deletednodewiththe left child of t */ elseif t.r.1=then /*theright chileofthas noleftchild*/ begin x:= x.r; x.1:= t.1 end /*replace thedeleted node withitsright child */ 19
else begin e:= x.r; while c.1.1<>zdo c:= x.1;/*find theleftmost node of therightsubtree*/ x:= c.1; /* xdenotesthenodethat willreplace the deletedone */ c.1= x.r; /* connectc, the parentof xtotheright child of x*/ x.1:= t.1; x.r:= t.r/*connectx:the childrenof the deletednode t*/ end; if t.key< p.key then p.1:= x /*connect xtotheparent of the deleted node */ else p.r:= x; end; 20
3.Hàng icó utiênvà gi ithu ts p th t HEAPSORT M tc utrúcd li umàh tr ítnh thaitácv : +thêmm tph nt m ivàoc utrúc +xóab ph nt l nnh t cg ilàhàng icó utiên(a priority-queue). Hàng icó utiênkhácv ihàng ithôngth ng i mkhil yph nt rakh ihàng ithì ó khôngph ilà ph nt c nh t tronghàng imàlàph nt có utiên l nnh t tronghàng i. 21
Hàng icó utiên(tt.) Chúngtamu nxâyd ngvàduytrì m tc utrúcd li uch anh ng m utincótr khóas ( utiên)vàcóh tr m ts trongnh ng tácv sau: -t om thàng icóth t utiêng mNph nt . -thêm(insert)m tph nt m ivào. - xóab ph nt l nnh trakh ihàng i. -thayth ph nt l nnh tvim tph nt m i -thay i utiênc am tph nt . -Xóab m tph nt b tk nào ó. -Ghéphaihàng icó utiênthànhm thàng icó utiên l nh n. 22
Thicônghàng icó utiên Hàng icó utiênnh ã mô t là m tvíd v ki ud li utr u t ng ã nói ch ng1.Cóhaicách thicônghàng icó utiên: 1. Dùng m ng thicônghàng icó utiên(Cáchnàythì n gi nkhithêmvàom tph nt m inh ngkhixóab ph nt có utiênl nnh trakh ihàng ithì ph ct ps cao.) 2. Dùngc utrúcd li u heap. 23
C utrúcd li uheap C utrúcd li umàcóth h tr chocáctácv làmvi cv i hàng icó utiên s ch acácm utintrongm tm ng saocho: m ikhóaph il nh nkhóa haiv trí kháctrongm ng. T ngt m ikhóatronghaikhóanàyph il nh nhaitr khóakhácvàc nh th Th t nàys d th yh nkhitadi nt m ngnh m tc u trúccâyv inh ng ngn im ikhóaxu nghaikhóa nh h n. Cáctr khóatrongc utrúccâyth a i uki n heap nh sau: Khóat im inútc nph il nh n(hay b ng) cáckhóa haicon c anó(n ucó). i unàyhàmý r ngtr khóal n nh t nútr . 24
Thí d : Heap d id ngcâynh phân X T O G S M N A E R A I 25
Heap d id ngm tm ng Ta có th di nt d ngcâyc aheapthànhm tm ngb ng cách tnútr t iv trí 1 c am ng, cáccon c anót iv trí 2 và 3, cácnút cácm ck ti p cácv trí 4, 5, 6 và 7, v.v k 1 2 3 4 5 6 7 8 9 10 11 12 a[k] XT O G S M N A E R A I T m tnútd dàng it inútcha và cácnútcon c anó. Cha m tnút v trí j s là nút v trí jdiv 2. Haicon c am tnút v trí j s cácv trí 2j và 2j+1. 26
Cácl i itrênheap M theap là m tcâynh phân, cdi nt nh là m tm ngtrong ó m inútth amãn i uki n heap. cbi t,ph nt cókhóal nnh tluôn v trí th nh t c am ng. T tc cácgi ithu tlàmvi ctrênheap id ctheo m tl i inào ót nútr xu ngm c áy(bottom) c aheap. Trongm theap có Nnút, t tc cácl i i(path) th ngcólgN núttrên ó. 27
Cácgi ithu ttrênHeap Có haitácv quantr nglàmvi ctrênheap:thêmvào ph nt m ivàxóab ph nt l nnh trakh iheap. 1.Tácv thêmvào(insert) Tácv nàys làmt ngkíchth cc aheap lênthêm m tph nt . N ct ngthêm1. Và ph nt m i c tvàot iv trí a[N],nh nglúc ó i uki nheap có th s b viph m. N u i uki nheap b vi ph m,nós ckh cph c b ngcách hoán i ph nt m iv icha c anó. i u nàyl icóth gâyravi ph m i uki nheap và nó s ckh cph cti pv icùngm tcácht ngt . 28
Tácv thêmvào procedure upheap(k:integer) var v:integer; begin v:=a[k];a[0]:=maxint; while a[k div 2]<=vdo begin a[k]:=a[k div 2];k:=k div 2 end; a[k]:= v end; procedure insert(v:integer); begin N:= N+1;a[N]:=v;unheap(N) end; 29
Thêm(P)vàoheap X T P G S O N A E R A I M 30
Tácv xóab ph nt l nnh t Tácv xóas làmgi mkíchth cc aheap m t nv, t cnólàmgi mN m t nv. Nh ngph nt l nnh t(t c a[1]) s cxóab và c thayth b ngph nt mà ã v trí a[N]. N utr khóat i nútr quá nh , nó ph i c dichuy nxu ng th amãn i uki nheap. Th t c downheap th chi nvi cdichuy nph nt ang nútr xu ngb ngcáchhoán inút v trí k v inút l nh ntronghainútcon c anó, n uc nvàd ngl ikhi nút k l nh nhainútcon c anó. 31
Tácv xóab procedure downheap(k: integer); label 0 ; var j,v : integer; begin v:= a[k]; while k = a[j] thengoto 0; remove := a[1]; a[k]:=a[j]; k:=j; a[1]:= a[N]; N:= N-1; end; downheap(1); 0: a[k]:=v end; end; 32
Thí d v tácv xóa Tr ckhixóa T S P G R O N A E C A I M 33
Saukhixóa S R P G M O N A E C A I 34
Tínhch tc acáctácv trênheap Tínhch t3.1: M itácv thêmvào,xóab , downheap,upheapdòih iíth n2lgNsosánhkhi th chi ntrênm theap g mNph nt . T tc nh ngtácv nàyph i id ctheom tl i igi a nútr cho ncu iheapmàbaog míth nlgNph nt v im theap g mNph nt . Th as 2 là dotácv downheapmàc nhaithaotácso sánhtrongvòngl ptrongvàcácthaotáckhácch òih i lgNl nsosánh. 35
Gi ithu theapsort Ý t ng:Gi ithu tbaog m2côngtác(1) t om theap ch anh ngph nt c ns pth t và (2) l nl tl y chúngrakh iheaptheom tth t . M:kíchth cc aheap N: s ph nt c n cs pth t . N:=0; for k:= 1toMdo insert(a[k]); /*constructtheheap */ for k:=Mdownto 1 do a[k]:=remove; /*puttingtheelementremoved intothe array a*/ 36
S pth t dãys 5,3, 1, 9, 8, 2, 11 b ngheapsort 5 9 3 1 5 1 3 9 9 8 1 8 2 3 5 3 5 1 11 8 9 3 5 1 2 37
9 8 8 2 5 2 3 5 1 11 3 1 9 11 5 3 3 2 1 2 1 8 9 11 8 9 5 11 2 1 1 3 2 3 8 5 9 11 5 8 9 11 38
ph ct pc aheap sort Tínhch t: Heapsortdùng íth n3MlgM l nso sánh s pth t M ph nt . Gi ih ntrênnàyxu tphátt gi ithu theapsort và tínhch tc ahaitácv thêmvào/xóab trên heap. Vòng for th nh tt nMlgMl nsosánh. Vòng for th hait n2MlgM l nsosánh. T ngc ng: MlgM+2MlgM=3MlgM 39
4.K thu tb m K thu tb m(Hashing) là m tph ngpháp tìmki mcác m utintrongm tb ngb ngcácbi n icáctr khóathành nh ng ach (v trí)trongb ng. B c ulàt om thàmb m(hashfunction )màchuy n i khóatìmki mthànhm t ach trongb ng. M tcáchlýt ng,nh ngtr khóakhácnhaunênánhx thànhnh ng ach khácnhau, nh ngkhôngcóhàmb mnào làhoành ovàdo ó haihay nhi ukhóakhácnhaucóth b m thànhcùngm tv trí b ng. B ck ti plàquá trình gi iquy t ng (collision- resolution)mà iphó v itr ngh phaihay nhi ukhóa khácnhaucóth b mthànhcùngm tv trí b ng. 40
Hàmb m Hàmb m làhàmbi nth cáctr khóathànhnh ngs nguyêntrongt m[0 M-1], v iM là s m ctinmàcóth cch atrongm ts l ng ô nh có s n. M thàmb mlýt nglàhàmb mmà -d tínhtoán -g ngi ngnh m thàm“ng unhiêm”. M tph ngphápthôngth ngnh t b mlàcho M là m ts nguyênt vàv im itr khóa k,tatính h(k): = kmod M ylàm tph ngpháptr cti pmàd tínhvàr ikhá ucáctr khóaratrênb ngb m. 41
Ví d Kíchth cb ngb m= 101.Gi s m itr khóag m4ký t . N ukhóa(“AKEY”) cmãhóathànhm tmãg m5 bit,tacóth coikhóa ylàm ttràngs nh ph nnh sau: 00001 01011 00101 11001 1 × 323 + 11 x322 + 5 x 321 + 25 x 320 Mà t ng ngv itr s th pphân44217 . Vì, 44217mod 101=80, nh v ykhóa “AKEY”ánhx thành80. T isaokíchth cM c ab ngb mc nph ilàs nguyên t ?Lýdo là vì chúngtamu n t tc m ikýt trongkhóa uthamgiavàovi cchuy n i(b m)thànhv trí. Trongthí d trên, n uM= 32,hàmb mc ab tk khóa nàoc ngch b mm ikýt saucùng! 42
B mm tkhóadài Nukhóalàm tdòngkýt khá dàithì chúngtav ncóth tínhb ngm thàmb mmàbi n ikhóat ngkýt m t. K thu t ó th hi nb nggi ithu tl pnh sau: h:=key[1]; for j:= 2 to key_size do begin h:=((h*32)+key[j]) mod M;/*25 is32,usedfor 5-bit code*/ end; 43
Ph ngphápgi iquy t ng : Xâuriêng (Separatechaining) Trongk thu tb m,chúngtaph iquy t nhdùngcách nào gi iquy tv n haikhóakhácnhaub mthành cùngm tgiá tr ach . M tph ngpháp ngi nnh t: t ochom iv trí trong b ngb mm tdanhsáchliênk t(xâuriêng) xâut tc nh ngtr khóamàb mvàocùngv trí ó. Khicáctr khóa cxâutrêndanhsáchliênk t, chúng nên cs pchocóth t . type link=node; node=record key, info:integer; next:link end; var heads:array[0 M] of link;t,x:link; 44
Xâuriêng(tt.) Danhsáchliênk tchot ngv trí trongb ngb m ckh i t onh gi ithu tsau: procedure initialize; var i:integer; begin new(z); z.next:= z; for i:=0to M-1 do begin new(heads[i]); heads[i].next:= z end; end; Tronghìnhv sautrìnhbàyvi c avàob ngb mm tdãy cáckýt ch . 45
Key:ASEARC H INGEXAMPL E Hash:18517389375212515 0 1 2 3 4 5 6 7 8 910 A M C E G H I A X N E R S A E L P 46
Ph ngphápgi iquy t ng : Dò tuy ntính Ph ngphápxâuriêngcóth ápd ngtrongtr ngh p M N, nh vàonh ngv trí tr ngtrong b ngb m gi iquy t ng . Nh ngph ngphápnh v y cg ilàk thu tb m ach m (open addressing hashing). Ph ngpháp ach m ngi nnh tlàph ngpháp dò tuy ntính ( linearprobing): m ikhicó ng thì dò n v trí k ti p trongb ngb m, t clàsosánhtr khóac ntìm v itr khóat im utin. 47
Dò tuy ntính(tt.) Có bak tqu có th có c as th mdò: - N uhaitr khóakh pnhauthì s tìmki mk tthúcthành công. - N ukhôngth ycóm utin t iv trí,thì s tìmki mk tthúc th tb i. - Ng cl i,dòtìmt iv trí k ti p,ti pt cnh th cho nkhi tìmth ytr khóakh pnhauho clàm tv trí r ng. 48
Gi ithu tdòtuy ntính procedure hash_initialize; var i:integer; begin for i:=0to M do a[i].key:=maxint;/*maxintmeansanempty position*/ end; function hash_search(v: integer): integer; var x: integer; begin x:=h(v); while a[x].key v do x:=(x+1) mod M; if a[x].key:= v then hash_search:= x else hash_search:=M; end; 49
Dò tuy ntính(tt.) function hash_insert (v:integer):integer; var x:interger begin x:=h(v); while a[x].key<>maxint do /*collision*/ x:= (x+1) mod M; a[x].key: =v;hash-insert:=x; end; Hìnhv sautrìnhbàyvi c avàob ngb mm tdãycácký t ch : ASE ARC HI N GE X AM P L E 50
Key: A S EARCHIN G EX A MP L E Hash: 1 05 1 18 3 8 9 14 7 5 5 1 13 16 12 5 S A A C A E E G H I X E L M N P R 51
Tínhch tc adòtuy ntính Kíchth cb ngb mdùngchok thu tdòtuy ntính th ngl nh nb ngb mdùngxâuriêng,vìtaph icó M > N, nh ngt ngch b nh s íth nvìkhôngc nl u cáccontr . Tínhch t. Dò tuy ntínhs d ngtrungbình íth n5 b cdò iv im tb ngb m yd i2/3. Côngth cchínhxácv s l ndòtrungbìnhc nchom ts tìmki mkhôngthànhcônglà: ½+1/(2*(1- )2) v i = N/M N u =2/3,ta ck tqu 5 b cdò. 52
Ch ng4 ph c t p c acácgi ithu t th 1
N idung 1. Cácgi ithu t th c n b n 2. th có tr ng s 3. th có h ng 2
1.Cácgi ithu t th c nb n Cónhi ubàitoán c nhngh atheo it ngvàcác k tn igi acác it ng y. M t th là m t it ngtoánh cmàmôt nh ngbài toánnh v y. Các ngd ngtrongcáclãnhv c: Giaothông Vi nthông i nl c M ngmáytính C s d li u Trìnhbiêndch Cách i uhành Lý thuy t th 3
M tthí d A H I B C G D E J K F L M Hình4.1a M t th thí d 4
Thu tng M t th là m tt pcác nh và các c nh.Các nhlà nh ng it ng nmàcóth có tênvàcóm ts tính ch tkhácvàc nhlà ngk tn igi ahai nh. M t l i i t x nytrongm t th là m tdanhsách nh ng nhmành ng nhk ti pnhau ck tn inh vàonh ngc nhtrên th . M t th là liênthông n ucóm tl i it m inút n m tnútkháctrong th . M t th mà khôngliênthông thì baog mnhi u thànhph nliênthông. M t l i i n là m tl i imàtrên ó khôngcó nhnào l pl i. 5
Thu tng (tt.) M t chutrình (cycle )làm tl i i nngo itr nh u tiênvà nhcu icùngtrùngnhau(m tl i it m t nh quay v chínhnó). M t th khôngcóchutrình cg ilàcây(tree). M t nhómcáccâykhôngliênthông cg ilàr ng ( forest ). Câybaotrùm c am t th là m t th conmàch at tc các nhtrongcâynh ngm ts c nh ch m nm i nh. G is nhtrongm t th là V, s c nhlàE, s c nhc a th có th có t 0 nV(V-1)/2.(Ch ngminhtruych ng). th có t tc m ic nhhi ndi ngi am ic p nh c g ilà th y (complete graphs). 6
Thu tng (tt.) Các th v is c nht ng i ít cg ilà th th a; các th v ich m ts ítc nhm t i cg ilà th dày. Các th mô t cho ngi là nh ng th vô h ng (undirected graphs).Trongcác th có tr ngs (weighted graphs), nh nggiá tr s (tr ngs ) cg nvàom ic nh di nt thí d kho ngcáchhay chi phí. Trong th có h ng (directedgraphs) cácc nhlà“m t chi u”: m tc nh it xsang y ch khôngph i it ysang x. Các th có h ng,cótr ngs còn cg ilàcácm ng (networks). 7
Cáchbi udi n th Ta ph i ánhx cáctên nh thànhnh ng s nguyên trong t mtr gi a1 và V. Gi s có t nt ihaihàm: -hàmindex: chuy n it tên nhthànhs nguyên -hàmname: chuy n is nguyênthànhtên nh. Có haicáchbi udi n th : -dùngmatr nk c n -dùngt pdanhsáchk c n 8
Cáchbi udi nmatr nk c n A B C DEFGH I J KL M M tmatr nV A 11 1001 1 000 00 0 B 11 0000 0 00 0 0 0 0 hàngV c tch a C 10 1000 0 00 0 0 0 0 cácgiá tr Boolean D 00 0111 0 00 0 0 0 0 mà a[x,y] là true if E 00 0111 1 00 0 0 0 0 n ut nt im t F 10 0111 0 00 0 00 0 c nht nh x n G1 0 0010 100 00 0 0 H 00 0000 011 00 0 0 nh y và false n u I 00 0 000 011 00 0 0 ng cl i. J0 0 000 0 0 00 1 1 1 1 K 00 0000 0 00 1 1 0 0 Hình4.1b: Ma tr nk L0 00000 0 00 1 01 1 c nc a th hình M0 0 0000 0 00 1 01 1 4.1a 9
Ghichú v cáchbi udi nmatr nk c n M ic nht ng ngv i2bittrongmatr n: m i c nhn igi a x và y cbi udi nb nggiá tr true t ic a[x, y] và a[y,x]. ti nl igi nhr ngcót nt im tc nhn im i nhv chínhnó. L ibi udi nnàych thíchh pkhicác th là d y. 10
Gi ithu t program adjmatrix(input,output); const maxV=50; var j,x,y,V, E:integer; a: array[1 maxV,1 maxV] of boolean; begin readln(V, E); for x:=1to V do /*initializethematrix*/ for y: =1to V do a[x,y]:=false; for x:=1to V do a[x,y]:=true; for j:=1to Edo begin readln(v1,v2); x:=index(v1);y:=index(v2); a[x,y]:=true;a[y,x]:=true end; end. 11
Cáchbi udi nb ngt pdanhsáchk c n Trongcáchbi udi nnày, m i nhmàn it im t nh ck tthànhm tdanhsáchk c n (adjacency-list )cho nh ó. program adjlist(input, output); const maxV= 100; type link=node node=record v: integer; next:link end; var j,x, y,V,E: integer; t,x:link; adj: array[1 maxV] of link; 12
begin readln(V,E); new(z); z.next:=z; for j:=1to V do adj[j]:=z; for j: 1 to E do begin readln(v1, v2); x:= index(v1); y:=index(v2); new(t); t.v:=x; t.next:=adj[y]; adj[y]:=t; /*insert xtothefirst element of y’sadjacencylist*/ new(t); t.v= y; t.next:=adj[x]; adj[x]:=t; /*insert ytothefirstelementof x’sadjacencylist */ end; end. 13
a bc d e f g h i j k l m f a a f g a e i h k j j j c e f e a l m l b d d m g Hình4.1c:Bi udi nb ngt pdanh sáchk c nc a th hình4.1 14
Cácph ngphápduy t th Duy thaytìmki mtrên th :vi ngm i nh/nút trong th m tcáchcóh th ng. Có haicáchchính duy t th : -duy ttheochi usâutr c(depth-first-search ) -duy ttheochi ur ngtr c(breadth-first-search). 15
Duy ttheochi usâutr c – gi ithu t quy procedure dfs; procedure visit(n:vertex); begin add n to thereadystack; while thereadystack isnotempty do get avertexfrom thestack,processit, andadd any neighbor vertexthat has not been processed tothestack. if a vertex hasalreadyappearedinthestack,thereis no needto push ittothestack,butitismoved tothetopof thestack. end; begin Initializestatus; for eachvertex,say n, inthegraph do if thestatusof nis “notyetvisited” then visit(n) end; 16
Tìmki mtheochi usâutr c – bi udi n danhsáchk c n procedure list-dfs; var id, k:integer; val: array[1 maxV] of integer; procedure visit(k:integer); var t:link; begin id:= id+ 1; val[k]:= id;/*change thestatus of k to “visited” */ t:= adj[k]; / * findtheneighborsofthevertexk */ while t<> z do begin if val[t .v]= 0 then visit(t.v); t:= t.next end end; 17
begin id:= 0; for k:=1to V do val[k]:= 0;/initialize thestatusofallvetices*/ for k:=1to V do if val[k]= 0 then visit(k) end; Ghichú: M ng val[1 V] ch a tr ngthái c acác nh. val[k] = 0 n u nh k ch ah cvi ng(“not yetvisited”), val[k] 0 n u nh k ã cvi ng. val[k]: =jngh alà nh jthmà cvi ngtrongquá trình duy tlà nh k. 18
A A A A E F F F A A A A G G G G E E E E F F F F A A A A G G G G D E D E D E D E F F F F A A A A C G C G B C G B C G D E D E D E D E F F F F 19 Hình4.2Duy ttheochi usâutr c
Nh v yk tqu c agi ithu tduy tDFStrên th cho hình4.1a v it pdanhsáchk c ncho hình4.1clà AFE G D C G L u ý:th t c acác nhtrongcácdanhsáchk c ncó nh h ng nth t duy tc acác nhkhi ápd ngDFS. 20
ph ct pc aduy ttheochi usâutr c Tínhch t5.1.1 Duy ttheochi usâutr cm t th bi udi nb ngcácdanhsáchk c n òih ith i giant l V+E. Ch ngminh:Chúngtaph igántr chom iph n t c am ng val (do ó t l v iO(V)),vàxétm i núttrongcácdanhsáchk tc nbi udi n th (do ó t l v iO(E)). 21
Duy ttheochi usâutr c – bi udi nb ngma tr nk c n Cùngm tph ngphápcóth c ápd ngcho th cbi udi nb ngmatr nk c nb ng cáchdùngth t c visit sau ây: procedure visit(k:integer); var t:integer; begin id:= id+ 1; val[k]:= id; for t:=1to V do if a[k,t] then if val[t]= 0 then visit(t) end; 22
ph ct pc aduy ttheochi usâutr c – bi udi nmatr n Tínhch t5.1.2 Duy ttheochi usâutr cm t th bi udi nb ngmatr nk c nt l v iV2. Ch ngminh: B ivìm ibittrongmatr nk c n c a th uph iki mtra. 23
Duy ttheochi usâutr c – không quy procedure list-dfs; var id,k: integer;val: array[1 maxV]of integer; procedure visit(k: integer); var t: link; begin push(k); repeat k:=pop; id:= id+1;val[k]:= id; /*change thestatusofk to “visited” */ t=:adj[k]; /* findtheneighborsof thevertexk*/. while t<>zdo begin if val[t.v]=0then begin push(t.v);val[t.v]:=-1 /*change thestatusof t.v to “ready” */ end else if val[t.v]=-1 then shift t.v to thetopof thestack; t:= t.next end until stackempty end; 24
begin id:= 0; stackinit; for k:= 1 to V do val[k]:=0;/* initialize the status of allvertices*/ for k:= 1 to V do if val[k]= 0 then visit(k) end; V igi ithu tkhông quy,tac ndùngm tstack cg i làreadystack. Ghichú: val[k] = 0 n u nh k là“ch a cvi ngth m”, val[k] = -1 n u nh k ang trongreadystack val[k] là m ttr d ngn u nh k ã cvi ngth m. 25
A A B C G F A A B C G B C G E D E F F Hình4.3aDFS d avàostack 26
GE D B BBB M C C C C C L L AF F FFF FHI JKK K Hình4.3b N idung c astackkhith chi nduy ttheochi usâutr c 27
Duy ttheochi ur ngtr c Khiduy t th n utadùngm tqueue thayvìm tstack,tas i nm tgi ithu t duy ttheochi ur ngtr c (breadth-first- search). procedure bfs; procedure visit(n:vertex); begin add n to thereadyqueue; while the ready queue is not empty do get a vertex fromthe queue, process it, and add any neighbor vertex that has not been processed tothe queue and changetheir statustoready. end; begin Initialize status; for eachvertex, say n, inthe graph if thestatus of n is “not yet visited” then visit(n) end; 28
procedure list-bfs; var id, k: integer; val: array[1 maxV] of integer; procedure visit(k: integer); var t: link; begin put(k);/* put a vertex to the queue */ repeat k:= get; /* get a vertexfrom the queue */ id:= id + 1; val[k]:= id; /* change the statusof kto “visited” */ t:= adj[k]; /* find the neighbors of the vertex k */ while t<> z do begin if val[t .v]= 0 then begin put(t.v); val[t.v]:=-1 /* change thevertex t.v to “ready” */ end; t:= t.next end until queueempty end; 29
begin id:= 0;queue-initialze; for k:=1to V do val[k]:= 0; /initializethe status ofall vertices*/ for k:=1to V do if val[k]= 0 then visit(k) end; Duy ttheochi usâutr cvàduy ttheochi ur ngtr c ch khácnhau ch gi ithu t udùngstack và gi ithu t saudùnghàng i.Do ó, ph ct ptínhtoánc aDFS và BFS là nh nhau. 30
I H D D D D D E E E E G G G G B B B M M M C C L L F K A J Hình4.4 N idung c ahàng ikhith chi nBFS 31
2. th có tr ngs Chúngtamu nmôhìnhhóanh ngbàitoánth ct s d ng nh ng tr ngs (weights ) hay chiphí (costs) cg nvào m ic nh. Có haibàitoán cgi iquy ttrongph nnày: -tìmm tcách ítt nchí phí nh t n it tc các nh trong th . -Tìmm tl i iv it ngchi phíítnh tgi ahai nh ã cho. Bàitoánth nh tlàbàitoán câybaotrùmt ithi u; bàitoán th hailàbàitoán tìm ng ing nnh t. 32
Câybaotrùmt ithi u M t câybaotrùmt ithi u (minimumspanningtree ) c am t th có tr ngs làm tt pcácc nhch mt tc các nh saochot ngtr ngs c acácc nhlành nh t. Câybaotrùmt ithi u khôngnh tthi tlàduynh t trong m t th . 8 7 b c d Hình 4.5 Cây bao 9 trùm t ithi u 4 11 2 14 a i 4 e 6 8 7 10 h g f 1 2 33
Gi ithu tPrim Gi ithu tPrim là gi ithu t gi ibàitoáncâybaotrùm t ithi u. Gi ithu tnàyc ngtrìnhbàym tchi nl c gi im tbàitoánt i uhóa:gi ithu t thamlam (greedy): T im ib cc agi ithu t,taph ich nm ttrongm t s kh n ngl ach n.Chi nl cthamlam xu tvi c l ach nkh n ngmàxemrat tnh tt ilúc ó. M tchi nl cnh v yth ngkhông mb o eml il i gi it i utoànc cchocácbàitoán. Tuynhiên iv ibàitoáncâybaotrùmt ithi u,tacóth ch ngminhr ngchi nl cthamlamcóth eml i câybaotrùmv it ngtr ngs t ithi u. 34
Xâyd ngcâybaotrùmt ithi u Gi s chúngtacóm t th vô h ng,liênthông G=(V,E) v ihàmgántr ngs w:E Rvàmu ntìmm t câybaotrùmt ithi uchoG. Có m t gi ithu tt ngquát mà t od ngd ncâybaotrùm t ithi um tlúcthêmm tc nh. Gi ithu tnàyduytrì m tt pAmàluônluônlàm tt p con c am tcâybaotrùmt ithi u. T im ib c, m tc nh (u,v) cch n thêmvàot pA màkhôngvi ph m h th cb tbi n A {(u, v)}luônluônlà m tt pcon c am tcâybaotrùmt ithi u. 35
Ta g im tc nhnh th là c nhan toàn chot pAvìnócó th cthêmvàoA m tcáchantoànmàkhôngvi ph mh th cb tbi nnêutrên. procedure GENERIC_MST(G, w); /* G is a weightedgraph withtheweightfunction w */ begin A:= ; while Adoes notform a spanning tree do begin find anedge(u,v) thatissafefor A; add(u,v) to A. end /*thesetA at this pointistheresult */ end; 36
Gi ithu tPrim Tronggi ithu tPrim, t pA hìnhthànhm tc utrúccây. M t c nhantoàn c avàoAth nglàc nhcótr ngs nh nh tn icâyA v im t nhkhôngthu cv cây. Câybaotrùmkh i it m tnútr b tk rvàpháttri ncho nkhicâyph t tc m i nhtrongV. T im ib c, m t c nhnh (lightedge) n im t nhtrongA v im tc nhtrong V-A. Trongquá trìnhth chi ngi ithu tnày, t tc nh ng nh mà khôngthu cv câyA c ttrongm thàng icó utiên Q d atrênm ttr nglàkey. V im i nh v, key[v] là c nhcótr ngs nh nh tc anh ngc nhn ivv im t nh trongcây.Theo qui ckey[v]= n ukhôngt nt im t c nhnh v y. 37
Tr ngp[v] l utênc a nhcha c a nh v trongcây. procedure MST-PRIM(G, w,r); /* G is weighted graph with the weight function w, and r is an arbitrary rootvertex*/ begin Q:=V[G]; for each u Q do key[u]:= ; key[r]:= 0; p[r]:= NIL; while Q is not empty do begin u:=EXTRACT-MIN(Q); for eachv Q and w(u,v)< key[v] then /* update the key field of verticev*/ begin p[v] := u; key[v]:= w(u,v) end end end; 38
8 7 Hình 4.6. M tthí 4 b c d 8 d v gi ithu t Prim. 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 39
8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 40
8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 41
8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f 42
8 7 4 b c d 8 2 4 11 a i 14 e 7 6 1 2 10 8 h g f ph ct pc agi ithu tPrimtùythu cvàocách mà chúngtathicônghàng icó utiên. 43
ph ct pc agi ithu tPrim Tínhch t: N uQ cthicôngnh là m theap nh phânthì th igiantínhtoánc agi ithu tPrimlàO(E lgV). N uQ cthicôngnh là m theap nh phân, chúngtacó th l pram theaptrongb ckh it ov ichi phí th igian là O(V). Vòngl pwhile cth chi nV l nvàvìm ithaotác EXTRACT-MIN có ph ct pO(lgV), chi phí tínhtoán chot tc cácl nhg iEXTRACT-MINlàO(VlgV). Vòngl pfor bêntrongvòngl pwhile cth chi nt ng c ngO(E) l n,vìt ngchi udàic at tc cácdanhsáchk c nlà2E.Vi cc pnh tkhóac a nh v trongheap t n O(lgV) l n. Nh v y, t ngchiphí tínhtoánc agi ithu t Prim là O(V lgV+2E lgV)=O(E lgV). 44
3. th có h ng Các th có h nglàcác th trong ó cácc nhn iv i cácnútcóh ng. A H I B C G D E J K F L M Hình 4.7. M tthí d v th có h ng 45
Th ngthì h ngc acácc nhbi uth m iliênh tr c sau (precedencerelationship)trong ngd ng cmôhình hóa. Thí d , th có h ngcóth cdùng mô hìnhhóa m t ngdâys nxu t(assembly line). Trongph nnày, chúngtaxemxétcácgi ithu tsau: -tínhbao óngtruy n(transitive closure) -s pth t topo(topologicalsorting) 46
Tínhbao óngtruy n Trong th có h ng, chúngtaquantâm nt p nh mà n ct m t nhnào ób ngcáchduy tcác c nhtrong th theom th ng ã c n nh. M ttácv màtamu nth chi nlà“thêmm tc nht x nyn ut nt im tcáchnào ó it x ny” th t orab ngcáchthêmt tc cácc nhcótính ch ttrên cg ilàbao óngtruy n c a th . Vì th bao óngtruy nthì th nglà th dày, do ó chúngtadùngcáchbi udi nmatr nk c n. 47
Gi ithu tWarshall Có m tgi ithu t ngi n tínhbao óngtruy nc a m t th cbi udi nb ngmatr nk c n. for y:= 1 to V do for x:=1to V do if a[x,y] then for j:= 1 to V do if a[y, j] then a[x, j]:=true; S. Warshall ragi ithu tnàyn m1962, d atrênm t quansát ngi n: “N ut nt im tcách it nútx n nútyvàcách it núty nnútj,thì s có cách it nút x nnútj.” 48
M tthí d tínhbao óngtruy n ( cho th hình4.7) AB C D EF GHI J K L M A 1 1 00 0 1 1 0 0 0 0 0 0 B 0 1 00 0 0 0 0 0 0 0 0 0 C 1 0 10 0 0 0 0 0 0 0 0 0 Matr nk c n ng D 0 0 01 0 1 0 0 0 0 0 0 0 v ib ckh i u E 0 0 0 1 1 0 0 0 0 0 0 0 0 c agi ithu t F 0 0 0 0 1 1 0 00 0 0 0 0 Warshall G 0 0 10 1 0 1 0 0 1 0 0 0 H 0 0 00 0 0 1 1 1 0 0 0 0 I 0 0 00 0 0 0 1 1 0 0 0 0 J 0 0 0 0 0 0 0 0 0 1 1 1 1 K 0 0 00 0 0 0 0 0 0 1 0 0 L 0 0 0 0 0 0 000 0 0 1 1 M 0 000 0 0 000 0 0 1 1 49
AB C DEF GHI J K L M A 1 1 1 1 1 1 1 0 0 1 1 1 1 B 0 1 0 0 0 0 0 0 0 0 0 0 0 Matr nk c n ngv i C 1 1 1 1 1 1 1 0 0 1 1 1 1 b ccu icùngc agi i D 0 0 0 1 1 1 0 0 0 0 0 0 0 thu tWarshall E 0 0 0 1 1 1 0 0 0 0 0 0 0 F 0 0 0 1 1 1 0 0 0 0 0 0 0 G 1 1 1 11 1 1 0 0 1 1 1 1 Tínhch t 5.3.1 Gi i H 1 1 1 1 1 1 1 1 1 1 1 1 1 thu tWarshalltínhbao I 1 1 11 1 1 1 1 1 1 1 1 1 óngtruy nv ichiphí J 1 1 1 1 1 1 1 0 0 1 1 1 1 O(V3). K 0 0 00 0 0 0 0 0 0 1 0 0 L 1 1 1 1 1 1 1 0 0 1 1 1 1 M 1 111 1 1 1 0 0 1 1 1 1 50
Bàitoáncácl i ing nnh t iv i th có tr ngs (có h ngho ckhông)tacóth mu ixâyd ngm tmatr nchophépng itatìm cl i i ng nnh tt x ny iv im ic p nh. ylàbàitoán nh ngl i ing nnh tchom ic p nh (all-pairsshortest pathproblem). A 4 2 3 1 H I B 1 C G 1 1 2 2 1 1 1 D E J K 5 2 3 F 2 L M 1 51
Gi ithu tFloyd Có th dùngm tph ngphápt ngt nh ph ngpháp Warshall,mà c arab iR. W. Floyd: for y:=1to V do for x:=1to Vdo if a[x,y]>0then for j:=1to V do if a[y,j]>0then if (a[x,j]=0) or (a[x,y]+a[y,j]<a[x,j]) then a[x,j]=a[x,y]+a[y,j]; 52
M tthí d dùnggi ithu tFloyd(cho thihình4.7) AB C DEF GHI J K L M A 0 1 00 0 2 4 0 0 0 0 0 0 Matr nk c n B 0 0 00 0 0 0 0 0 0 0 0 0 ngv ib c C 1 0 00 0 0 0 0 0 0 0 0 0 kh i uc a D 0 0 00 0 1 0 0 0 0 0 0 0 gi ithu tFloyd E 0 0 0 2 0 0 0 0 0 0 0 0 0 F 0 0 0 0 2 0 0 00 0 0 0 0 G 0 0 10 1 0 0 0 0 1 0 0 0 H 0 0 00 0 0 3 0 1 0 0 0 0 I 0 0 00 0 0 0 1 0 0 0 0 0 J 0 0 0 0 0 0 0 0 0 0 1 3 2 K 0 0 00 0 0 0 0 0 0 0 0 0 L 0 0 0 0 0 5 5 00 0 0 0 1 M 0 000 0 0 000 0 0 1 0 53
AB CDEF G HI JKL M Matr nk c n ng A 6 1 56 4 2 4 00 5 6 8 7 v ib ccu ic a B 0 0 00 0 0 0 00 0 0 0 0 gi ithu tFloyd C 1 2 67 5 3 5 00 6 7 9 8 D 0 0 05 3 1 0 00 0 0 0 0 Tínhch t5.3.2 Gi i E 0 0 0 2 5 3 0 0 0 0 0 0 0 thu tFloyd gi ibài F 0 0 0 4 2 5 0 0 0 0 0 0 0 toánnh ngl i i G 2 3 1 31 4 6 0 0 1 2 4 3 ng nnh tgi a H 5 6 4 6 4 7 3 2 1 4 5 7 6 nh ngc pcó I 6 7 57 5 8 4 12 5 6 8 7 ph ct ptínhtoán J 10 11 9 11 9 12 8 0 0 9 1 3 2 O(V3). K 0 0 00 0 0 0 00 0 0 0 0 L 7 8 6 8 6 9 500 6 7 2 1 M 8 979 7 10 600 7 8 1 2 54
Gi ithíchgi ithu tFloyd Gi ithu tFloyd l p V b ctrênmatr nk c na. Saub cl pth y, a[x,j] s ch achi udàinh nh tc a b tk l i inàot nh x n nh j mà không iqua nh ng nhmangch s l nh ny. Ngh alà,xvàjcóth b tk nhnàonh ngnh ng nhtrunggiantrênl i i ph i nh h nhay b ng y. T ib cl pth y,tatínhcácph nt c amatr n a b ng côngth csau: ay[x,j]=min( ay-1[x,j], ay-1[x, y] + ay-1[y,j]) Ch s y ch tr c am tph nt trongmatr n a saub c l pth y. 55
Côngth cnày cminhh ab nghìnhv sau ây. y ay-1[x,y] ay-1[y,j ] j x ay-1[x,j ] 56
X pth t tôpô th có h ngkhôngchutrình(DirectedAcyclicGraph) th có h ngmàkhôngcóchutrình cg ilàcác th có h ngkhôngchutrình (dags). T pth t riêngph nvàx pth t tôpô ChoGlàm t th có h ngkhôngchutrình. Xét quan h th t < c nhngh anh sau: u < v n ucóm tl i it u nvtrongG. Quanh nàycó3tínhch t: (1) V im i nhtrongV[G],not(u<u). (khôngph nx ) (2) n uu< v,thì not( v< u) . (không ix ng) (3) n uu< v và v<w,thì u<w. (Truy n) 57
T pth t riêngph n M tquanh <trênt pSmàth ahaitínhch tb t ix ng và truy nlàm tquanh th t riêngph n (partial ordering) c aS, và m tt pcótrênnóm tquanh th t riêngph n thì cg ilàt pth t riêngph n (partially orderset ). Nh v y, b tk th có h ngkhôngchutrìnhcóth c coi nh là m t t pth t riêngph n. 58
T p th t riêngph n(tt.) M tkhác, gi s S là m t t pth t riêngph n v iquan h th t riêng ph n<,thì S có th c coinh là m t th có h ng mà các nh là nh ng ph n t trong t p S và các c nh c nh ngh a nh sau: (u,v)làm t c nh n u u < v. H n n a,ta có th ch ngminhthêm r ng m t t pth t riêngph n S, có th c coi nh là m t th có h ng, thì không có chutrình. 59
X pth t tôpô ChoG là m t th có h ngkhôngchutrình. M t th t tôpô (topologicalsort)Tc aG là m tth t tuy ntínhmàb otoànth t riêngph nban u trongt p nhV[G]. Ngh alà: n u u < v trongV(t clàn ucóm tl i i t u nv trongG), thì uxu thi ntr cvtrongth t tuy ntínhT. 60
A H I B C G D E J K F L M Cácnúttrong th hìnhtrêncóth cs pth t tôpô theoth t sau: JKL M AG HIFE DB C 61
S pth t tôpô1(Ph ngpháp1) Có vàiph ngpháp s pth t tôpô. Ph ngpháp1 Ý t ngc nb nlàtìmm tnútkhôngcónút isau (no successor)lo ib nórakh i th và anóvàom tdanh sách. L pl iquá trìnhnàycho nkhi th r ngthì s sinhram t danhsách. ong cdanhsáchnàytas cth t tôpô. Algorithm: while thegraph has a node with nosuccessors do removeonesuch nodefrom the graphand addittotheend ofa list. if theloop terminateswiththegraph empty then thelistshowsthereserseof a topologicalorder. else the graph containsa cycle. 62
Hình 4.8 S pth t tôpô b ng ph ngpháp 1 A H I B C G D E J K F L M C B D E F I H G A M L K J J KL MA G H I E F D B C 63
Ph ngpháp2(s px ptôpô) Ph ngphápth hailàth chi ntheoki u tìmki mtheo chi usâutr c và thêmm tnútvàodanhsáchm ikhic n thi tl ym tnútrakh istack ti pt c.Khig pm tnút khôngcónút isauthì tas l yra(pop) m tph nt t nhstack. Algorithm: Start withnodes withno predecessor, putthem in the stack. while thestackis notempty do if thenode attopof thestackhassomesuccessors then pushallitssuccessorsontothestack else pop itfrom the stackandadd ittothe list. 64
1 2 10 4 6 9 8 3 5 7 8 6 5 55 44 4 Hình 4.9 S pth th tôpô 33333 10101010 b ng ph ng pháp 2. 222222 2 2222 1 111111 1 11111 9 7 777777 7 7777777 7 65
Bàitoánnh ng l i ing nnh t t m t nhngu n Th xétbàitoán nh ngl i ing nnh tt m t nhngu n (single-sourceshortest-paths problem): Chom t th G=(V,E), chúngtamu ntìmm tl i ing n nh tt m t nhngu nnào ós V nm inútv V. Bi udi nnh ngl i ing nnh t Chúngtamu ntínhkhôngch tr ngs c anh ngl i ing n nh tmàcònxác nhnh ng nhtrênnh ngl i ing nnh t. Chom t th G=(V,E),taduytrì chom i nh v V m t nh itr c p[v] mà là m t nhkháchay là NIL.Gi ithu t gántr chothu ctính p saochodãycác nh itr cxu t phátt nh v s choral i ing nnh tt s nv. 66
Nh ng l i ing nnh tvàs n i l ng Gi ithu ttìmnh ngl i ing nnh tth ngdùngm tk thu t cg ilàs n il ng (relaxation). S n il nglàm tph ngphápmàliênti pgi mc ntrênc a tr ngs c al i ing nnh tth cs c am i nhcho nkhi c ntrênb ngv itr ngs l i ing nnh t. Nh v y, v im i nh v V,taduytrì thu ctính d[v],màlàc n trênc atr ngs c am tl i ing nnh tt nhngu ns nv. Ta g i d[v] là cl ngl i ing nnh t (shortest pathestimate). Quá trìnhn il ngm tc nh(u,v) baog mvi cth xemtacó th c ithi nl i ing nnh t n v mà angtìmth yb ngcách i qua u và n unh v y,tac pnh t d[v] và p[v]. M tb cn il ng s làmgi m cl ngl i ing nnh t d[v] và c pnh tthu c tính p[v]. 67
2 u 5 9 v Relax(u,v) 2 u 6 v u v 5 5 7 2 Relax(u,v) (a) u v 5 6 2 (b) Hình4.10:S n il ngc am tc nh 68
Gi ithu tDijkstra Gi ithu tnàygi ibàitoánnh ngl i ing nnh tt nh ngu nchom t th có h ng,cótr ngs G=(V,E)trong tr ngh pcáctr ngs c acácc nhlàtr không âm. Gi ithu tnàyduytrì m tt pS c acác nhmàtr ngs c a cácl i ing nnh tt nhngu n ã cxác nh.Ngh a là, v im i nh v S,tacó d[v]=min( cl ngl i ing nnh tt s nv) Gi ithu tliênti nch n nh u V – S v ithu ctính d nh nh t, a u vàoS, và n il ngm ic nh irat u. Tronggi ithu tsau ây,tadùng hàng icó utiên Q ch at tc các nhtrongV-S, l pkhóatheothu ctính d. Và gi nh th G cdi nt b ngcácdanhsáchk c n. 69
procedure dijkstra(G, w, s); /* G is a graph, w is aweightfunction andsis thesourcenode*/ begin for eachvertex v V[G] do /*initialization */ begin d[v]:= ; p[s]:= NIL end; d[s]:=0; S:=;Q:= V[G] while Qis notempty do begin u:=EXTRACT-MIN(Q);S:= S  {u}; for each vertex v Adj[u] do /*relaxation */ if d[v]> d [u]+ w(u, v) then begin d[v]:= d[u]+ w(u,v); p[v]:= u end end end 70
Gi ithu tDijkstra • Vì gi ithu tDijkstraluônluônch n nh “g nnh t” trong V-S avàot pS,nóth cs s d ngchi nl ctham lam. • Gi ithu tthamlamth ngkhông mb o eml il igi i t i utrongtr ngh pt ngquát, nh ng iv ibàitoán này, gi ithu tDijkstrath cs ã eml inh ngl i ing n nh t. • Gi ithu tDijkstrat ngt nh gi ithu tPrim dùng tínhcâybaotrùmt ithi u. Nó c ngdùngm thàng icó utiên tìmm t nh “nh nh t” bênngoàim tt p, a nh ó vàot p, và i uch nhl itr ngs c anh ng nh còn l ibênngoàit p. 71
M tthí d u v u v 10 10 10 0 s 0 s 5 5 5 x y x y 72
u v u v 1 1 8 14 8 13 10 9 10 9 3 3 0 4 s 4 s 2 0 2 7 6 7 6 5 5 5 7 7 2 2 x y x y 73
u v u v 1 8 9 1 8 9 10 9 3 10 6 3 9 2 6 0 0 4 2 7 s 7 4 s 5 5 7 5 7 5 2 2 x y x y (s,u): (s, v): (s, x): (s,y): 74
ph c t p c agi ithu tDijkstra • N uhàng icó utiênQ=V–S cth chi nb i m tm ng tuy ntính, m ithaotácEXTRACT-MIN t n O(V), và có t tc |V|thaotácnh v y, do ó tacóm tchi phí tínhtoánchothaotácnàylàO(V2). • M i nh v V c avàot pS úngm tl n, do ó m i nhtrongcácdanhsáchk c nAdj[v] cxét úngm t l ntrongsu tti ntrìnhc agi ithu t. Vì t ngs nhtrongt tcáccácdanhsáchk c nlà|E|, có t tc |E| b cl pchovòngl pfor, v im il nl pt nO(1). Th igiantínhtoánc agi ithu tlà O(V2 +E)=O(V2). 75
ph c t p c agi ithu tDijkstra • N uhàng icó utiênQ chi nth cb im tc u trúc heap, m ithaotácEXTRACT-MIN t nchi phí O(lgV), và có t tc |V|thaotácnày, do ó tacót ngchi phí cho thaotácEXTRACT-MIN là O(VlgV). Phépgánd[v]:= d[u] + w(u, v) òih im tthaotácc p nh tkhóac a nh v trongheap và nó t nO(lgV). Có t tc |E|thaotácnh v y.Do ó t ngth igiantínhtoánc agi i thu tlà O(VlgV+E lgV). 76
Ch ng 5 Các k thu tthi t k gi ithu t 1
N i dung 1. Quiho ch ng 2. Gi ithu ttham lam 3. Gi ithu tquay lui 2
1.Quiho ch ng Quy ho ch ng(dynamic programming) gi i các bàitoán b ng cách k t h p các l i gi i c a các bàitoán con c a bài toán ang xét. Ph ng pháp này kh d ngkhi các bàitoán con không c l p i v inhau, t c là khi các bàitoán con có dùngchung nh ng bàitoán “cháu” (subsubproblem). Quiho ch ng gi icác bàitoán “cháu” dùng chung này m t l nvàl u l igi i c a chúngtrong m t b ng và sau ó kh i ph itính l ikhi g p l i bàitoán cháu ó. Quiho ch ng c áp d ng cho nh ng bàitoán t i u hóa(optimization problem). 3
B n b c c aquiho ch ng S xây d ng m t gi ithu t quiho ch ng có th c chia làm b n b c: 1. ctr nghóa c utrúc c a l igi i t i u. 2. nh ngh agiá tr c a l igi i t i u m t cách quy. 3.Tínhtr c a l igi i t i utheoki u t d ilên. 4. C u t o l igi i t i u t nh ngthôngtin ã ctính toán. 4
Thí d 1:Nhânxâu matr n Cho m t chu i g m n matr n, và tamu n tínhtích cácmatr n. A1 A2 An (5.1) Tích c axâumatr n này c g ilàm - óng-ngo c- y- (fullyparenthesized ) n u nó là m tmatr n n ho c là tích c a hai xâumatr n m - óng-ngo c- y- . Thí d : A1 A2 A3 A4 có th c m - óng-ngo c- y- theo 5 cách: (A1(A2(A3A4))) (A1((A2A3)A4) ((A1A2)(A3A4)) (A1(A2A3))A4) (((A1A2)A3)A4) 5
Cáchmàta m óngngo c m t xâumatr n có nh h ng r t l n n chi phí tínhtíchxâumatr n. Thí d : A1 10 100 A2 100 5 A3 5 50 (A1(A2A3))th chi n 10.000.5+10.5.50=5000+ 2500 = 7500 phép nhân vô h ng. (A1(A2A3))th chi n 100.5.50+10.100.50 = 25000+ 50000= 75000phép nhân vô h ng. Hai chi phí trên r tkhác bi t nhau. 6
Phátbi ubàitoánnhânxâu matr n Bàitoántínhtíchxâumatr n: '‘Cho m tchu i g m n matr n, v i m i i= 1, 2, , n, matr n Ai có kíchth c pi-1 pi,ta m - óng- ngo ctíchnàysaocho t ithi uhóa t ng s phép nhân vô h ng”. ây là m t bài toán t i u hóathu c lo ikhó. 7
C utrúc c a m tcách m óngngo c t i u B c 1: ctr ng hóa c utrúc c a m t l i gi i t i u. Dùng Ai j ký hi umatr n k t qu c a vi ctính Ai Ai+1 Aj. M t s m óng ngo c t i u c atíchxâumatr n A1.A2 An Táchxâungay t i v trí n mgi a Ak và Ak+1 v i m ttr nguyên k,1 k < n. Ngh alà,tr ctiêntatínhcác chu ima tr n A1 k and Ak+1 n và r i nhânchúng v inhau cho ra A1.n. Chi phí c a s m óng ngo c t i u này= chi phí tính Al k + chí phí tính Ak+1 n, + chi phí nhân chúng l i v i nhau. 8
Di n t l igi i m tcách quy ây, nh ng bàitoán con c atalàbàitoán xác nhchi phí t i u ng v i s m óng ngo c cho chu i Ai.Ai+1 Aj v i 1 i j n. tm[i,j]làt ng s t ithi ucác phép nhân vô h ng c òi h i tínhmatr n Ai j. Chi phí c acách r nh t tính A1 n s c ghi m[1, n]. Gi s r ng s m óng ngo c t i u tách ôi tíchchu i Ai Ai+l Aj t i gi a Ak and Ak+l, v i i k < j.Thì m[i,j] b ng v i chí phí t ithi u tính Ai k và Ak+1 j, c ng v ichiphí nhân haimatr n này l i v i nhau. m[i,j]=m[i,k] + m[k+1,j] + pi-1pkpj. 9
M tcôngth c quy Nh v y, nhngh a quychochi phí t i thi u c a m t s m óngngo ccho Ai Ai+l Aj là nh sau: m[i, j]= 0 n ui=j, =min{m[i,k]+m[k+1, j]+ pi-1pkpj.} n ui<j. (5.2) giúptheo dõicách t o m t l igi i t i u,hãy nh ngh a: s[i, j]: tr c a k t i ó chúngta tách tíchxâuma tr n AiAi+1 Aj t n m t s m óng ngo c t i u. 10
M tnh nxétquantr ng M t nh n xét quan tr ng là ''S m óng ngo c c a xâu con A1A2 Ak bên trong s m óng ngo c t i u c axâu A1A2 An c ng ph ilàm t s m óng ngo c t i u''. Nh v y, m t l i gi i t i u chobàitóantíchxâumatr n ch a ngtrong nó nh ng l igi i t i u c a nh ng bàitoán con. B cth hai c a ph ng phápqui ho ch ng là nh ngh a tr c a l igi i t i u m tcách quytheonh ng l igi i t i u c a nh ng bàitoán con. 11
Tínhnh ngchiphí t i u Thay vì tính l igi i d a vào côngth ccho (5.2) b ng m t gi ithu t quy, chúngta ith c hi n B c 3 c aqui ho ch ng: tínhchi phí t i u b ng cáchti p c n t d ilên. Gi s matr n Ai có kíchth c pi-1 pi v i i = 1, 2 , ,n. u vào là chu itr s . Th t c dùng m t b ngm[1 n,1 n] l u các chi phí m[i,j] và b ngs[1 n, 1 n] l ugiá tr nào c a v trí k mà th c hi n cchi phí t i ukhitínhm[i,j]. Th t cMATRIX-CHAIN-ORDERtr v hai m ng m và s. 12
Th t c tínhhai b ng m và s procedure MATRIX-CHAIN-ORDER(p,m,s); begin n:= length[p]-1; for i:= 1 to n do m[i, i]:= 0; for l:=2to n do /* l: length of the chain */ for i:= 1 to n – l + 1 do begin j:= i + l – 1; m[i, j]:= ; /* initialization */ for k:= i to j-1 do begin q:=m[i, k]+m[k+ 1, j]+ pi-1pkpj; if q<m[i, j] then begin m[i, j]:= q;s[i, j]:= k end end end end 13
M tthí d :Tínhtíchxâu matr n Vì ta nhngh am[i,j] ch cho i<j, ch ph n c a b ng m trên ng chéo chính m i cdùng. Cho cácmatr n v ikíchth c nh sau: A1 30 35 A2 35 15 A3 15 5 A4 5 10 A5 10 20 A6 20 25 Hình5.1trình bày b ng m và s ctính b ith t c MATRIX-CHAIN-ORDER v i n = 6. 14
M tthí d v tínhtíchxâu matrân(tt.) M ng m i 1 2 3 4 5 6 6 15125 10500 51375 3500 5000 0 5 11875 7125 2500 1000 0 j 4 9357 4375 750 0 3 7875 2625 0 2 15750 0 1 0 M ng s Hình 5.1 i 1 2 3 4 5 6 3 3 3 5 5 5 3 3 3 4 j 4 3 3 3 3 1 2 2 1 15
M tthí d v tínhtíchxâu matrân(tt.) m[2,2] m[3,5] p.p25p 0 2500 35.15.20 13000 m[2,5]=min m[2,3] m[4,5] p1p25p 2625 100 35.5.30 7125 m[2,4] m[5m5] p1p45p 43750 35.10.20 11375 = 7125 k = 3for A2 5 Bc 4 c a ph ngpháp qui ho ch ng là t o m t l igi i t i u t nh ngthôngtin ã tínhtoán. 16
B c4: T o m t l igi i t i u Ta dùng m ngs[1 n, 1 n] xác nhcách t t nh t tính tíchxâumatr n. M i ph n t s[i,j] ghitr of k saocho t i ó s m óng ngo c t i u tách ôi xâu AiAi+1 Aj thành hai o n t i Ak và Ak+1. Chotr cchu imatr n A = , b ng s và các ch s i và j,th t c quy MATRIX-CHAIN-MULTIPLY sau âytínhtíchxâumatr n Ai j,.Th t ctr v k t qu qua tham s AIJ. V i l nh g i ban ulà MATRIX-CHAIN-MULTIPLY(A,s, 1, n, A1N) Th t c s tr v k tqu matr ntíchsaucùng v i m ng A1N. 17
Tính l igi i procedure MATRIX-CHAIN-MULTIPLY(A,s, i,j, AIJ); begin if j>ithen begin MATRIX-CHAIN-MULTIPLY(A,s, i,s[i,j], X); MATRIX-CHAIN-MULTIPLY(A,s,s[i, j]+1,j, Y); MATRIX-MULTIPLY(X,Y, AIJ); end else assignAi to AIJ; end; 18
Cácthànhph n c aquyho ch ng Có haithành ph nthen ch tmàm tbàitoán t i uhóa ph i có có th áp d ngqui ho ch ng: (1) ti u c utrúc t i u (optimalsubstructure) và (2) các bàitoáncon trùng l p (overlappingsubproblems). Ti u c utrúc t i u M tbàitoáncótínhch tti u c utrúc t i u n u l igi i t i uch atrongnónh ng l igi i t i u c anh ngbàitoán con. 19
Nh ngbàitoáncontrùng l p Khi m tgi ithu t quy g p l i cùng m tbàitoán con nhi u l n,ta b o r ngbàitoán t i u hóa có nh ng bàitoán contrùng l p. Gi ithu t quy ho ch ng l i d ng nh ng bài toáncon trùng l p b ng cáchgi i m i bàitoán con m t l n, c t l i gi i vàotrong m t b ng mà b ng này s cthamkh o nkhi c n. Cácgi ithu t quy làmvi c t trênxu ng trongkhicác gi ithu tquyho ch ng làmvi c t d ilên, Cáchsau h u hi u h n . 20
Thí d 2:Bàitoánchu iconchungdàinh t M t chu i con (subsequence) c a m t chu i(sequence) là chu i ysaukhi b i m t vài ph n t . Thí d :Z = làm tchu icon c a X = v i chu i ch s . Cho hai chu i X và Y,ta b oZ là chu icon chung (common subsequence) c a X và Y n uZ là m t chu i con c a c hai chu i X và Y. Trongbàitoánchu iconchungdàinh t,ta cchohai chu iX= vàY= vàmu ntìm chu iconchung dài nh t (LCS) c a X và Y. 21
Ti u c utrúc t i u c abàitoánchu icon chungdàinh t Thí d : X= và Y= là LCS c a X and Y. Chochu iX= ,ta nhngh a ti n t th i c a X, v i i =0, 1, ,m,làXi= . nh lý 6.1 ChoX= vàY= lành ng chu i,và Z = là LCS c a X và Y. 1.Nu xm = yn thì zk = xm = yn và Zk-1 là LCS c a Xm-1 và Yn-1. 2.Nu xm yn,thì zk xm hàm ý Z là LCS c a Xm-1 và Y. 3.Nu xm yn,thì zk yn hàm ý Z là LCS c a X và Yn-1. 22
L igi i quy tìm m tLCS c a X và Y,tacóth c ntìmLCS c a X và Yn-1 và LCS c a Xm-1 và Y. Nh ng m itrong hai bàitoán con này có nh ng bàitoán “cháu” tìm Xm-1 và Yn-1. G i c[i,j] là chi u dài c aLCS c a hai chu i Xi và Yj. N u i = 0 hay j = 0,thì LCS có chi u dài 0. Tính ch tti u c u trúc t i u c a bàitoánLCS cho ra côngth c quysau: 0 n u i=0 hayj= 0 c[i,j]=c[i-1,j-1]+1 n u i, j>0 và xi = yj max(c[i,j-1],c[i-1,j]) n u i,j>0vàxi yj (5.3) 23
Tínhchi udài c a m tLCS D avàoph ng trình (5.3),tacóth vi t m tgi i thu t quy tìmchi udài c a m tLCS c a haichu i.Tuy nhiên,chúng ta dùngquiho ch ng tính l igi i theocách t d ilên. Th t cLCS-LENGTHcóhaichu i X= và Y= là uvào. Th t c l ucác tr c[i, j] trong b ngc[0 m,0 n].Nó c ng duytrì b ng b[1 m,1 n] ngi nhóavi c t o l igi i t i u. 24
procedure LCS-LENGTH(X, Y) begin m:=length[X];n:=length[Y]; for i:=1to m do c[i, 0]:=0; for j:= 1 to n do c[0,j]:=0; for i:=1to m do for j:= 1 to n do if xi = yj then begin c[i,j]:= c[i-1,j-1]+1; b[i,j]:= “” end else if c[i – 1,j]>= c[i,j-1] then begin c[i,j]:=c[i – 1,j]; b[i, j]:= “” end else begin c[i,j]:=c[i, j-1];b[i,j]:= “” end end; Hình5.2sau âytrình bày matr n c c athí d . 25
yj B D C A B A 0 0 0 0 0 0 0 xi A 0 0  0  0  1  1  1  B 0 1  1  1  1  2  2  C 0 1  1  2  2  2  2  Hình 5.2 0 1  1  2  2  3  3  B D 0 1  2  2  2  3  3  A 0 1  2  2  3  3  4  B 0 1  2  2  3  4  4  26
T ochu iconchungdàinh t B ng b có th c dùng t o m tLCS c a X= andY= Th tuc quysau âyinra m tLCS c aXvàY. L nh g i utiênlà PRINT-LCS(b,X, n, m). procedure PRINT-LCS(b,X,i,j) Th i giantínhtoán begin c ath t cPRINT- if i 0then if b[i,j]=''  '' then LCS là O(m+n),vìít begin PRINT-LCS(b,X,i-1,j-l ) ; nh t i hay j gi m m t n v trong m i print xi end ch ng c a quy. elseif b[i,j]='''' then PRINT-LCS (b,X,i-1,j) else PRINT-LCS(b,X,i,j-1) end; 27
Thí d 3.Bàitoáncáitúi(Knapsack) '‘M t k tr m t nh p vào m t c a hi utìmth y có n m t hàng có tr ng l ngvàgiá tr khác nhau, nh ng y ch mangtheo m tcáitúicós cch a v tr ng l ng t i a là M.Bàitoán cáitúilàtìm m t t h p các m t hàngmàk tr m nên b vào cáitúi t m t giá tr cao nh t v i nh ngmón hàng mà y mang i.” Bàitoánnày có th gi i b ng qui ho ch ng b ng cách dùng hai b ng cost và best sau ây: cost[i] ch a giá tr t i amàcóth th chi n c v i m t cáitúicós c ch a i cost[i]= cost[i – size[j]]+ val[j] best[i] ch a m thàngcu icùng b vàotúinh m t c giá tr t i a. 28
M tthí d c abàitoáncáitúi value 4 5 10 11 13 name A B C D E Hình5.3 M tthí d c a bàitoán cáitúi 29
Gi ithu tquyho ch ngchobàitoáncáitúi for i:= 0 to M do cost[i]:= 0; for j:= 1 to N do /* each ofitem type*/ begin for i:=1to M do /*imeans capacity*/ if i – size[j]>= 0 then if cost[i]<(cost[i – size[j]]+ val[j])then begin cost[i]:= cost[i – size[j]]+ val[j]; best[i]:= j end; end; 30
M tth hi n c acáitúi K 1 2 3 4 5 6 7 8 9 10 111213 1415 16 17 j=1 cost[k] 0 0 4 4 4 8 8 8 12 12 12 1616 1620 20 20 best[k] A A A A AAA A A A A A A A A j=2 cost[k] 0 0 4 5 5 8 9 10 12 13 14 16 17 18 2021 22 best[k] A B B A B B A B B A B B A B B j=3 cost[k] 0 0 4 5 5 8 1010 12 14 15 16 18 18 2022 24 best[k] A B B A C B A C C A C C A C C j=4 cost[k] 0 0 4 5 5 8 1011 12 14 15 16 18 20 2122 24 best[k] A B B A C D A C C A C C D C C j=5 cost[k] 0 0 4 5 5 8 1011 13 14 15 17 18 20 2123 24 best[k] A B B A C D E C C E C C D E C Hình 5.4 Các m ng cost và best c a m tthí d bàitoán cái túi 31
Ghi Chú: Bàitoán cáitúi có th d dànggi i c n u M không l n, nh ngkhiM l nthì th igian ch ytr nên khôngth ch p nh n c. Ph ng pháp này khôngth làmvi c c khi M và tr ng l ng/kíchth clành ng s th cthayvìs nguyên. Tính ch t5.1.1 Gi ithu t qui ho ch ng gi i bàitoán cái túicóth igian ch y t l v iNM. 32
Gi ithu tthamlam Các gi ithu t t i uhóath ng i qua m t s b c v i m t t p cáckh n ng l ach n t i m i b c. M t gi ithu ttham lamth ng ch n m tkh n ng mà xem nh t tnh t t i lúc ó. T c là,gi ithu t ch n m tkh n ng t i u c c b v i hy v ng s d n n m t l igi i t i utoàn c c. Vàithí d c a gi ithu ttham lam: -Gi ithu tPrim tính câybaotrùm t ithi u -Gi ithu t Dijkstra gi ibàitóan nh ng l i ing n nh t t m t nhngu n(single-sourceshortest paths problem). 33
Bàitoán x p l chchocácho t ng(Activity- Selection Problem) Gi s tacóm t t pS = {1, 2, , n} g m n ho t ngmà cùngmu n s d ngcùng m t tài nguyên,thí d nh m t gi ng òng,màch có th cdùng b i m tho t ng t i m t lúc. M i ho t ng i có th i i m b t u si và m t th i i m k t thúc fi,mà si fi. N u c l ach n, ho t ng i di n ra trongth i kho ng[si, fi). Ho t ng i và j là t ng thích n u th ikho ng[si, fi) và [sj, fj)không ph l p lên nhau (t c là, i và j là t ngthích n u si >= fj hay sj >= fi). Bàitoán x p l ch cácho t ng là ch n ra m tchu icác ho t ng t ngthích v i nhauvàcós ho t ng nhi u nh t. 34
Gi ithu tthamlamchobàitoán x p l chcác ho t ng Trongth t c áp d ng gi ithu tthamlam gi i bàitoán x p l chcác ho t ng,tagi s r ng cácho t ngnh p vào c s ptheoth t t ngc ath i i m k tthúc: f1 f2 fn. procedure GREED-ACTIVITY-SELECTOR(S,f) ; /*sis thearraykeepingthesetofactivitiesandfisthearraykeeping thefinishing times*/ begin n:=length[s]; A :={1};j: = 1; for i:=2to n do if si >= fj then /* i is compatible with allactivitiesinA */ begin A:= A  {i};j:= i end end 35
Th t cGreedy-activity-selector Ho t ng c ch n b ith t c GREEDY-ACTIVITY- SELECTERth ng là ho t ng v i th i i m k t thúc s m nh t mà có th c x p l ch m t cách h p l . Ho t ng c ch ntheocách “thamlam” theongh a nó s l i c h i x p l ch cho c nhi u ho t ngkhác. Gi ithu tthamlam không nh tthi t em l i l igi i t i u. Tuy nhiênth t cGREEDY-ACTIVITY-SELECTOR th ngtìm c m t l igi i t i u cho m tth hi n c a bài toán x p l ch các ho t ng. 36
Hình 5.5 M tthí d i si fi c a bài toán x p l ch 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 1112 14 37
Haithànhph nchính c agi ithu tthamlam Có haitính ch tmàcác bàitoán ph i có có th áp d ng gi ithu tthamlamlà:(1)tínhch t l a ch nthamlam và (2)ti u c utrúc t i u. L a ch n cth chi n b igi ithu tthamlamtùythu c vào nh ng l a ch n ã làm cho n bây gi , nh ngnó khôngtùythu c vào b t k l a ch ntrong t nglaihay nh ng l igi i c a nh ng bàitoán con. Nh v y, m tgi i thu ttham lamti nhànhtheoki u t trênxu ng,th chi n m ilúc m t l a ch nthamlam. Tính ch tti u c utrúc t i u(OptimalSubstructure) M tbàitóancótínhch tti u c utrúc t i u n u m t l i gi i t i uch atrongnónh ng l igi i t i uchonh ng bàitoán con. 38
Gi ithu tthamlamsosánh v iquyho ch ng S khác bi tgi a quiho ch ng và gi ithu ttham lam khi dùng gi i bàitoán t i ulàr t t nh . Bàitoán cái túi d ng 0-1 c nhnghiã nh sau: '‘M t k tr m tnh pvào m t c ahi u tìm th y n lo i món hàngcótr ng l ngvàgiá tr khácnhau (mónhàng th i có giá tr vi ô la và tr ng l ng wi),nh ngch có m tcái túi v i s c ch a v tr ng l nglàM mangcác mónhàng.Bài toáncái túi là tìm m t t h pcácmónhàng mà k tr mnênch n b vàocái túi t c m tgiá tr t i a v inh ng mónhàng mà y l y i.”. Bàitoánnày c g i là bàitoán cáitúi d ng0-1 vì m i món hàngthì ho clàl y i ho c là b l i, k tr mkhông th l y ich m t ph n c amónhàng. 39
Bàitoáncáitúi d ngphân s (Fractional knapsackproblem) Trong bàitoán cáitúi d ng phân s ,tìnhti t c ng nh v y, nh k tr m có th l y i m tph n c a m tmón hàng. C hai bàitoán u có tínhch t ti u c utrúc t i u. i v ibàitoán cáitúi d ng0-1,xét m t t h p n ng M ký mà em l i giá tr c c i. N uta l ymónhàngth j rakh i túi, nh ngmón hàngcòn l i c ng là t h p em l igiá tr l n nh t ng v itr ng l ng t i aM-wjmàk tr m có th l y i t n-1 lo i m thàngtr m t hàng th j. i v ibàitoáncáitúi d ngphân s ,xéttr ng h pkhita l yrakh itúiwj-wký c a m thàngth j,nh ngmónhàng còn l i c nglàt h p em l igiá tr l nnh t ng v itr ng l ngM–(wj–w) mà k tr mcóth l y i t n-1 lo i m t hàngtr m t hàngth j. 40
Bàitoáncáitúi d ngphân s (tt.) Ta dùng gi i thu tthamlam chobàitoán cáitúi d ngphân s và quiho ch ng cho bàitoán cáitúi d ng 1-0. gi i bàitoán cáitúi d ng phân s ,tr ctiêntatính h s giá tr ti ntrên m t n v tr ng l ng (vi/wi )c a t ng m t hàng. K tr m b t u b ng cách l ycàng nhi u càng t t m t hàng có h s vi/wi l n nh t.Khi lo i m thàng này ã c n mà k tr m còncóth mangthêm c n athì y s càng nhi ucàng t t m t hàng có h s vi/wi l n nhì và c nh th cho nkhi y không còn có th mangthêm n a. 41
Hình 5.6 42
procedure GREEDY_KNAPSACK(V,W,M,X,n); /*V,Warethearrayscontainthevaluesandweightsofnobjects orderedsothat Vi/Wi Vi+1/Wi+1.MistheknapsackcapacityandXis solutionvector*/ var rc:real; i:integer; begin for i:=1to n do X[i]:=0; rc :=M; //rc=remaining knapsack capacity// B quath i gian for i:=1to n do s pth t các begin món hàng,gi i if W[i]>rc thenexit; thu t nàycó X[i]:= 1;rc:=rc – W[i] ph c t p O(n). end; if i n then X[i]:=rc/W[i] end 43