Bài giảng Chương 5: Các kỹ thuật thiết kế giải thuật

(5.1) A1 A2 … An

c g i là m - óng-ngo c- y-

n ho c là tích

.

y- c m - óng-ngo c- y- theo

Tích c a xâumatr n này (fullyparenthesized ) n u nó là m tmatr n c a hai xâumatr n m - óng-ngo c- Thí d : A1 A2 A3 A4 có th 5 cách:

5

(A1(A2(A3A4))) (A1((A2A3)A4) ((A1A2)(A3A4)) (A1(A2A3))A4) (((A1A2)A3)A4)

ng

Cách mà ta m óngngo c m t xâumatr n có nh h r t l n n chi phí tính tích xâumatr n.

Thí d :

10 100 5 100 5 50 A1 A2 A3

(A1(A2A3))th chi n 10.000.5 +10.5.50=5000+ 2500

= 7500 phép nhân vô h ng.

ép nhân vô

(A1(A2A3))th chi n 100.5.50 +10.100.50 = 25000+ 50000= 75000ph h ng.

6

Hai chi phí trên r tkh ác bi t nhau.

Phátbi u bàito ánnh ân xâu matr n

ng”. c pi-1 pi,ta m - óng- i= 1, 2, …, n, matr n Ai có kíchth ngo c tích nàysaocho t ithi u hóa t ng s phép nhân vô h

7

ây là m t bài toán t i u hóathu c lo ikh ó.

C utr úc c a m t cách m óngngo c t i u

ctr ng hóa c utr úc c a m t l i gi i t i u.

ký hi umatr n k t qu c a vi c tính

i v trí n mgi a Ak và Ak+1 v i m ttr

cti ênta t ính các chu ima

B c 1: Dùng Ai..j Ai Ai+1…Aj. M t s m óng ngo c t i u c a tích xâumatr n A1.A2… An Tách xâungay t nguyên k, 1 k < n. Ngh a là,tr tr n A1..k and Ak+1..n và r i nhânch úng v inhau cho ra A1.n.

8

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.

Di n t

l

igi

i m t cách

quy

ây, nh ng bàito án con c ata l à 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 j n. i

tm[i,j] l à t ng s t ithi u các phép nhân vô h ng

c tính

tínhmatr n Ai..j. Chi phí c a cách r nh t c ghi m[1, n]. òi h i A1..n s

Gi s r ng s m óng ngo c t i u tách ôi tíchchu i Ai k < j.Th ì m[i,j] b ng Ai+l… Aj t i gi a Ak and Ak+l, v i i tính Ai..k và Ak+1..j, c ng v ichiph í v i chí phí t ithi u nhân haimatr n này l i v i nhau.

m[i,j]=m[i,k] + m[k+1,j] + p

i-1pkpj.

9

M t côngth c

quy

quychochi ph í t i thi u c a m t

Nh v y, nhngh a s m óngngo ccho A i Ai+l… Aj là nh sau:

n ui =j,

m[i, j]= 0

=min{m[i,k]+m[k+1, j]+ p

i-1pkpj.}

(5.2)

n ui

giúptheo d õi cách t o m t l igi

i t i u, hãy nh

ngh a:

tr c a k t i ó chúngta t ách tích xâuma tr n

t

n m t s m óng ngo c t i u.

s[i, j]: AiAi+1…Aj

10

M tnh n xé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 a xâu A1A2…An c ng ph i là m t s m óng ngo c t i u''.

ngtrong n ó nh ng l igi i t i u c a nh ng bàito án

Nh v y, m t l i gi i t i u cho bài tóan tích xâumatr n ch a con.

ng phápqui ho ch

B cth hai c a ph tr c a l igi i t i u m t cách quytheonh ng l igi ng là nh ngh a i t i

11

u c a nh ng bàito án con.

Tínhnh ngchiph í t i u

i d a vào côngth ccho (5.2) b ng m t

Thay vì tính l igi 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 i lên.

c pi-1 pi v i

Gi s matr n Ai có kíchth i = 1, 2 ,..,n.

u vào là chu itr s .

l u các chi phí m[i,j]

l ugi á tr nào c a v trí k mà th c

Th t c dùng m t b ngm[1..n,1..n] và b ngs[1..n, 1..n] hi n cchi ph í t i ukhi t ínhm[i,j].

12

Th t cMATRIX-CHAIN-ORDERtr v hai m ng m và s.

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:= 2 to n do /* l: length of the chain */

for i:= 1 to n – l + 1 do begin

/* initialization */

j:= i + l – 1; m[i, j]:= ; for k:= i to j-1 do begin

i-1pkpj;

then

q:=m[i, k]+m[k+ 1, j]+ p if q

end

end

end

13

M tth í d : Tính tích xâu matr n

Vì ta nhngh am[i,j] ch cho i

c nh sau:

30 35 15 5 10 20 Cho cácmatr n v i kíchth 35 A1 15 A2 5 A3 10 A4 A5 20 25 A6

c tính b ith t c

14

Hình5.1tr ình bày b ng m và s MATRIX-CHAIN-ORDER v i n = 6.

M tth í d v tính tích xâu matr ân(tt.) M ng m

i

1

2

3

5

4

6 0

2500 1000

0

750 0

6 15125 10500 51375 3500 5000 5 11875 7125 0 9357 4375 7875 2625 0 15750 0

j 4 3 2 1

M ng s

Hình 5.1

5 5

4 5 4

i 3 3 3 3

2 3 3 3 2

1 3 3 3 1 1

6 5 j 4 3 2

15

M tth í d v tính tích xâu matr ân(tt.)

0 2500 35.15.20 13000





 





2625 100 35.5.30 7125













4375 0 35.10.20 11375







 



m[2,2] m[3,5] p.p p  2 5  m[2,3] m[4,5] p p p  1 2 5  m[2,4] m[5m5] p p p  1 4 5

m[2,5]=min

= 7125 k = 3for A 2..5

ngph áp qui ho ch ng là t o m t l igi i

16

B c 4 c a ph t i u t nh ngth ôngtin ã tínhto án.

B c4: T o m t l

igi

i t i u

xác nh cách t t nh t

s[i,j] ghitr tính i

Ta dùng m ngs[1..n, 1..n] tích xâumatr n. M i ph n t of k saocho t ó 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.

cchu imatr n A = , b ng s và các

Chotr quy MATRIX-CHAIN-MULTIPLY sau ch s i và j,th t c ây tính tích xâumatr n Ai..j,.Th t ctr v k t qu qua tham s AIJ.

V i l nh g i ban u là

17

MATRIX-CHAIN-MULTIPLY(A,s, 1, n, A1N) Th t c s tr v k tqu matr n tíchsau c ùng v i m ng A1N.

Tính l

igi

i

procedure MATRIX-CHAIN-MULTIPLY(A,s, i,j, AIJ); begin

if j> i then 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;

18

end;

Cácth ànhph n c aquyho ch

ng

có th áp d ngqui ho ch ng: Có haith ành ph nthen ch t mà m t bàito án t i u hóa ph i có

(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 t bàito án có tínhch tti u c utr úc t i u n u l igi

i t i i t i u c anh ng bàito án uch atrong n ó nh ng l igi

19

con.

Nh ng bàito áncontr ùng l p

ithu t quy g p l i cùng m t bàito án con

Khi m tgi nhi u l n,ta b o r ng bàito án t i u hóa có nh ng bàito án contr ùng l p.

Gi ithu t quy ho ch trùng l p b ng cáchgi gi i vàotrong m t b ng mà b ng này s ng l i d ng nh ng bài toáncon i m i bàito án con m t l n, c t l i cthamkh o

nkhi c n.

ithu t

quy làmvi c t ch ng làmvi c t trênxu ng trongkhi c ác i lên, Cáchsau d

20

Cácgi gi ithu tquyho h u hi u h n .

Thí d 2: Bàito ánchu iconchung d àinh t

M t chu i con (subsequence) c a m t chu i(sequence) l à i m t vài ph n t . chu i ysaukhi b

Thí d :Z = l à m tchu icon c a

X = v i chu i ch s <2, 3, 5, 7>.

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.

cchohai

21

Trong bàito ánchu iconchung d àinh t,ta chu i X = và Y= và mu n tìm chu iconchung d ài nh t (LCS) c a X và Y.

Ti u c utr úc t i u c a bàito ánchu icon chung dàinh t

Thí d : X= v à Y=

l à LCS c a X and Y.

nhngh a ti n t th i c a

Chochu iX=,ta X, v i i =0, 1, …,m, l à Xi =.

nh lý 6.1

22

Cho X = và Y= là nh ng chu i, và Z = là LCS c a X và Y. 1. N u xm = yn thì zk = xm = yn và Zk-1 là LCS c a Xm-1 và Yn-1. 2. N u xm yn,th ì zk 3. N u xm yn,th ì zk xm hàm ý Z l à LCS c a Xm-1 và Y. yn hàm ý Z là LCS c a X và Yn-1.

L igi

i

quy

tìm m tLCS c a X và Y,ta c ó th c n tì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 quysau: trúc t i u c a bàito ánLCS cho ra c ôngth c

0 n u i=0 hayj= 0

c[i,j]=c[i-1,j-1]+1 n u i, j>0 v à xi = yj

23

(5.3) max(c[i,j-1],c[i-1,j]) n u i,j>0 v à xi yj

Tínhchi u dài c a m tLCS

ng trình (5.3),ta c ó th vi t m tgi

D a vàoph quy

i thu t tìmchi u dài c a m tLCS c a haichu i.Tuy

ch

ng

tính l

igi

i

nhiên,ch úng ta dùngquiho d theo cách t

i lên.

u vào.

ngi n hóavi c t o

i t i u.

igi

Th t cLCS-LENGTH c ó haichu i X= và Y= là Th t c l u các tr c[i, j] trong b ngc[0..m,0..n]. N ó c ng duytr ì b ng b[1..m,1..n] l

24

procedure LCS-LENGTH(X, Y) begin

for j:= 1 to n do c[0,j]:=0;

“” end

then

m:=length[X];n:=length[Y]; for i:= 1 to m do c[i, 0]:=0; for i:= 1 to 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]:= else if c[i – 1,j]>= c[i,j-1] 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;

25

âytr ình bày matr n c c ath í d . Hình5.2sau

0

0

0

0

0

0

0

B D C A B A yj

xi

1 

1 

0

0 

0 

0 

1 

A

2 

0

1 

1 

1 

1 

2 

B

Hình 5.2

2 

0

1 

1 

2 

2 

2 

C

1 

3 

0

1 

2 

2 

3 

B

2 

0

1 

2 

2 

3 

3 

D

3 

4 

0

1 

2 

3 

2 

A

1 

4 

0

2 

2 

3 

4 

B

26

T ochu iconchung d àinh t

B ng b có th

c dùng

t o m tLCS c a

X= andY=

quysau

âyinra m tLCS c aX v à Y. L nh g i

uti ên là

Th tuc PRINT-LCS(b,X, n, m).

procedure PRINT-LCS(b,X,i,j) begin

Th i gian tínhto án c ath t cPRINT- LCS là O(m+n), vì ít nh t i hay j gi m m t n v trong m i

ch ng c a quy.

if i<> 0 and j<> 0 then if b[i,j]=''  '' then begin PRINT-LCS(b,X,i-1,j-l ) ; print xi end 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 án cái túi(Knapsack)

ng và giá tr khác nhau, nh ng y ch

ng t i a là

t m t giá tr cao nh t v i

'‘M t k tr m t nh p vào m t c a hi u tìmth y có n m t hàng có tr ng l mangtheo m t cái túi có s cch a v tr ng l M. Bàito án cái túi là tìm m t t h p các m t hàng mà k tr m nên b vào cái túi nh ng món hàng mà y mang i.”

ng b ng cách

Bàito án này có th gi i b ng qui ho ch dùng hai b ng cost và best sau ây:

c v i m t

cost[i] ch a giá tr t i a mà có th th chi n cái túi có s c ch a i

cost[i]= cost[i – size[j]]+ val[j]

c

28

best[i] ch a m t hàngcu i cùng b vào túinh m t giá tr t i a.

M tth í d c a bàito án cái túi

value 4

5

10

11

13

name A

B

C

D

E

29

Hình5.3 M tth í d c a bàito án cái túi

Gi ithu tquyho ch

ngcho b àito án cái túi

for i:= 0 to M do cost[i]:= 0; for j:= 1 to N do /* each ofitem type*/ begin

for i:= 1 to 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;

30

end;

M tth hi n c a cái túi

6 7 8 9

10 111213 1415 16 17

8 8 8 12

12 12 1616 1620 20 20

A A A A A A A A A A A A A A A

8 9 10 12 13 14

A B B A B B A B B A

16 17 18 2021 22 B B A B B

8 1010 12 14 15

16 18 18

2022 24 A B B A C B A C C A C C A C C

8 1011 12 14 15

16 18 20

2122 24 A B B A C D A C C A C C D C C

8 1011 13 14 15

17 18 20

K 1 2 3 4 5 j=1 cost[k] 0 0 4 4 4 best[k] j=2 cost[k] 0 0 4 5 5 best[k] j=3 cost[k] 0 0 4 5 5 best[k] j=4 cost[k] 0 0 4 5 5 best[k] j=5 cost[k] 0 0 4 5 5 best[k]

2123 24 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ú:

i

c. c n u M không l n, Bàito án cái túi có th d dànggi nh ngkhiM l nth ì th igian ch ytr nên khôngth ch p nh n

ng pháp này khôngth làmvi c c khi M và tr ng

Ph l ng/kíchth c là nh ng s th cthay v ì s nguyên.

ng gi i bàito án cái

32

Tính ch t5.1.1 Gi ithu t qui ho ch túi có th igian ch y t l v iNM .

Gi ithu tthamlam

ng i qua m t s b

c v i m t c. M t gi ithu ttham ng ch n m tkh n ng mà xem nh t tnh t t i lúc

Các gi ithu t t i u hóath t p cáckh n ng l ach n t i m i b lamth ó.

T c là,gi v ng s d n ithu t ch n m tkh n ng t i u c c b v i hy i t i uto àn c c. n m t l igi

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 i bài tóan nh ng l i ing n

33

nh t t m t nhngu n(single-sourceshortest paths problem).

ng(Activity-

Bàito án x p l chcho c ácho t Selection Problem)

c dùng b i m tho t òng, mà ch có th

Gi s ng mà ta có m t t pS = {1, 2, …, n} g m n ho t cùngmu n s d ng cùng m t tài nguyên,th í d nh m t ng gi ng t i m t lúc.

i m b t i m k t u si và m t th i

c l ach n, ho t ng i di n ra ng i có th i fi. N u

ng i và j là t

M i ho t thúc fi, mà si trongth i kho ng[s i, fi). Ho t ng thích n u th ikho ng[s i, 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).

ng t ngth ích v i nhau và có s ho t ng là ch n ra m tchu i các ng nhi u

34

Bàito án x p l ch cácho t ho t nh t.

Gi ithu tthamlamcho b àito án x p l ch các ho t

ng

gi i bàito án

s r ng cácho t ngnh p vào

ng,tagi t t ng c ath i i m k tth úc:

Trongth t c áp d ng gi ithu tthamlam x p l ch các ho t c s ptheoth f2 … fn.

/*sis

f1 procedure GREED-ACTIVITY-SELECTOR(S,f) ; thearraykeepingthesetofactivitiesandfisthearraykeeping thefinishing times*/ begin

= 1;

n:=length[s]; A :={1};j: for i:= 2 to n do

if si >= fj then /* i is compatible with allactivitiesinA */ begin A:= A  {i};j:= i end

35

end

Th t cGreedy-activity-selector

ng

ng là ho t i m k t thúc s m

c ch n b ith t c GREEDY-ACTIVITY- ng v i th i c x p l ch m t cách h p l . Ho t c

ng l i c h i

Ho t SELECTERth nh t mà có th ch ntheo c ách “thamlam ” theongh a nó s c nhi u ho t x p l ch cho ngkhác.

t em l i l igi i t i u.

c m t l igi ng tìm i t i u cho m tth hi n c a bài

36

Gi ithu tthamlam kh ông nh tthi Tuy nhiênth t cGREEDY-ACTIVITY-SELECTOR th toán x p l ch các ho t ng.

i

si

fi

Hình 5.5 M tth í d 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ó th áp d ng Có hai tính ch t mà các bàito án ph i có gi ithu tthamlam l à:(1) t ínhch t l a ch nthamlam v à (2)ti u c utr úc t i u.

ithu tthamlam t ùythu c cth chi n b igi

i

trênxu ng,th chi n

L a ch n vào nh ng l a ch n ã làm cho n bây gi , nh ng nó nglaihay không tùythu c vào b t k l a ch ntrong t i c a nh ng bàito án con. Nh v y, m tgi nh ng l igi thu ttham lamti n hànhtheoki u t m i lúc m t l a ch nthamlam.

Tính ch tti u c utr úc t i u(OptimalSubstructure)

i t i uchonh

38

M t bài tóan có tínhch tti u c utr úc t i u n u m t l i gi i t i uch atrong n ó nh ng l igi ng bàito án con.

Gi ithu tthamlamso s ánh v iquyho ch

ng

ng và gi ithu ttham lam

S khác bi tgi a quiho ch khi dùng gi i bàito án t i u là 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 p vào m t c ahi u tìm th y n lo i món ng và giá tr khácnhau (m ón hàng th i có giá hàng có tr ng l tr vi ô la và tr ng l ng wi),nh ngch có m t cái túi v i s c ng là M mang các món hàng. Bài toán cái túi ch a v tr ng l là tìm m t t h p các món hàng mà k tr m nênch n b vào cái c m tgi á tr t i a v inh ng món hàng mà y l y túi

t

i.”.

39

Bàito án này c g i là bàito án cái túi d ng0-1 vì m i món hàngth ì ho c là l y i ho c là b l i, k tr mkh ông th l y ich m t ph n c a món hàng.

Bàito án cái túi d ngph ân s (Fractional knapsackproblem)

t c ng nh v y,

Trong bàito án cái túi d ng phân s , tìnhti nh k tr m có th l y i m tph n c a m t món hàng.

C hai bàito án u có tínhch t ti u c utr úc t i u.

i v i bàito án cái tú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 y món hàngth j rakh i túi, nh ng món hàng còn l i c ng là t h p em l igi á tr l n ng t i aM- w j mà k tr m có th l y nh t ng v itr ng l

i t n-1 lo i m t hàngtr m t hàng th j.

ng h pkhita

i v i bàito án cái túi d ngph ân s , xéttr i túi wj -w ký c a m t hàngth

40

j,nh ng món hàng l yrakh còn l i c ng là t h p em l igi á tr l nnh t ng v itr ng ng M – (wj –w) mà k tr m có th l y i t n-1 lo i m t l hàngtr m t hàngth j.

Bàito án cái túi d ngph ân s (tt.)

Ta dùng gi i thu tthamlam cho bàito án cái túi d ngph ân s và quiho ch ng cho bàito án cái túi d ng 1-0.

gi i bàito án cái túi d ng phân s ,tr

n v tr ng l cti ênta t ính h s ng (vi/wi ) c a t ng m t

giá tr ti ntr ên m t hàng.

u b ng cách l y càng nhi u càng t t m t

41

K tr m b t hàng có h s vi/wi l n nh t.Khi lo i m t hàng này ã c n c n ath ì y s càng mà k tr m còn có th mangth êm nhi u cà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.

Hình 5.6

42

procedure GREEDY_KNAPSACK(V,W,M,X,n);

/*V,Warethearrayscontainthevaluesandweightsofnobjects orderedsothat V i/Wi  Vi+1/Wi+1.Mistheknapsackcapacityand Xis solutionvector*/

var rc:real; i:integer; begin

for i:= 1 to n do X[i]:=0; rc :=M; //rc=remaining knapsack

capacity//

for i:= 1 to n do begin i

thenexit;

if W[i]>rc X[i]:= 1;rc:=rc – W[i] B quath i gian s pth t các món hàng,gi thu t này có ph c t p O(n).

end; if i  n then X[i]:=rc/W[i]

43

end

Mã Huffman

n v n

nàyli ênquan

nén file (file

c dùng c nén d li u, ti tki m

Ch compression). Các mã Huffman là k thu t ph bi n và r t h uhi uchovi t 20% n90% l à i n hình.

uti ên c avi c xây d ng mã Huffman là m

B c t n s xu t hi n (frequency) c a m i ký t

trong t p tin

c mã hóa.

Gi s chúng ta có m t t p tin100000 k ý t mà chúng tamu n l u tr

d ng nén.

44

a b

c

d e

f

5

45

13

12

16 9

T n s

Mã có chi u dài c

nh 000

001

010

011 100

101

i 0 101

100

111 1101

1100

Mã có chi u dàithay

t k m t mã nh phâncho k ý t

ó m i ký t d

c di n t

Chúng ta xét bài toánthi (binarycharactercode)theo b ng m ttr àng bit nh phân.

nh (3 bit)

N uch úng ta dùng m t mã có chi u dài c di n t 6 ký t :

a =000,b=001, . .. , f=101

Thì c n t t c 300000bit

mã hóa toàn t p tin.

45

Mã có chi u dàithay

i

i (variable-length code) có th làm

M t mã có chi u dài thay vi c t t h n m t mã có chi u dài c nh, nó cho nh ng ký t hayxu t hi n nh ng mã ng n và nh ng ký t hayxu t hi n nh ng mã dài h n.

a= 0, b= 101, . . .f = 1100

Mã này òi h i:

(45. 1 + 13.3 + 12.3 +16.3+ 9.4+ 5.4).1000 = 224000bits

bi udi n t ptin,ti tki m c 25%.

46

Và y c ng chính là mã t i ucho t ptin n ày.

Mã phi-ti n t

(Prefix-code)

âytach xét nh ng cách mã hóa mà không có mã c a ký t (prefix) c a mã c a m t ký t khác. Nh ng cách

c g i là mã phiti n t (prefix-free-code)

nào là ti n t mã hóa nh v y hay mã ti n t (prefix-code).

c r ng s néntin t i u cth chi n

Có th ch ngminh b i m t cách mã hóa ký t và ó là mã phiti n t .

c a chu ng vì nó làm n gi n s mã hóa

Mã phiti n t và gi i mã.

- S mã hóa là t l i v inhauth ì s bi udi n ngi n;ta ch c n ghép k các mã c a các ký c m i ký t trong t ptin.

47

- S gi i mã c n m t s bi udi nthu nti n cho mã phiti n t sao cho ph n cnh t ra m t cách d dàng. u c a mã

Mã phiti n t và câynh phân

là m t câynh phân v i m i

Bi u di ncho m t mã phiti n t nút lá t ng ng v i các ký t c cho.

i t nút r

Chúngtaph ân gi i m t mã nh phân cho m t ký t nh là y, mà 0 ng v i “r n nút lá c a ký t m t l i sang con bêntr ái” và 1 ngh a là “r sang con bên ph i”.

ng

y (fullbinarytree ). M t cây nh phân Mã t i u c a m t t ptinth cây nh phân

cbi u di n b ng m t y hai là m t cây nh phân mà m i nútkh ôngph i lá có

con.

ó các ký t l yra,th ì câynh phân

t i u có úng|C| n út lá, m i nút lá cho

48

N u C là t p ký t mà t cho mã phiti n t m t ký t , và úng|C|-1 n út n i.

100

100

0

1

0

86

14

1 55

a:45

1

0

0

0

1

30

58

28

14

25

1

0

1

0

1

0

0

1

0

1

f:5

a:45 b:13

c:12

d:16

e:9

c:12

b:13

d:16

14

1

0

e:9

f:5

(a)

(b)

Hình5.7So s ánhhai c ách mã hóa

49

Mã phiti n t và câynh phân(tt.)

ng ng v i m t mã phiti n t , chúngta c ó

Cho m t câyT t th tính t ng s bit c n mã hóa m t t ptin.

V i m i ký t c trong t p ký t C, dùng f(c) ký hi u t n s xu t hi n c a c trong t ptin v à dT(c) là chi u dài c a mã cho ký t c.Th ì s bit òi h i mã hóa t ptin l à

B(T) = f(c)dT(c)

c C

50

Mà chúngta coi l à chi phí c a cây nh phânT.

C u t o mã Huffman

xu t m tgi ithu ttham lam c u t o m t

t i u c g i là mã Huffman (Huffman

Huffman ã mã phiti n t code).

ng ng v i mã t i u u v i m t t p g m|C|

t o ra

Gi ithu t t o m t cây nh phân T t i lên. Gi ithu t b t theoki u t d nút lá và th c hi n m t chu i g m|C| t ác v tr n cây cu i cùng.

u tiên Q, l ytr khóatheo t n s f, c

i có nh n di nhai i t ng có t n s nh nh t tr n

M t hàng dùng l i v i nhau.

i t ng là m t i t

51

K t qu c a vi ctr nhai t n s là t ng t n s c a hai i t ng mà ã ng m i mà ctr n.

(a)

(b)

f:5

e:9

c:12

b:13

d:16

a:45

c:12

b:13

d:16

a:45

14

0 f:5

1 e:9

(c)

(d)

d:16

a:45

a:45

14

25

25

30

0

0 f:5

1 e:9

0 c:12

1 b:13

0 c:12

1 b:13

1 d:16

14

0 f:5

1 e:9

(e)

(f)

a:45

55

100

0

1

0

1

30

25

a:45

55

0

0

1

0 c:12

1 b:13

1 d:16

14

30

25

0

0 f:5

1 e:9

0 c:12

1 b:13

1 d:16

14

Hình 5.8 Các b c c agi

ithu t t o mã Huffman

52

0 f:5

1 e:9

Gi ithu tHuffman

procedure HUFFMAN(C) ; begin

n:=|C|;Q := C ; for i:= 1 to n-1 do begin

z: = ALLOCATE-NODE(); left[z]: =EXTRACT-MIN(Q); right[z]: =EXTRACT-MIN(Q); f[z]:=f[left[z]] +f[right[z]]; INSERT(Q,z);

end

53

end

ph c t p c agi

ithu tHuffman

Gi s Q

c hi n th c hóa b i m t heap nh phân.

c

Cho m t t pC g m n ký t ,vi c kh i t o c a Q th c thi v i th igianO(n).

c th c thich ính xác g m|n|-1 l n, và vì

Vòng l p for m i tác v làmvi c trên heap òi h iO(lgn), v òng l p này óng gópchi ph í O(nlgn) vào th igian t ính toán.

i thu tHUFFMAN

Nh v y,th igian t ính toán c agi trên t p n ký t

s là O(nlgn).

54

Gi ithu tquay lui

ng pháp t ng quát gi i quy t v n :thi

(trialand error ). t k M t ph gi ithu t tìm l i gi icho b ài tóankh ông ph i là bámtheo c xác nh mà là b ng cách m t t p qui lu t tính tóan th và s asai

ng là phân rã quá trìnhth và s a ngth ì nh ng công quy m t cách c di n t

Khuôn m uth ôngth saith ànhnh ng công tác b ph n.Th theo l i tác b ph n này thu nti n và bao g m vi c th m dò m t s h u h nnh ng công tác con.

55

Ta có th coito àn b quá trình này nh là m t quá trình tìm ki m (search process) mà d n d n c u t o và duy t qua m t cây các công táccon.

ng i c aconhi p s (TheKnight ’s

Bàito án Tour Problem)

c di

c ttr ên bàn c t i

Cho m t bàn c n n v i n2 ô. M tcon hi p s – chuy ntu ântheolu tch i c vua – ô uti ên có t a x0, y0.

là tìm m t l csao cho ph toàn

trình g m n2 –1 b c vi ng úng m t l n). V n b bàn c (m i ô

thugi m bàito án ph n2 ô là xét bài toán,

Cách rõ ràng ho c là

-th chi n b c i k ti p, hay

56

-ph át hi n r ngkh ôngki m c b c i h p l nào.

procedure trynextmove; begin initializeselection ofmoves;

repeat

selectnextcandidatefrom list of nextmoves; if acceptable then

begin

recordmove; if board notfull then

begin

try nextmove;

(5.3.1) if notsuccessful then erase previousrecording end

end

until (move wassuccessful)  (nomore candidates)

57

end

Cáchbi udi n d li u

Chúngtadi n t bàn c b ng m tmatr n h.

type index= 1..n ; var h: array[index,index] of integer; h[x, y] = 0: h[x, y] = i: ô ch a h ô ã c vi ng cvi ng t i b cchuy nth i

(1 i n2)

i uki n “board notfull ” có th c di n t b ng “i <

n2”.

c a ô n. u, v: t a

i uki n “acceptable” có th c di n t b ng

58

(1 v n) (h[u,v]=0) (1 u n)

procedure try(i:integer; x,y :index; var q:boolean); var u,v:integer; q1:boolean; begin initializeselectionformoves;

repeat let u, v bethe coordinates ofthe nextmove ;

then (5.3.2)

if (1un)  (1vn)  (h[u,v]=0) then begin h[u,v]:=i; if i

try(i+1, u, v, q1); i f  q1 then h[u,v]:=0

end else q1:=true

end

until q1  (nomorecandidates); q:=q1

59

end

c a ô hi n hành, c ó 8 kh n ng

3

2

4

1



5

8

6

7

60

Cho t a ti p ch n ô k c ánh s t 1 n 8 nh sau: i t i.Ch úng

S tinhch sau cùng

ngi n nh t t c t a u, v t x, y là b ng

saibi tto t ihai m ng a và b. Cách cách c ng

Và k c dùng ánh s ngvi ên(candidate) k ti p.

61

program knightstour(output); const n= 5; nsq= 25; type index= 1..n var i,j: index;q: boolean; s: setof index; a,b: array [1..8] of integer; h: array [index,index] of integer;

procedure try(i:integer; x,y: index; var q:boolean); var k,u,v : integer; q1: boolean; begin k:=0; repeat

k:=k+1;q1:=false; u:=x+a[k]; v:=y+b[k]; if (u in s)  (v in s) then

if h[u,v]=0 then begin

h[u,v]:=i; if i< nsq then begin

try(i+1, u,v,q1); if  q1 then h[u,v]:=0

end else q1:=true

end

until q1  (k=8); q:=q1 end {try};

62

begin

h[1,1]:=1;try(2,1,1,q); if q then

for i:=1 to n do begin

for j:=1 to n do

write(h[i,j]:5);

writeln

s:=[1,2,3,4,5]; a[1]:=2; b[1]:=1; a[2]:=1; b[2]:= 2; a[3]:= –1; b[3]:=2; a[4]:= –2; b[4]:=1; a[5]:= –2; b[5]:= –1; a[6]:= –1; b[6]:= –2; a[7]:=1; b[7]:= –2; a[8]:=2; b[8]:= –1;

end

for i:=1 to n do

else writeln (‘NO

for j:=1 to n do h[i,j]:=0;

63

SOLUTION’) end.

quy

ckh i

ng b ng l nh g i v i t a

kh i

u x0,

u.

Th t c y0 , t

ó chuy n i b t H[x0,y0]:=1; try(2, x 0, y0,q)

Hình5.3.1tr ình bày m t l igi

i

t

c v i v trí <1,1> v in=5.

1

6

15

10

21

14

9

20

5

16

19

2

7

22

11

8

13

24

17

4

25

18

3

12

23

64

T thí d trênta

i

n v i m tki u “gi iquy t v n

” m i:

c i m chính là

ng v l igi

i

c h và ghi l ith ôngtin y c này mà sau ó nó có th b tháo g và xóa i

c này ã không d n

, t c là m t b

y

c i d n

n l i n “tìnhth b c g i là quay lui -

“b v b khiph áthi n r ng b gi i t c”(dead-end).(H ànhvi n ày bactracking.)

65

ithu tquay lui

Khuôn m u t ngqu át c agi

procedure try; begin intializeselection ofcandidates; repeat

select next;

if acceptable then begin

recordit; if solutionincomplete then begin

(5.3.3)

trynextstep; if notsuccessful then cancelrecording

end

end

66

until successful  nomore candidates end

procedure try(i: integer); var k : integer; begin k:=0; repeat

k:=k+1;select k-thcandidate; if acceptable then begin

N u t i m i b ng c, s viên ph ith là nhth ì ki u c m utr ên có th i nh : bi n

record it; if i

(5.3.4)

c g i

try(i+1); if not successful then

cancelrecording

Th t c b ng l nh g i

end

try(1).

end

until successful  (k=m)

end

67

Bàito án8con h u

cC.F.Gausskh

o sát n m1850,

Bàito án này ã nh ng ôngtakh ôngho ànto àngi

iquy t

c.

t vào bàn c saochokh ông có

c

“Támcon h u con h u nào có th t n côngcon h u nào”.

có

c m tth

Dùngkhu ôn m u hình5.3.1,ta s t csaucho b àito án8con h u:

68

procedure try (i:integer); begin

initializeselectionofpositionsfori-thqueen; repeat

makenextselection; if safe then begin

setqueen; if i< 8 then begin

try (i+1); if notsuccessful then removequeen

end

end

until successful  nomorepositions

end

69

Lu t c : M tcon h u có th t n công cáccon h ukh ác n mtr ên ngch éotr ên bàn c . cùng m t hàng, cùng m t c thay l à cùng

Cách bi udi n d li u

Làm cách nào di n t 8con h utr ên bàn c ?

var x: array[1..8] of integer; a: array[1..8] ofBoolean; b: array[b1..b2] ofBoolean; c: array[c1..c2] ofBoolean;

v i

x[i]ch v trí c acon h utr ên c tth i;

a[j] chobi tkh ông có con h utr ên hàngth j;

b[k] cho bi tkh ông có con h utr ên ng chéo th k;

70

ng chéo c[k] cho bi tkh ông có con h utr ên th k.

c xác nh c tính. t t

ng chéo chi u

i +j, và

ng chépchi u

Vi cch ntr cho các m c b1, b2, c1, c2 b i cách mà các ch s c a các m ng b và c Hãych ú ý r ngtr ên cùng m t c các ô s có cùnggi á tr c a t nghai t a trên cùng m t các ô s có cùnggi á tr c ahi uhai t a

diagonal, t t c (i – j ).

ctinh ch nh sau:

Nh v y,ph átbi u setqueen

x[i]:=j; a[j]:=false; b[i+j]:=false;c[i-j]:=false;

Phátbi u removequeen

c chiti

a[j]= true; b[i+j]=true ; c[i-j] := true

t hóa nh sau:

i uki n safe

cdi n t nh sau:

a[j]  b[i+j]  c[i-j]

71

begin

i : integer; q:boolean;

x[i]:=j; a[j]:=false; b[i+j]:=false; c[i-j]:=false; if i<8 then begin

try(i+1,q); if  q then begin

a[j]:=true; b[i+j]:=true; c[i-j]:=true

program eightqueeen1(output); {findonesolution to eight queens problem} var a : array [1..8] of boolean; b : array [2..16] of boolean; c : array [–7..7] of boolean; x : array [1..8] of integer; procedure try(i: integer; var q: boolean); var j: integer; begin

end

j:=0; repeat

end else q:=true

end

j:=j+1; q:=false; if a[j]  b[i+j]  c[i-j] then

until q  (j=8)

end {try};

72

begin

for i:= 1 to 8 do a[i]:=true; for i:= 2 to 16 do b[i]:=true; for i:= –7 to 7 do c[i]:=true; try(1,q); if q then for i:=1 to 8 do

write(x[i]:4);

writeln

end

73

c cho hình v sau: M t l i gi i c a bàito án 8 con h u

H

1

H

2

H

3

H

4

H

5

H

6

H

7

H

8

74

S m r ng: Tìm t t c các l

igi

i

i mà t t c

S m r ng là tìmkh ông ch m t l igi nh ng l

i c a bàito án ã cho.

igi

ngph áp: M tkhi m t l igi

c tìmth y và

i

Ph ghi l i,tati p t c xét ng viên k trongqu á trình ch n

ngvi ên m t cách có h th ng.

c d nxu t t

(5.3.4) và

Khuôn m u t ngqu át ctr ình bàynh sau:

75

procedure try(i:integer); var k: integer; begin

for k:=1 to m do begin

selectk-thcandidate; if acceptable then begin

recordit; if i

end

end

76

end

n gi n hóa i uki n d ng cthayth b ng phát

Trong gi ithu t m r ng, c a quá trình ch n,ph át bi u repeat bi u for

procedure try(i:integer); var j: integer; begin

for j:=1 to 8 do

if a[j]  b[i+j]  c[i-j] then begin

program eightqueens(output); var i: integer; of boolean; a: array [1..8] b: array [2..16] of boolean; c: array [–7..7] of boolean; x: array [1..8] of integer; procedure print; var k : integer; begin

for k : 1 to 8 do write(x[k]:4); writeln end {print};

x[i]:=j; a[j]:=false; b[i+j]:=false; c[i-j]:=false; if i< 8 then try(i+1) else print; a[j]:=true; b[i+j]:= true; c[i-j]:= true;

end

end {try};

77

begin

for i:= 1 to 8 do a[i]:=true; for i:= 2 to 16 do b[i]:=true; for i:= –7 to 7 do c[i]:=true; try(1);

end.

t c 92 l igi

i

Gi ithu t m r ng có th s nsinh t cho bàito án8 con h u.

ith t s khácbi

t

Nh ngth t rach có 12 l igi nhau.

78

cli igi i ó

N

x4

x6

x2

x3

x7

x8

t kê trong b ngsau: x5

M ihai l x1 ========================================================= 1 1 1 1 2 2 2 2 2 2 2 2

876 264 200 136 504 400 72 280 240 264 160 336

8 8 4 5 6 7 7 1 8 3 5 6

3 7 8 2 3 3 1 4 1 8 1 3

5 6 7 7 4 5 5 6 6 7 7 8

7 4 2 4 1 8 8 8 4 5 4 5

6 3 6 8 8 1 4 7 3 6 8 1

4 5 3 3 5 4 3 5 5 4 3 4

2 2 5 6 7 6 6 3 7 1 6 7

79

c tNch s l nth Nh nggi á tr bình c n 161 phép th trong 92 l igi tìm m t ô anto àn.Trung i này.

Câykh ônggiantr ngth ái



ti n di n t gi ithu t quay lui,ta x ây d ng c utr úc cây

ghi nh ng l a ch n ã cth c hi n. C utr úc cây này

c g i là cây khônggiantr ng thái (statespacetree) hay

cây tìmki m (searchtree).

tr ngth ái uti ên tr ckhi qu á

 Nút r c a cây di n t trình tìmki m l igi

 Các nút m c

i b t u.

uti êntrong c ây di n t nh ng l ach n

c làm ng v ith ành ph n uti ên c a l i gi i.

 Các nút m cth haì trong cây di n t nh ng l ach n i và các

c làm ng v ith ành ph nth hai c a l igi

80

m c k ti p t ng t nh th .

M t núttr ên cây KGTT

ng v i l i gi i b ph n mà s có th d n c g i là tri n v ng n u nó t i n l igi ng y

;tr ái l i, nó

Các nút lá di n t nh ngtr c g i là m t l i gi i không tri n v ng. ng h p b t c (deadend) hay

nh ng l igi i y .

Thí d : Cho m t bàito án nh sau: T p bi n:X, Y,Z. Gántr t t p{1,2} v ào các bi nsao choth a mãn các ràng

bu c: X=Y, X Z,Y >Z.

i bàito án b ng m t gi ithu t quaylui.

Hãygi Câykh ông giantr ngth ái c a bàito án này c cho hình

81

v sau:

X=1

X=2

Y=2

Y= 1

Y= 1

Y=2

Z=1

Z=2

Z=2

Z=1

l

igi

i

Hình5.9Th í d v câyKh ông GianTr ngTh ái

82

ph c t p c a gi

ithu tquay lui

ithu tquayluith

ng

Th igian t ínhto án c a cácgi là hàm m (exponential).

nút con, và chi u dài c a l i

i l igi

i là N,th ì

N u m i núttr ên câykh ônggiantr ngth ái có trung bình s núttr ên cây s t l v i N.

ithu t

quy t

ng ng

Th igian t ínhto án c agi v i s núttr ên câykh ônggiantr ngth ái nên có ph c t p hàm m .

83