Môn học: Phân tích và thiết kế giải thuật-Chương 5

Chia sẻ: Phan Thi Ngoc Giau | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

92
lượt xem 11
download

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

Các kỹ thuật thiết kế giải thuật-Quy hoạch động 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

Chủ đề:

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

Lưu

Nội dung Text: Môn học: Phân tích và thiết kế giải thuật-Chương 5

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