Bài giảng Phân tích thiết kế giải thuật: Chương 1 - ĐH Bách khoa

Dưới đây là bài giảng Phân tích thiết kế giải thuật: Chương 1 - Dynamic Programming. Bài giảng bao gồm những nội dung về nguyên tắc của Dynamic Programming; các yếu tố để áp dụng Dynamic Programming; một biến dạng của Dynamic Programming.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Chương 1 - ĐH Bách khoa DynamicProgramming10.2.2004 Ch.1:DynamicProgramming 1 Giớithiệu° Dynamicprogramming — giảibàitoánbằngcáchkếthợpcáclờigiảicủacácbàitoáncon. — (ởđây“programming”khôngcónghĩalàlậptrình).° Sosánhdynamicprogrammingvà“chiavàtrị”(divideandconquer) — Giảithuậtchiavàtrị ° chiabàitoánthànhcácbàitoánconđộclập, ° giảichúngbằngđệquy, ° kếthợpchúngđểcólờigiảichobàitoánbanđầu. — Giảithuậtdynamicprogramming ° cácbàitoánconkhôngđộclậpvớinhau:chúngcóchungcác bàitoánconnhỏhơn. ° giảimỗibàitoánconchỉmộtlần,vàghinhớlờigiảiđó trongmộtbảngđểtruycậpkhicầnđến.10.2.2004 Ch.1:DynamicProgramming 2 Bàitoántốiưu° Bàitoántốiưu — cóthểcónhiềulờigiải — mỗilờigiảicómộttrị° Tìmlờigiảicótrịtốiưu(cựctiểuhaycựcđại).10.2.2004 Ch.1:DynamicProgramming 3 Nguyêntắccủadynamicprogramming° Mộtgiảithuậtdynamicprogrammingđượcxâydựngquabốnbước: 1.Xácđịnhcấutrúccủamộtlờigiảitốiưu. 2.Địnhnghĩađệquychogiátrịcủamộtlờigiảitốiưu. 3.Tínhgiátrịcủamộtlờigiảitốiưutừdướilên(“bottomup”). 4.Xâydựnglờigiảitốiưutừcácthôngtinđãtính.10.2.2004 Ch.1:DynamicProgramming 4 Nhânmộtchuỗimatrận° Chomộtchuỗimatrận A1,A2,...,An .° XácđịnhtíchA1A2 Andựatrêngiảithuậtxácđịnhtíchcủahaima trận.° Biểudiễncáchtínhtíchcủamộtchuỗimatrậnbằngcách“đặtgiữa ngoặc”(parenthesize)cáccặpmatrậnsẽđượcnhânvớinhau.° Mộttíchcủamộtchuỗimatrậnlàfullyparenthesizednếunólà — mộtmatrậnhoặclà — tíchcủahaitíchcủachuỗimatrậnfullyparenthesizedkhác,và đượcđặtgiữangoặc. Vídụ:mộtvàitíchcủachuỗimatrậnđượcfullyparenthesized — A — (AB) — ((AB)C).10.2.2004 Ch.1:DynamicProgramming 5 Chuỗimatrậnfullyparenthesized° Vídụ:Chomộtchuỗimatrận A1,A2,A3,A4 .TíchA1A2A3A4cóthể đượcfullyparenthesizedtheođúng5cáchkhácnhau: (A1(A2(A3A4))) (A1((A2A3)A4)) ((A1A2)(A3A4)) ((A1(A2A3))A4) (((A1A2)A3)A4)10.2.2004 Ch.1:DynamicProgramming 6 Nhânhaimatrận° TíchcủahaimatrậnAvàBvới — Acóchiềulàp q — Bcóchiềulàq r làmộtmatrậnCcóchiềulàp r. MATRIXMULTIPLY(A,B) 1ifcolumns[A] rows[B] 2thenerror“cácchiềukhôngtươngthích” 3elsefori 1torows[A] 4doforj 1tocolumns[B] 5doC[i,j] 0 6fork 1tocolumns[A] 7doC[i,j] C[i,j]+A[i,k] B[k,j] 8returnC° ThờigianđểtínhCtỷlệvớisốphépnhânvôhướngthựcthitrong dòng7,tứclàp q r.10.2.2004 Ch.1:DynamicProgramming 7 Phítổnđểnhânmộtchuỗimatrận° Nhậnxét:Phítổnnhânmộtchuỗimatrậntùythuộcvàocáchđặt giữangoặc(parenthesization).° Vídụ:Chochuỗimatrận A1,A2,A3 trongđócácchiều(dimension) củacácmatrậnlà10 100,100 5,và5 50 Cóđúng2cáchđểđóngngoặchoàntoàntíchA1A2A3: — Cách1:((A1A2)A3) ° TínhA1A2cần10 100 5=5000phépnhânvôhướng ° KếđónhânA1A2vớiA3cần10 5 50=2500phépnhânvôhướng ° Tổngcộng:7500phépnhânvôhướng — Cách2:(A1(A2A3)) ° TínhA2A3cần100 5 50=25000phépnhânvôhướng ° KếđónhânA1vớiA2A3cần10 100 50=50000phépnhânvô hướng ° Tổngcộng:75000phépnhânvôhướng.10.2.2004 Ch.1:DynamicProgramming 8 Bàitoánnhânchuỗimatrận° Chochuỗimatrận A1,A2,...,An gồmnmatrận,trongđóchiềucủa Ailàpi 1 pi,vớii=1,2,…,n.° Bàitoán:XácđịnhmộtđóngngoặchoàntoànchotíchA1A2 Ansao chosốphépnhânvôhướnglàtốithiểu.° Giảibàitoántrênbằngcáchvétcạn?10.2 ...