Luận văn Một số vấn đề về cây

Thuật toán theo lý thuyết

Giả sử G không có chu trình thì nó là một cây và cũng chính là cây bao trùm của nó. Nếu G có chu trình thì ở 1 chu trình đơn nào đó bỏ đi 1 cạnh đồ thị vẫn liên thông. Nếu G còn chu trình đơn thì bỏ tiếp 1 cạnh nữa . cho đến khi không còn chu trình thì ta được đồ thị mới G' nhận được từ G và G' chính là 1 cây bao trùm của G.

Thuật toán trên chỉ có ý nghĩa lý thuyết vì khi số đỉnh lớn, chu trình lớn thì việc kiểm tra chu trình đối với máy tính đòi hỏi nhiều tính toán

2.2 Thuật toán tìm kiếm ưu tiên chiều sâu và chiều rộng

Rất nhiều thuật toán trên đồ thị được xây dựng dựa trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được thăm đúng 1 lần, trong mục này ta sẽ đề cập tới 2 thuật toán rất cơ bản của đồ thị về thăm đỉnh theo nguyên tắc trên. Đó là thuật toán tìm kiếm theo chiều sâu và chiều rộng, chúng được sử dụng để tìm cây bao trùm của đồ thị, ngoài ra chúng còn được sử dụng trong các thuật toán tìm đường đi, tìm các thành phần liên thông, kiểm tra tính liên thông.

 

doc27 trang | Chia sẻ: netpro | Ngày: 10/04/2013 | Lượt xem: 1205 | Lượt tải: 2download
Bạn đang xem nội dung tài liệu Luận văn Một số vấn đề về cây, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
duyÖt c©y ®ã tõ gèc tíi l¸, khi tíi nót con sÏ t¹o ra mét bÝt 0 hoÆc 1 vµ tíi nót l¸ sÏ t¹o ra mét x©u bÝt. Do vËy, m· sinh ra cho mét ký tù sÏ kh«ng lµ phÇn ®Çu cña ký tù kh¸c. 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a e i k o p u H×nh 1.2 VÝ dô nh­ h×nh 1.2 c©y nhÞ ph©n biÓu diÔn m· tiÒn tè cña c¸c ký tù a, e, i, k, o, p, u trong ®ã: a : 000 k : 1100 u : 11111 e : 001 o : 1101 i : 01 p : 11110 ThuËt to¸n m· ho¸ Huffman: Mét sè thuËt to¸n vÒ m· tiÒn tè ®· ra ®êi ®· ®­îc sö dông réng r·i vµ ®em l¹i hiÖu qu¶ cao trong vÊn ®Ò nÐn vµ m· ho¸ th«ng tin. Mét trong nh÷ng thuËt to¸n ®ã lµ Huffman xuÊt hiÖn tõ n¨m 1952, thuËt to¸n nµy m· ho¸ theo ph­¬ng ph¸p kiÓu thèng kª, t¹o ra m· cã ®é dµi thay ®æi kh¸c nhau khi ®· cã b¶ng tÇn sè xuÊt hiÖn cña c¸c ký tù. Qu¸ tr×nh m· ho¸ vµ gi¶i m· phô thuéc vµo viÖc x©y dùng c©y nhÞ ph©n m· ho¸. ThuËt to¸n Huffman t¹o c©y nhÞ ph©n tõ nót l¸ ®Õn nót gèc, ký tù nµo cã tÇn sè cµng cao th× nót l¸ t­¬ng øng cµng gÇn gèc h¬n. ThuËt to¸n: Vµo: B¶ng tÇn sè xuÊt hiÖn c¸c ký tù s¾p xÕp gi¶m dÇn Ra : C©y nhÞ ph©n biÓu diÔn m·, nh¸nh ph¶i lµ 1, tr¸i lµ 0. B­íc 1: LÊy hai phÇn tö cuèi b¶ng tÇn sè xuÊt hiÖn ra khái b¶ng B­íc 2: NÕu phÇn tö nµo ch­a n»m trong c©y nhÞ ph©n th× t¹o ra mét nót l¸ chøa phÇn tö ®ã, phÇn tö nµy chÝnh lµ ký tù. Nèi hai nót t­¬ng øng víi hai phÇn tö nµy víi nhau th«ng qua viÖc t¹o nót cha cña chóng. PhÇn tö cã tÇn sè xuÊt hiÖn lín h¬n lµ nót tr¸i, nhá h¬n lµ nót ph¶i. B­íc 3: TÝnh tæng tÇn sè xuÊt hiÖn cña 2 phÇn tö nµy chÌn vµo b¶ng sao cho phï hîp víi nguyªn t¾c gi¶m dÇn cña b¶ng. PhÇn tö míi cña b¶ng sÏ t­¬ng øng víi nót võa ®­îc t¹o ra ë b­íc 2. B­íc 4: Quay trë l¹i b­íc 1 ®Õn khi b¶ng chØ cßn l¹i 1 phÇn tö. PhÇn tö cuèi cïng t­¬ng øng víi nót gèc cña c©y nhÞ ph©n. VÝ dô: Ta cã kÕt qu¶ m· Huffman cho c¸c ký tù ë b¶ng sau: Ký tù TÇn suÊt M· nhÞ ph©n ChiÒu dµi m· a 0.3 00 2 b 0.2 10 2 c 0.2 11 2 d 0.1 011 3 e 0.1 0100 4 f 0.1 0101 4 C©y nhÞ ph©n biÓu diÔn nh­ h×nh 1.3 a,e,f,d,b,c a,e,f,d b,c e,f,d a e,f d e f b c 0 0 0 0 0 1 1 1 1 1 0,3 0,6 0,2 0,1 0,1 0,1 0,3 0,4 0,2 0,2 H×nh 1.3 Víi thuËt to¸n Huffman tr­êng hîp xÊu nhÊt lµ thêi gian h×nh thµnh c©y nhÞ ph©n lµ O(n) víi n lµ sè ký tù cÇn m· ho¸. Ch­¬ng tr×nh viÕt b»ng ng«n ng÷ Pascal minh ho¹ thuËt to¸n t¹o m· Huffman: Const n = 6; {Sè ký tù cÇn m· ho¸ a, b, c, .....} Type Nod = record S:integer; {tÇn suÊt} Code:String; {m· nhÞ ph©n} Name:char; {tªn ký tù} end; Var a:array[1..n] of Nod; i,m:integer; Procedure InputData; {Khëi t¹o b¶ng tÇn suÊt c¸c ký tù} Var i:integer; begin for i:=1 to n do with A[i] do begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end; end; Procedure FindCode(m:integer); {Sinh m· huffman} Var y,z:nod; k:integer; Begin if m=1 then exit; y:=a[m-1]; a[m-1].s:=a[m-1].s+a[m].s; k:=m-1; While (k>1) and (a[k].s>a[k-1].s) do Begin z:=a[k]; a[k]:=a[k-1]; a[k-1]:=z; k:=k-1; End; FindCode(m-1); z:=a[k]; for i:=k to m-2 do a[i]:=a[i+1]; a[m-1]:=y; a[m-1].code:=z.code+'1'; a[m].code:=z.code+'0'; End; BEGIN InputData; FindCode(n); For i:=1 to n do writeln(a[i].code); END. 4.2 C©y biÓu diÔn biÓu thøc Mét biÓu thøc to¸n häc cã thÓ biÓu diÔn b»ng c©y, ®©y còng lµ vÊn ®Ò h÷u Ých trong viÖc xö lý vµ l­u tr÷ biÓu thøc to¸n häc trong m¸y tÝnh XÐt biÓu thøc ®¹i sè sau: Cã thÓ vÏ 1 c©y nhÞ ph©n nh­ h×nh 1.4 biÓu diÔn biÓu thøc A, trong ®ã mçi ®Ønh trong mang dÊu cña mét phÐp tÝnh, gèc cña c©y mang phÐp tÝnh sau cïng cña A, ë ®©y lµ dÊu nh©n ký hiÖu: *, mçi l¸ mang 1 sè hoÆc mét ch÷ ®¹i diÖn cho sè. a * + - / b c d 2 H×nh 1.4 Mét phÐp duyÖt c©y lµ tiÒn thø tù nÕu th¨m gèc tr­íc råi sau ®ã th¨m con tr¸i nh­ lµ mét c©y con víi ph­¬ng ph¸p th¨m gèc tr­íc vµ cuèi cïng th¨m con ph¶i nh­ lµ mét c©y con víi ph­¬ng ph¸p th¨m gèc tr­íc. DuyÖt c©y nh­ vËy mang tÝnh ®Ö quy. Khi duyÖt c©y trªn theo tiÒn thø tù ta cã: * + a b - c / d 2 C¸ch viÕt biÓu thøc theo tiÒn thø tù lµ ký ph¸p Balan. B»ng duyÖt c©y ta cã thÓ tÝnh ®­îc gi¸ trÞ biÓu thøc, ngoµi ph­¬ng ph¸p tiÒn thø tù cßn cã thÓ duyÖt c©y theo ph­¬ng ph¸p ph¸p kh¸c ®Ó tÝnh gi¸ trÞ biÓu thøc tïy vµo yªu cÇu vµ ®Æc ®iÓm cña tõng bµi to¸n. 4.3 C©y quyÕt ®Þnh Cã nh÷ng bµi to¸n phô thuéc vµo c¸c quyÕt ®Þnh. Mçi quyÕt ®Þnh th× cã thÓ cã nhiÒu kÕt côc vµ nh÷ng kÕt côc cuèi cïng chÝnh lµ lêi gi¶i cña bµi to¸n. §Ó gi¶i nh÷ng bµi to¸n nh­ vËy, ng­êi ta biÓu diÔn mçi quyÕt ®Þnh b»ng mét ®Ønh cña ®å thÞ vµ mçi kÕt côc lµ 1 l¸ cña quyÕt ®Þnh. Mét c©y ®­îc x©y dùng nh­ trªn gäi lµ c©y quyÕt ®Þnh. Trong nhiÒu bµi to¸n Tin gÆp ph¶i, cã thÓ dïng c©y quyÕt ®Þnh ®Ó m« h×nh ho¸ tõ ®ã viÖc cµi ®Æt sÏ dÔ dµng thuËn tiÖn h¬n. VÝ dô: h×nh 1.5 lµ c©y quyÕt ®Þnh biÓu diÔn viÖc s¾p xÕp 3 sè kh¸c nhau a, b, c a ? b a ? c b ? c b ? c a ? c c<a<b c<b<a b<c<a b<a<c a<c<b a<b<c b<a a<b c<a a<c c<b b<c c<b b<c c<a a<c H×nh 1.5 §o¹n ch­¬ng tr×nh sau thÓ hiÖn cho c©y trªn: Var a, b, c: Integer; Function Can(x,y: Integer): Boolean; Begin if x > y then Can:=True Else Can:=False; End; Begin Readln(a,b,c); If Can(a,b) then Begin If Can(a,c) then Begin if Can(b,c) then Writeln(c,' ',b,' ',a) Else Writeln(b,' ',c,' ',a); End Else Writeln(b,' ',a,' ',c); End Else Begin If Can(b,c) then Begin if Can(a,c) then Writeln(c,' ',a,' ',b) Else Writeln(a,' ',c,' ',b); End Else Writeln(a,' ',b,' ',c); End; End. 4.4 C©y s¾p xÕp vµ t×m kiÕm S¾p xÕp vµ t×m kiÕm lµ mét trong nh÷ng vÊn ®Ò c¬ b¶n trong kü thuËt lËp tr×nh, c©y nhÞ ph©n còng cã kh¸ nhiÒu øng dông quan träng trong vÊn ®Ò nµy. Ta cã thÓ m« h×nh ho¸ viÖc s¾p xÕp vµ t×m kiÕm b»ng c©y tõ ®ã ta cã thÓ ®¸nh gi¸ c¸c kü thuËt nµy tõ gãc ®é vÒ c©y. 4.4.1 S¾p xÕp chÌn víi t×m kiÕm nhÞ ph©n ý t­ëng ®­îc b¾t ®Çu nh­ sau, cho 1 danh s¸ch ch­a s¾p xÕp h·y t×m 1 phÇn tö x bÊt kú nµo ®ã trong danh s¸ch, râ rµng ®Ó t×m ta ph¶i lÇn l­ît xÐt tõng phÇn tö cho tíi khi nµo b¾t gÆp phÇn tö cÇn t×m, nÕu danh s¸ch lín th× thêi gian t×m rÊt l©u. B©y giê víi mét danh s¸ch ®· s¾p xÕp, chia ®«i danh s¸ch vµ lÊy phÇn tö lµ t ë vÞ trÝ chia ®«i ®Ó so s¸nh. NÕu t = x th× dõng, nÕu t < x v× danh s¸ch ®· s¾p xÕp nªn x chØ cã thÓ n»m bªn nöa ph¶i danh s¸ch nªn ta chØ viÖc t×m kiÕm trong 1 nöa danh s¸ch bªn ph¶i vµ gi¶m ®i kh¸ nhiÒu c«ng viÖc t×m kiÕm. NÕu x < t th× t­¬ng tù, ta chØ viÖc t×m bªn nöa tr¸i, ®èi víi viÖc t×m kiÕm cho lÇn sau víi c¸c danh s¸ch con nöa tr¸i hoÆc nöa ph¶i ta thùc hiÖn t­¬ng tù nh­ vËy mét c¸ch ®Ö quy. a) Tõ nh÷ng ý t­ëng thuËt to¸n ta x©y dùng c©y nhÞ ph©n t×m kiÕm cho mét danh s¸ch nh­ sau: - Chän 1 phÇn tö bÊt kú lµm gèc - TÊt c¶ c¸c phÇn tö cã gi¸ trÞ £ gèc th× thuéc c©y con tr¸i - TÊt c¶ c¸c phÇn tö cã gi¸ trÞ > gèc th× thuéc c©y con ph¶i - §èi víi c¸c c©y con th× còng cã tÝnh chÊt t­¬ng tù nh­ vËy VÝ dô c©y nhÞ ph©n t×m kiÕm cho danh s¸ch 12, 10, 6, 11, 15, 13, 16, 19, 18 nh­ h×nh 1.6: 12 15 18 10 6 11 13 16 19 H×nh 1.6 b) S¾p xÕp chÌn b»ng viÖc t×m nhÞ ph©n vÞ trÝ ®óng. Cã thÓ t¹m gäi lµ ph­¬ng ph¸p s¾p xÕp chÌn nhÞ ph©n. ý t­ëng nh­ sau: cho tr­íc mét danh s¸ch ®· s¾p xÕp A, cÇn chÌn 1 phÇn tö míi x vµo A sao cho danh s¸ch lu«n ®­îc s¾p xÕp. §Çu tiªn ta t×m vÞ trÝ ®óng cña x trong A sau ®ã chÌn x vµo ®óng vÞ trÝ nµy trong A, ta cã danh s¸ch A = A È {x} lu«n ®­îc s¾p xÕp. §Ó t×m ®­îc vÝ trÝ ®óng cÇn chÌn cña x trong A ta sö dông ph­¬ng ph¸p t×m kiÕm nhÞ ph©n, chÌn theo c¸ch nµy gäi lµ chÌn nhÞ ph©n. VÝ dô ®Ó s¾p xÕp B = x1, x2, x3, ... xn ta thùc hiÖn nh­ sau: A := f; For i:=1 to n do Begin - T×m vÞ trÝ ®óng cña xi trong A theo ph­¬ng ph¸p t×m nhÞ ph©n - ChÌn xi vµo A theo ®óng vÞ trÝ võa t×m ®­îc (A := A È {xi}) End; KÕt qu¶ A lµ danh s¸ch s¾p xÕp cña B. Ch­¬ng tr×nh Pascal sau s¾p xÕp t¨ng dÇn theo ph­¬ng ph¸p chÌn nhÞ ph©n Const n = 9; Ds : Array[1..n] of Integer = (1,9,1,6,3,10,10,8,7); {Ham tra lai vi tri dung cua Pt trong danh sach} Function FindNp(l,r,Pt: Integer): Integer; Var t: Integer; Begin If Pt<=Ds[l] then FindNp:=l Else If Pt>=Ds[r] then FindNp:= r + 1 Else Begin Repeat t:= (l + r) div 2; If Pt = ds[t] then Begin FindNp:=t+1; Exit End Else If Pt<ds[t] then r:=t Else l:=t; Until r=l+1; FindNp:=l+1; End; End; Var i, j, vt, s: Integer; Begin For i:=2 to n do Begin vt:= FindNp(1,i-1,ds[i]); {Chen dung vi tri sao cho ds luon duoc sap xep} s:=ds[i]; For j:=i-1 Downto vt do ds[j+1]:=ds[j]; ds[vt]:=s; End; For i:=1 to n do Write(ds[i]:3); End. 4.4.2 ThuËt to¸n s¾p xÕp hoµ nhËp Gi¶ sö ta cã danh s¸ch ch­a ®­îc s¾p 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 cã thÓ dïng c©y nhÞ ph©n m« t¶ qu¸ tr×nh s¾p xÕp danh s¸ch theo thø tù t¨ng dÇn nh­ sau: C©y nhÞ ph©n víi gèc ®­îc g¸n lµ chÝnh lµ danh s¸ch ®ã. C¸c con cña gèc ®­îc g¸n theo nguyªn t¾c: Con bªn tr¸i g¸n nöa danh s¸ch ®Çu, con bªn ph¶i g¸n nöa danh s¸ch cßn l¹i (danh s¸ch g¸n ë gèc c©y con tr¸i vµ c©y con ph¶i hoÆc b»ng nhau vÒ sè l­îng hoÆc chªnh lÖch nhau 1 phÇn tö). Cø tiÕp tôc cho tíi khi c©y nhÞ ph©n cã mçi l¸ ®­îc g¸n 1 phÇn tö trong d·y. §ã lµ c©y nh­ h×nh 1.7 8, 2, 4, 6, 9, 7, 10, 1, 5, 3 8, 2, 4, 6, 9 7, 10, 1, 5, 3 8, 2, 4 6, 9 7, 10, 1 5, 3 8, 2 4 6 9 8 2 7, 10 1 7 10 5 3 H×nh 1.7 §©y lµ c©y nhÞ ph©n ®Çy ®ñ ch­a ph¶i c©y s¾p xÕp cña d·y ®· cho ë trªn 8 2 7 10 2, 8 4 6 9 7, 10 1 5 3 2, 4, 8 6, 9 1,7, 10 3, 5 2, 4, 6, 8,9 1, 3,5, 7, 10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 H×nh 1.8 §Ó cã c©y nhÞ ph©n s¾p xÕp cña mét d·y, tr­íc hÕt c©y ®­îc x©y dùng t­¬ng t­¬ng tù nh­ vËy, mçi l¸ t­¬ng øng víi mçi phÇn tö cña d·y. B­íc ®Çu tiªn 2 phÇn tö ®­îc hoµ nhËp vµo 1 danh s¸ch theo thø tù t¨ng dÇn, danh s¸ch t­¬ng øng nµy nh­ mét nót cha, 2 phÇn tö ®­îc hoµ nhËp lµ nót con. Sau ®ã ta tiÕp tôc hoµ nhËp c¸c cÆp nót t­¬ng tù nh­ vËy cho tíi toµn bé danh s¸ch ®­îc s¾p xÕp l¹i theo thø tù t¨ng dÇn vµ c©y biÓu diÔn cho d·y lµ c©y nhÞ ph©n c©n ®èi ®­îc m« t¶ nh­ h×nh 1.8 C¸c b­íc thuËt to¸n trªn ®­îc m« t¶ trªn lµ ®· vËn dông thuËt to¸n hoµ nhËp hai danh s¸ch ®· ®­îc s¾p xÕp thµnh mét danh s¸ch míi ®­îc s¾p xÕp, thuËt to¸n nµy theo nguyªn t¾c sau: - So s¸nh phÇn tö bÐ nhÊt trong danh s¸ch trong danh s¸ch thø nhÊt víi phÇn tö bÐ nhÊt trong danh s¸ch thø 2. - Qu¸ tr×nh trªn ®­îc lÆp l¹i cho 2 danh s¸ch nhËn ®­îc ë b­íc trªn - Sau mét sè b­íc sÏ gÆp hai tr­êng hîp sau: a) C¶ 2 danh s¸ch trë thµnh rçng. Trong tr­êng hîp nµy, c¸c phÇn tö cã mÆt trong danh s¸ch hoµ nhËp chÝnh lµ danh s¸ch cÇn x¸c ®Þnh b) Mét danh s¸ch trë thµnh rçng, cßn danh s¸ch kia kh¸c rçng. Trong tr­êng hîp nµy ®­a c¸c phÇn tö cßn l¹i (trong danh s¸ch kh«ng rçng) nèi vµo cuèi cña danh s¸ch hoµ nhËp. §é phøc t¹p thuËt to¸n cña thuËt to¸n trªn lµ O(nlogn) trong ®ã n lµ sè phÇn tö hoµ nhËp Ch­¬ng tr×nh b»ng ng«n ng÷ Pascal thÓ hiÖn thuËt to¸n hoµ nhËp nh­ sau: Const n = 10; Type Vec = Array[1..n] of Integer; Const cm:Vec = (-3,3,-1,4,1,5,6,7,-8,-9); Var x,y:Vec; Procedure Viet; Var i:byte; Begin For i:=1 to n do Write(x[i]:3); Writeln; End; Procedure Hoa_nhap2p(x:Vec; p,m,n:Integer; Var z:Vec); Var i,j,k: Integer; Begin i:=p;j:=m+1;k:=p; While (i<=m) and (j<=n) do Begin If x[i]<x[j] Then Begin z[k]:=x[i];inc(i); End Else Begin z[k]:=x[j];inc(j);End; Inc(k); End; If i>m Then for K:=j to n Do z[k]:=x[k] Else for k:=i to m Do z[n+k-m]:=x[k]; End; Procedure Merge(l,r:integer); Var i,m:integer; Begin If l<r Then Begin m:=(l+r) div 2; Merge(l,m); Merge(m+1,r); For i:=l to r do y[i]:=x[i]; Hoa_nhap2p(y,l,m,r,x); End; End; BEGIN X := cm; Viet; Merge(1,n); Viet; END. 4.4.3 ThuËt to¸n s¾p xÕp nhanh S¾p xÕp 1 danh s¸ch cã nhiÒu thuËt to¸n, mçi thuËt to¸n ®Òu cã nh÷ng ­u nh­îc ®iÓm. Trong c¸c thuËt to¸n s¾p xÕp th× thuËt s¾p xÕp nhanh (Quick sort) tá ra cã nhiÒu ­u ®iÓm ®­îc sö dông phæ biÕn vµ rÊt hiÖu qu¶. Nguyªn t¾c cña thuËt to¸n nµy cã tÝnh ®Ö quy cã thÓ sö dông c©y nhÞ ph©n ®Ó m« t¶ thuËt to¸n nµy. ThuËt to¸n cã thÓ ®­îc m« t¶ tãm t¾t nh­ sau: VÝ dô ®Ó s¾p xÕp danh s¸ch a1, a2, ..., an thuËt to¸n b¾t ®Çu b»ng viÖc lÊy ngÉu nhiªn 1 phÇn tö lµm chèt nh­ng th­êng th× phÇn tö ®Çu tiªn ®­îc chän lµm chèt. Nh­ danh s¸ch trªn ta chän a1 lµm chèt khi ®ã danh s¸ch ®­îc ph©n ®o¹n thµnh 2 danh s¸ch con, mét danh s¸ch con gåm c¸c phÇn tö nhá h¬n a1 theo thø tù xuÊt hiÖn, cßn danh s¸ch con kh¸c gåm c¸c phÇn tö lín h¬n a1 còng theo thø tù xuÊt hiÖn. Sau khi ®· cã hai danh s¸ch con th× a1 ®­îc ®Æt vµo sau cïng cña danh s¸ch con gåm c¸c phÇn tö nhá h¬n a1, nh­ vËy sau a1 lµ danh s¸ch con gåm c¸c phÇn tö lín h¬n a1. Thñ tôc nµy ®­îc lÆp l¹i mét c¸ch ®Ö quy cho mçi danh s¸ch con cho tíi khi nµo mçi danh s¸ch con chØ chøa mét phÇn tö theo thø tù xuÊt hiÖn cña nã. Víi kÕt qu¶ nµy ta ®­îc mét danh s¸ch ®· ®­îc s¾p xÕp. VÝ dô cho danh s¸ch: 3, 5, 7, 8, 1, 9, 2, 6; Cã thÓ dïng c©y nhÞ ph©n biÓu diÔn thuËt to¸n s¾p xÕp nhanh ®Ó s¾p xÕp danh s¸ch nµy nh­ h×nh 1.9 3, 5, 7, 8, 1, 9, 2, 4, 6 1, 2, 3 5, 7, 8, 9, 4, 6 1 2, 3 4, 5 7, 8, 9, 6 2 3 4 5 6, 7 8, 9 9 8 6 7 H×nh 1.9 Danh s¸ch lóc ch­a s¾p xÕp lµ gèc, danh s¸ch ®­îc s¾p xÕp lµ danh s¸ch mµ mçi phÇn tö cña nã lµ l¸ cña c©y. Ch­¬ng tr×nh thÓ hiÖn thuËt to¸n s¾p xÕp nhanh nh­ sau: Uses Crt; const Max = 10; type List = array[1..Max] of Integer; var Data: List; I: Integer; procedure QuickSort(var A: List; Lo, Hi: Integer); procedure Sort(l, r: Integer); var i, j, x, y: integer; begin i := l; j := r; x := a[(l+r) DIV 2]; repeat while a[i] < x do i := i + 1; while x < a[j] do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1; end; until i > j; if l < j then Sort(l, j); if i < r then Sort(i, r); end; Begin {QuickSort}; Sort(Lo,Hi); End; Begin {QSort} { Khëi t¹o ngÉu nhiªn 10 phÇn tö } Randomize; for i := 1 to Max do Data[i] := Random(3000); Writeln; {S¾p xÕp c¸c phÇn tö b»ng Quick Sort} QuickSort(Data, 1, Max); Writeln; for i := 1 to 10 do Write(Data[i]:8); End. Ng­êi ta ®· chØ ra r»ng ®é phøc t¹p cña thuËt to¸n lµ O(nlog2n) II. C©y bao trïm 1. §Þnh nghÜa vµ c¸c tÝnh chÊt §Þnh nghÜa: Cho ®å thÞ G = víi sè ®Ønh n lín h¬n 1. Gi¶ sö G' lµ ®å thÞ bé phËn cña G (G' nhËn ®­îc tõ G b»ng c¸ch bá ®i mét sè c¹nh nh­ng vÉn gi÷ nguyªn ®Ønh). NÕu G' = lµ mét c©y th× G' gäi lµ c©y bao trïm cña G. Theo ®óng tÝnh chÊt vÒ c©y. G' lµ c©y bao trïm ph¶i cã n - 1 c¹nh vµ lµ mét ®å thÞ liªn th«ng kh«ng cã chu tr×nh. Trong mét ®å thÞ cã thÓ cã nhiÒu c©y bao trïm. e a b d c e a b d c a) b) h×nh 2.1 VÝ dô c©y nh­ h×nh 2.1.b lµ mét c©y bao trïm cña ®å thÞ trong h×nh 2.1.a §Þnh lý: Cho ®å thÞ G = , G cã c©y bao trïm khi vµ chØ khi G lµ ®å thÞ liªn th«ng. Chøng minh: §iÒu kiÖn cÇn: Gi¶ sö G cã c©y bao trïm lµ G'. Ta chØ ra G lµ liªn th«ng. ThËt vËy, nÕu G kh«ng liªn th«ng th× tån t¹i cÆp ®Ønh x, y mµ gi÷a chóng kh«ng ®­îc nèi bëi ®­êng nµo, mµ gi÷a x, y còng lµ c¸c ®Ønh cña G'. Chøng tá G' kh«ng liªn th«ng, tr¸i víi gi¶ thiÕt G' lµ mét c©y. §iÒu kiÖn ®ñ: Gi¶ sö G lµ liªn th«ng ta chøng minh G cã c©y bao trïm, thËt vËy v×: - NÕu trong G kh«ng cã chu tr×nh th× theo ®Þnh nghÜa G lµ mét c©y, ®ã lµ c©y bao trïm. - NÕu trong G cã chu tr×nh th× bá ®i 1 c¹nh trong chu tr×nh ®ã ta ®­îc G' liªn th«ng vµ kh«ng cã chu tr×nh, G' lµ c©y bao trïm. 2. C¸c thuËt to¸n t×m c©y bao trïm XÐt ®å thÞ G = liªn th«ng cã n ®Ønh, ta cã c¸c thuËt to¸n t×m c©y bao trïm nh­ sau: 2.1 ThuËt to¸n theo lý thuyÕt Gi¶ sö G kh«ng cã chu tr×nh th× nã lµ mét c©y vµ còng chÝnh lµ c©y bao trïm cña nã. NÕu G cã chu tr×nh th× ë 1 chu tr×nh ®¬n nµo ®ã bá ®i 1 c¹nh ®å thÞ vÉn liªn th«ng. NÕu G cßn chu tr×nh ®¬n th× bá tiÕp 1 c¹nh n÷a ... cho ®Õn khi kh«ng cßn chu tr×nh th× ta ®­îc ®å thÞ míi G' nhËn ®­îc tõ G vµ G' chÝnh lµ 1 c©y bao trïm cña G. ThuËt to¸n trªn chØ cã ý nghÜa lý thuyÕt v× khi sè ®Ønh lín, chu tr×nh lín th× viÖc kiÓm tra chu tr×nh ®èi víi m¸y tÝnh ®ßi hái nhiÒu tÝnh to¸n 2.2 ThuËt to¸n t×m kiÕm ­u tiªn chiÒu s©u vµ chiÒu réng RÊt nhiÒu thuËt to¸n trªn ®å thÞ ®­îc x©y dùng dùa trªn c¬ së duyÖt tÊt c¶ c¸c ®Ønh cña ®å thÞ sao cho mçi ®Ønh cña nã ®­îc th¨m ®óng 1 lÇn, trong môc nµy ta sÏ ®Ò cËp tíi 2 thuËt to¸n rÊt c¬ b¶n cña ®å thÞ vÒ th¨m ®Ønh theo nguyªn t¾c trªn. §ã lµ thuËt to¸n t×m kiÕm theo chiÒu s©u vµ chiÒu réng, chóng ®­îc sö dông ®Ó t×m c©y bao trïm cña ®å thÞ, ngoµi ra chóng cßn ®­îc sö dông trong c¸c thuËt to¸n t×m ®­êng ®i, t×m c¸c thµnh phÇn liªn th«ng, kiÓm tra tÝnh liªn th«ng... Tr­íc khi ®i vµo 2 thuËt to¸n, ta sÏ ®Ò cËp tíi 1 yÕu tè c¬ b¶n cÊu thµnh nªn ý t­ëng cña nhiÒu thuËt to¸n trong ®å thÞ ®ã lµ kü thuËt quay lui. §©y lµ mét kü thuËt chÝnh trong kü thuËt lËp tr×nh cã nhiÒu ¸p dông, ®Æc biÖt lµ ¸p dông trong gi¶i thuËt t×m kiÕm theo chiÒu s©u. 2.2.1 Kü thuËt quay lui Néi dung cña kü thuËt quay lui cã thÓ tãm t¾t nh­ sau: Dïng c©y quyÕt ®Þnh, cßn l¸ th× biÓu thÞ 1 lêi gi¶i cã thÓ. §Ó t×m nghiÖm b»ng kü thuËt quay lui, tr­íc tiªn t¹o ra d·y quyÕt ®Þnh (cµng dµi cµng tèt) ®Ó tiÕn tíi lêi gi¶i. D·y quyÕt ®Þnh cã thÓ biÓu thÞ mét ®­êng ®i trong c©y quyÕt ®Þnh. Mçi khi biÕt ®­îc kh«ng thÓ cã lêi gi¶i tõ bÊt kú d·y quyÕt ®Þnh nµo th× ta quay lui l¹i ®Ønh cha cña ®Ønh hiÖn t¹i ®Ó h­íng tíi lêi gi¶i b»ng d·y quyÕt ®Þnh kh¸c (nÕu cã thÓ). Thñ tôc tiÕp tôc cho tíi khi t×m ®­îc lêi gi¶i hoÆc lµ kÕt luËn kh«ng cã lêi gi¶i. VÝ dô cho 1 tËp A = {1, 2, 3, 4} h·y t×m tËp con cña A gåm 3 phÇn tö sao cho tæng c¸c phÇn tö cña tËp con nµy lµ 8. Tr­íc hÕt ta x©y dùng c©y quyÕt ®Þnh cho bµi to¸n nµy nh­ sau: 6 7 8 9 1 2 3 4 3 4 2 3 4 H×nh 2.2 Mçi mét nh¸nh lµ 1 phÇn tö cña mét tËp con 3 phÇn tö nµo ®ã cña A, mét d·y liªn tiÕp ®­êng ®i gåm 3 nh¸nh tõ gèc tíi l¸ lµ mét tËp con cña A, mçi mét l¸ lµ tæng cña mét tËp con. D·y quyÕt ®Þnh cho lêi gi¶i nh­ sau: §Çu tiªn ®i theo c¸c nh¸nh 1 - 2 - 3 tæng d·y ë l¸ lµ 6 . Kh«ng ph¶i, quay lui mét nh¸nh vÒ nh¸nh 2 ®i vµo nh¸nh 4 ®­îc: 1 - 2 - 4 ë l¸ lµ 7 . Kh«ng ®óng quay l¹i vÒ nh¸nh 1 ®i tiÕp nh¸nh 3 vµ 4 ®­îc: 1 - 3 - 4 ë l¸ lµ 8, ®©y lµ nghiÖm cÇn t×m, vËy tËp con cÇn t×m lµ {1, 3, 4} §©y còng lµ bµi to¸n tæ hîp cã tÝnh ®Ö quy, râ rµng ë ®©y ta thÊy ®­îc mét ¸p dông cña c©y trong kü thuËt nµy. 2.2.2 ThuËt to¸n t×m kiÕm theo chiÒu s©u B­íc 1: LÊy mét ®Ønh bÊt kú lµm gèc cña c©y bao trïm B­íc 2: X©y dùng ®­êng ®i tõ ®Ønh nµy b»ng c¸ch lÇn l­ît ghÐp thªm c¸c c¹nh vµo, sao cho mçi c¹nh ghÐp míi sÏ nèi ®Ønh cuèi cïng trªn ®­êng ®i víi ®Ønh ch­a thuéc ®­êng ®i. B­íc nµy thùc hiÖn cho tíi khi nµo kh«ng thÓ ghÐp thªm c¹nh míi ®­îc n÷a. B­íc 3: NÕu ®­êng ®i chøa tÊt c¶ c¸c ®Ønh cña ®å thÞ G th× ®ã chÝnh lµ c©y bao trïm cÇn t×m. Ng­îc l¹i th× thùc hiÖn tiÕp b­íc sau ®©y: B­íc 4: Quay lui l¹i ®Ønh tr­íc ®Ønh cuèi cïng cña ®­êng ®i vµ x©y dùng ®­êng ®i míi xuÊt ph¸t tõ ®Ønh nµy. NÕu kh«ng x©y dùng ®­îc ®­êng ®i míi tõ ®Ønh nµy th× lïi tiÕp l¹i mét ®Ønh n÷a trªn ®­êng ®i vµ lÆp l¹i qu¸ tr×nh x©y dùng ®­êng míi cµng dµi cµng tèt. B­íc 5: V× ®å thÞ lµ h÷u h¹n nªn qu¸ tr×nh trªn sau mét sè h÷u h¹n b­íc sÏ dõng l¹i vµ cho ta c©y bao trïm cña G = 2.2.3 ThuËt to¸n t×m kiÕm theo chiÒu réng: B­íc 1: Chän mét ®Ønh lµm gèc cña c©y B­íc 2: GhÐp c¸c c¹nh liªn thuéc víi ®Ønh nµy. C¸c ®Ønh míi kÒ víi gèc trong b­íc nµy ®Òu n»m trªn møc 1 cña c©y (víi thø tù tuú ý). B­íc 3: TiÕp tôc víi mçi ®Ønh ë møc 1, ta ghÐp c¸c c¹nh liªn thuéc nã sao cho chóng kh«ng t¹o nªn chu tr×nh. C¸c ®Ønh kÒ ®­îc t¹o ra ë b­íc nµy n»m trªn møc 2 cña c©y. B­íc 4: Qu¸ tr×nh nµy sÏ dõng l¹i sau mét sè b­íc lµm viÖc (do tËp c¹nh h÷u h¹n) vµ tÊt c¶ c¸c ®Ønh cña ®å thÞ ®Òu ®­îc ghÐp vµo c©y. 2.3 C¸c ch­¬ng tr×nh thÓ thiÖn cho c¸c thuËt to¸n: 2.3.1 Ch­¬ng tr×nh Pascal vÒ thuËt to¸n quay lui thÓ hiÖn c©y ë h×nh 2.2 { m lµ tæng cña tËp con, n lµ sè phÇn tö cña tËp A, k lµ sè phÇn tö cña tËp con cña A} Var s: Array[1..10] Of Integer; t,n,k,m,tg: Integer; Procedure Try(h,a:Integer); Var i: Integer; Begin h:=h+1; For i:=a to n-(k-h) do Begin s[h]:=i; If h<k then Try(h,i+1) Else Begin tg:=0; For t:=1 to k do tg:= tg+ s[t]; if tg = 8 then For t:=1 to k do Write(s[t]:3); Writeln; End; End; End; Begin n:=4; k:=3; m:=8; Try(0,1); {T¹o c©y b¾t ®Çu tõ møc 0} End. 2.3.2 Ch­¬ng tr×nh Pascal thÓ hiÖn thuËt to¸n t×m kiÕm ­u tiªn theo chiÒu s©u vµ chiÒu réng t×m c©y bao trïm Uses Crt; Var mG,mT : Array[1..100,1..100] of Integer; {mG: mt ke cua do thi G mT: mt ke cua cay bao trum cho dt G} n: Integer; ChuaXet: Array[1..100] Of Boolean; Queue: Array[1..100] of Integer; tl: Char; {Nhap du lieu cho do thi} Procedure NhapDl; Var i,j: Integer; Begin {Nhap du lieu cho do thi G} Write('So dinh: '); Readln(n); For i:=1 to n do Begin ChuaXet[i]:=True; Queue[i]:=0; For j:=i+1 to n do Begin Write('a',i,j,' = '); Readln(mG[i,j]); mG[j,i]:=mG[i,j]; End; mG[i,i]:=0; End; {Khoi tao du lieu cho cay bao trum} For i:=1 to n do For j:=1 to n do mT[i,j]:=0; End; Procedure Display; Var i,j: Integer; Begin Writeln('Ma tran ke cua do thi'); For i:=1 to n do Begin For j:=1 to n do Write(mG[i,j]:3); Writeln; End; Writeln; Writeln('Ma tran ke cua cay bao trum'); For i:=1 to n do Begin For j:=1 to n do Write(mT[i,j]:3); Writeln; End; End; {Thu tuc tim cay bao trum theo chieu sau} Procedure Dfs(v: Integer); Var u: Integer; Begin ChuaXet[v]:=False; {Dinh v da duoc tham} For u:=1 to n do If (mG[v,u]0) and (ChuaXet[u]) then Begin {Duyet nhung canh ke voi v} mT[v,u]:=mG[v,u]; {Bo sung vao tap canh cua cay} mT[u,v]:=mT[v,u]; Dfs(u); End; End; {Tim cay bao trum cua do thi theo chieu rong} Procedure Bfs(v: Integer); Var i,u,First,Last: Integer; Begin First:=1; Last:=1; Queue[Last]:=v; ChuaXet[v]:=False; {Dinh v da duoc tham} While First<=Last do Begin {Trong khi hang doi chua rong} u:=Queue[First]; Inc(First); For i:=1 to n do If (mG[u,i]0) and (ChuaXet[i]) then Begin {Duyet nhung canh ke voi v} mT[u,i]:=mG[u,i]; {Bo sung vao tap canh cua cay} mT[u,i]:=mT[i,u]; ChuaXet[i]:=False; Inc(Last); Queue[Last]:=i; End; End; End; BEGIN NhapDl; Write('Chon chieu sau hay chieu rong (s/r)? '); Readln(tl); If Upcase(tl) = 'S' then Dfs(1) Else Bfs(1); Display; END. 3. C©y bao trïm bÐ nhÊt 3.1 §Þnh nghÜa: Cho ®å thÞ n ®Ønh G = liªn th«ng, n > 1. Mçi c¹nh u Î U ta g¸n cho nã träng sè l(u). Gi¶ sö G' = <X, U') lµ c©y bao trïm cña G. Ký hiÖu gäi lµ träng sè hay lµ ®é dµi cña G'. Ký hiÖu ¡ lµ tËp c¸c c©y bao trïm cña G, khi ®ã nÕu c©y bao trïm g Î ¡ tho¶ m·n l(g) = Min {l(g') / g' Î ¡} th× ta nãi r»ng g lµ c©y bao trïm bÐ nhÊt trong G. 3.2 ThuËt to¸n t×m c©y bao trïm bÐ nhÊt Cho ®å thÞ G = víi sè ®Ønh n t×m c©y bao trïm bÐ nhÊt cña G. 3.2.1 ThuËt to¸n Kruskal ThuËt to¸n sÏ x©y dùng tËp c¹nh cña c©y bao trïm nhá nhÊt theo tõng b­íc. Tr­íc hÕt s¾p xÕp c¸c c¹nh cña ®å thÞ G theo thø tù kh«ng gi¶m cña ®é dµi. B¾t ®Çu tõ tËp c¹nh cña c©y lµ rçng , ë mçi b­íc ta sÏ lÇn l­ît duyÖt trong danh s¸ch c¹nh ®· s¾p xÕp, tõ c¹nh cã ®é dµi nhá ®Õn c¹nh cã ®é dµi lín h¬n, ®Ó t×m ra c¹nh mµ viÖc bæ sung nã vµo tËp c¹nh cña c©y kh«ng t¹o thµnh chu tr×nh trong tËp nµy. ThuËt to¸n sÏ kÕt thóc khi ta thu ®­îc 1 tËp c¹nh gåm n - 1 c¹nh. Cô thÓ thuËt to¸n cã thÓ m« t¶ nh­ sau: - B­íc 1: Chän c¹nh u1 tho¶ m·n l(u1) = min {l(u) : u Î U} ®Æt U1 = {u1} - B­íc 2: Chän u2 tho¶ m·n : l(u2) = min{l(u) : u Î U\U1} ®Æt U2 = {u1, u2} .......... - B­íc k + 1: Gi¶ sö ®· cã tËp Uk = {u1, u2, ..., uk} chän uk+1 tho¶ m·n l(uk+1) = min(l(u) : u Î U\Uk} ®Æt Uk+1 = Uk È {uk+1} Chó ý ë c¸c b­íc, c¹nh míi ®­îc chän ph¶i kh«ng lËp thµnh chu tr×nh víi c¸c c¹nh ®· chän ë c¸c b­íc tr­íc. ThuËt to¸n dõng l¹i l¹i ë b­íc thø n - 1. VËy c©y T = t×m ®­îc lµ c©y bao trïm ng¾n nhÊt. 3.2.2 ThuËt to¸n Prim ThuËt to¸n Prim cßn ®­îc gäi lµ ph­¬ng ph¸p l©n cËn gÇn nhÊt. Trong ph­¬ng ph¸p nµy, b¾t ®Çu tõ mét ®Ønh s tuú ý cña ®å thÞ, ®Çu tiªn ta nèi s víi ®Ønh l©n cËn gÇn nã nhÊt, ch¼ng h¹n lµ ®Ønh y. NghÜa lµ trong sè c¸c c¹nh kÒ cña ®Ønh s, c¹nh (s, y) cã ®é dµi nhá nhÊt. TiÕp theo, trong sè c¸c c¹nh kÒ víi 2 ®Ønh s hoÆc y ta t×m c¹nh cã ®é dµi nhá nhÊt, c¹nh nµy dÉn ®Õn ®Ønh thø ba z, vµ ta thu ®­îc c©y bé phËn gåm 3 ®Ønh vµ 2 c¹nh. Qu¸ tr×nh nµy sÏ ®­îc tiÕp tôc cho tíi khi ta thu ®­îc ®­îc c©y gåm n ®Ønh vµ n - 1 c¹nh, c©y ®ã còng lµ c©y bao trïm nhá nhÊt cÇn t×m. C¸c b­íc thuËt to¸n nh­ sau: - B­íc 1: Chän u1 sao cho l(u1) = min{l(u)} víi u Î U ®Æt U1 = {u1} - B­íc 2: Chän u2 sao cho l(u2) = min{l(u)} víi u Î U\U1 vµ u kÒ víi 1 c¹nh thuéc U1 ......... - B­íc k +1: Gi¶ sö ®· cã Uk = {u1, u2, ..., uk} Chän uk + 1 sao cho l(uk+1) = min{l(u)} víi u Î U\Uk vµ u kÒ víi 1 c¹nh thuéc Uk. Víi thuËt to¸n Prim, c¹nh míi ®­îc chän còng ph¶i kh«ng lËp thµnh chu tr×nh víi c¸c c¹nh ®· chän ë c¸c b­íc tr­íc. ThuËt to¸n dõng ë b­íc n - 1. KÕt luËn: c©y T = lµ c©y bao trïm ng¾n nhÊt cña G. * VÒ h×nh thøc thuËt to¸n Prim phøc t¹p h¬n thuËt to¸n Kruskal nh­ng vÒ k

Các file đính kèm theo tài liệu này:

  • docLVANCH5.DOC
  • rarBAOCAO.rar
  • docBttat.doc
  • rarCAIDAT.rar
  • rarNdLVan.rar
  • docTomTat.doc
Tài liệu liên quan