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

1

Ch ng 5

Các k thu t thi t k gi i thu t

2

N i dung

1. Qui ho ch ng

2. Gi i thu t tham lam

3. Gi i thu t quay lui

3

1. Qui ho ch ng

Quy ho ch ng (dynamic programming) gi i các bài toán

b ng cách k t h p các l i gi i c a các bài toán con c a bài

toán ang xét.

Ph ng pháp này kh d ng khi các bài toán con không c

l p i v i nhau, t c là khi các bài toán con có dùng chung

nh ng bài toán “cháu” (subsubproblem).

Qui ho ch ng gi i các bài toán “cháu” dùng chung này

m t l n và l u l i gi i c a chúng trong m t b ng và sau ó

kh i ph i tính l i khi g p l i bài toán cháu ó.

Qui ho ch ng c áp d ng cho nh ng bài toán t i u

hóa (optimization problem).

4

B n b c c a qui ho ch ng

â d ng m t gi i thu t qui ho ch ng có th c chia

làm b n b c:

1. c tr ng hóa c u trúc c a l i gi i t i u.

2. nh ngh a giá tr c a l i gi i t i u m t cách quy.

3. Tính tr c a l i gi i t i u theo ki u t d i lên.

4. C u t o l i gi i t i u t nh ng thông tin ã c tính

toán.

5

Thí d 1 Nhân xâu ma tr n

Cho m t chu i <A1

, A2

, …, An

> g m n matr n, và ta mu n

tính tích các ma tr n.

A1 A2 … An

(5.1)

Tích c a xâu ma tr n này c g i là m - óng-ngo c- y-

(fully parenthesized ) n u nó là m t ma tr n n ho c là tích

c a hai xâu ma tr 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

)

6

á à a m óng ngo c m t xâu ma tr n có nh h ng

r t l n n chi phí tính tích xâu ma tr n.

Thí d : A1

10 100

A2 100 5

A3

5 50

(A1

(A2A3

)) th c hi n

10.000.5 + 10.5.50 = 5000 + 2500

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

(A1

(A2A3

)) th c hi n

100.5.50 + 10.100.50 = 25000 + 50000 = 75000 phép nhân vô

h ng.

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

7

Phát bi u bài toán nhân xâu ma tr n

à á í í â

'‘Cho m t chu i <A1

, A2

, …, An

> g m n matr n, v i m i

i = 1, 2, …, n, ma tr n Ai

có kích th c pi-1 pi

, ta m - óng￾ngo c tích này sao cho t i thi u hóa t ng s phép nhân vô

h ng”.

ây là m t bài toán t i u hóa thu c lo i khó.

8

C u tr c c a m t cách m óng ngo c t i u

c 1: c tr ng hóa c u trúc c a m t l i gi i t i u.

Dùng Ai..j ký hi u ma tr n k t qu c a vi c tính

Ai Ai+1…Aj

.

M t s m óng ngo c t i u c a tích xâu ma tr n A1

.A2… An

Tách xâu ngay t i v trí n m gi a Ak

và Ak+1 v i m t tr

nguyên k, 1 k < n. Ngh a là, tr c tiên ta tính các chu i ma

tr n A1..k and Ak+1..n và r i nhân chúng v i nhau 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.