Phân tích và thiết kế giải thuật: Các kỹ thuật thiết kế giải thuật - Chương 5

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 5: 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 bài toán con của bài toán đang xét.
Nội dung trích xuất từ tài liệu:
Phân tích và thiết kế giải thuật: Các kỹ thuật thiết kế giải thuật - Chương 5Ch ng 5 Các k thu t thi t k gi i thu t 1N i dung1. Qui ho ch ng2. Gi i thu t tham lam3. Gi i thu t quay lui 21. Qui ho ch ng Quy ho ch ng (dynamic programming) gi i các bài toánb 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àitoán ang xét.Ph ng pháp này kh d ng khi các bài toán con không cl p i v i nhau, t c là khi các bài toán con có dùng chungnh 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àym 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 uhóa (optimization problem). 3B nb c c a qui ho ch ngS 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. 4Thí d 1: Nhân xâu ma tr nCho m t chu i g m n matr n, và ta mu ntí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íchc 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- theo5 cách: (A1(A2(A3A4))) (A1((A2A3)A4) ((A1A2)(A3A4)) (A1(A2A3))A4) (((A1A2)A3)A4) 5Cách mà ta m óng ngo c m t xâu ma tr n có nh h ngr 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 n10.000.5 + 10.5.50 = 5000 + 2500 = 7500 phép nhân vô h ng.(A1(A2A3)) th c hi n100.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. 6Phát bi u bài toán nhân xâu ma tr nBà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ó. 7C u trúc c a m t cách m óng ngo c t i uB 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ínhAi Ai+1…Aj.M t s m óng ngo c t i u c a tích xâu ma tr n A1.A2… AnTách xâu ngay t i v trí n m gi a Ak và Ak+1 v i m t trnguyên k, 1 k < n. Ngh a là, tr c tiên ta tính các chu i matr 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. 8Di 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 i1 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ínhA1..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 AiAi+l… Aj t i gi a Ak and Ak+l, v i i k < j. Thì m[i, j] b ngv 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. 9M t công th c quyNh v y, nh ngh a quy cho chi phí t i thi u c a m ts 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 nhngh a:s[i, j]: tr c a k t i ó chúng ta tách tích xâu ma tr nAiAi+1…Aj t n m t s m óng ngo c t i u. 10M t nh n xét quan tr ngM 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 nch a ng trong nó nh ng l i gi i t i u c a nh ng bài toáncon.B c th hai c a ph ng pháp qui ho ch ng là nh ngh atr 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. ...