Chương 5: Các kỹ thuật thiết kế giải thuật

Chia sẻ: Ba Xoáy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

63
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Quy hoạch động giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét. Phương pháp này khả dụng khi các bài toán con không độc lập với nhau, tức là khi các bài toán con có dùng chung những bài toán " cháu"

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 5: Các kỹ thuật thiết kế giải thuật

Ch ng 5 Các k thu t thi t k gi i thu t 1
N i dung 1. Qui ho ch ng 2. Gi i thu t tham lam 3. Gi i thu t quay lui 2
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). 3
B nb c c a qui ho ch ng S xây 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. 4
Thí d 1: Nhân xâu ma tr n Cho m t chu i g m n matr n, và ta mu n tính tích các ma tr n. A1 A2 … An (5.1) c g i là m - óng-ngo c- y- Tích c a xâu ma tr n nà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) 5
Cách mà ta 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. 6
Phát bi u bài toán nhân xâu ma tr n Bài toán tính tích xâu ma tr n: '‘Cho m t chu i 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ó. 7
C u trúc c a m t cách m óng ngo c t i u B 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. 8
Di n t l i gi i m t cách quy ây, nh ng bài toán con c a ta là bài toán xác nh chi 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. t m[i, j] là t ng s t i thi u các phép nhân vô h ng c òi h i tính ma tr n Ai..j. Chi phí c a cá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ích chu 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 i thi u tính Ai..k và Ak+1..j, c ng v i chi phí nhân hai ma tr n này l i v i nhau. m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj. 9
M t công th c quy Nh v y, nh ngh a quy cho chi phí t i thi u c a m t s m óng ngo c cho Ai Ai+l… Aj là nh sau: m[i, j] = 0 n u i = j, = min {m[i, k] + m[k + 1, j] + pi-1pkpj.} n u i < j. (5.2) giúp theo dõi cách t o m t l i gi i t i u, hãy nh ngh a: s[i, j]: tr c a k t i ó chúng ta tách tích xâu ma tr n AiAi+1…Aj t n m t s m óng ngo c t i u. 10
M t nh n xét quan tr 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''. Nh v y, m t l i gi i t i u cho bài tóan tích xâu ma tr n ch a ng trong nó nh ng l i gi i t i u c a nh ng bài toán con. B c th hai c a ph ng pháp qui ho ch ng là nh ngh a tr c a l i gi i t i u m t cách quy theo nh ng l i gi i t i u c a nh ng bài toán con. 11
Tính nh ng chi phí t i u Thay vì tính l i gi i d a vào công th c cho (5.2) b ng m t gi i thu t quy, chúng ta i th c hi n B c 3 c a qui ho ch ng: tính chi phí t i u b ng cách ti p c n t d i lên. Gi s ma tr n Ai có kích th c pi-1 pi v i i = 1, 2 ,.., n. u vào là chu i tr s . Th t c dùng m t b ng m[1..n, 1..n] l u các chi phí m[i, j] và b ng s[1..n, 1..n] l u giá tr nào c a v trí k mà th c hi n c chi phí t i u khi tính m[i, j]. Th t c MATRIX-CHAIN-ORDER tr v hai m ng m và s. 12
Th t c tính hai 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 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 t thí d : Tính tích xâu ma tr n nh ngh a m[i, j] ch cho i < j, ch ph n c a b ng m Vì ta trên ng chéo chính m i c dùng. Cho các ma tr n v i kích th c nh sau: A1 30 35 A2 35 15 A3 15 5 A4 5 10 A5 10 20 A6 20 25 Hình 5.1 trình bày b ng m và s c tính b i th t c MATRIX-CHAIN-ORDER v i n = 6. 14
M t thí d v tính tích xâu ma trân (tt.) M ng m i 1 2 3 4 5 6 15125 10500 51375 3500 5000 0 6 11875 7125 2500 1000 0 5 j4 9357 4375 750 0 7875 2625 0 3 15750 0 2 0 1 M ng s Hình 5.1 i 1 2 3 4 5 3 3 3 5 5 6 3 3 3 4 5 j4 3 3 3 1 2 3 1 2 15
M t thí d v tính tích xâu ma trân (tt.) m[2, 2]  m[3, 5]  p.p2p5  0  2500  35.15.20  13000  m[2,5] = min m[2,3]  m[4,5]  p1p2p5  2625 100  35.5.30  7125 m[2,4]  m[5m5]  p p p  4375  0  35.10.20  11375  145 = 7125 k = 3 for A2..5 B c 4 c a ph ng pháp qui ho ch ng là t o m t l i gi i t i u t nh ng thông tin ã tính toán. 16
B c 4: T o m t l i gi i t i u Ta dùng m ng s[1..n, 1..n] xác nh cách t t nh t tính tích xâu ma tr n. M i ph n t s[i, j] ghi tr of k sao cho 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. Cho tr c chu i ma tr n A = , b ng s và các ch s i và j, th t c quy MATRIX-CHAIN-MULTIPLY sau ây tính tích xâu ma tr n Ai..j,. Th t c tr v k t qu qua tham s AIJ. V i l nh g i ban u là MATRIX-CHAIN-MULTIPLY(A,s, 1, n, A1N) Th t c s tr v k t qu ma tr n tích sau cùng v i m ng A1N. 17
Tính l i gi 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 assign Ai to AIJ; end; 18
Các thành ph n c a quy ho ch ng Có hai thành ph n then ch t mà m t bài toán t i u hóa ph i có có th áp d ng qui ho ch ng: (1) ti u c u trúc t i u (optimal substructure) và (2) các bài toán con trùng l p (overlapping subproblems). Ti u c u trúc t i u M t bài toán có tính ch t ti u c u trúc t i u n u l i gi i t i u ch a trong nó nh ng l i gi i t i u c a nh ng bài toán con. 19
Nh ng bài toán con trùng l p Khi m t gi i thu t quy g p l i cùng m t bài toán con nhi u l n, ta b o r ng bài toán t i u hóa có nh ng bài toán con trùng l p. Gi i thu t quy ho ch ng l i d ng nh ng bài toán con trùng l p b ng cách gi i m i bài toán con m t l n, c t l i gi i vào trong m t b ng mà b ng này s c tham kh o n khi c n. quy làm vi c t trên xu ng trong khi các Các gi i thu t gi i thu t quy ho ch ng làm vi c t d i lên, Cách sau h u hi u h n . 20