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.
Bạn đang xem trước 20 trang tài liệu Luận văn Một số vấn đề về cây, để xem tài liệu hoàn chỉnh 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 cha 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µ lu 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 cha 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 cha ®î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 ®ñ cha 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 nhng 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 cha 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 nhng 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 cha 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 nhng vÒ k
Các file đính kèm theo tài liệu này:
LVANCH5.DOC
BAOCAO.rar- Bttat.doc
- CAIDAT.rar
- NdLVan.rar
- TomTat.doc
