Bài giảng Phân tích và thiết kế giải thuật: Chương 5 - PGS.TS. Dương Tuấn Anh

Bài giảng Phân tích và thiết kế giải thuật - Chương 5 trình bày một số kiến thức về qui hoạch động và giải thuật tham lam. Sau khi học xong chương này người học có thể biết được qui hoạch động là gì, các bước của qui hoạch động, các thành phần của quy hoạch động, biết được giải thuật tham lam là gì,... mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và thiết kế giải thuật: Chương 5 - PGS.TS. Dương Tuấn AnhChương 4Qui hoạch động và giải thuậttham lam Quihoạchđộng Giảithuậtthamlam 11. Qui hoạch độngQuyhoạchđộng(dynamicprogramming)giảicácbàitoánbằngcáchkếthợpcáclờigiảicủacácbàitoánconcủabàitoánđangxét.Phươngphápnàykhảdụngkhicácbàitoánconkhôngđộclậpđốivớinhau,tứclàkhicácbàitoánconcódùngchungnhữngbàitoán“cháu”(subsubproblem).Quihoạchđộnggiảicácbàitoán“cháu”dùngchungnàymộtlầnvàlưulờigiảicủachúngtrongmộtbảngvàsauđókhỏiphảitínhlạikhigặplạibàitoáncháuđó.Quihoạchđộngđượcápdụngchonhữngbàitoántốiưuhóa(optimizationproblem). 2Bốn bước của qui hoạch độngSựxâydựngmộtgiảithuậtquihoạchđộngcóthểđược chialàmbốnbước:1. Đặctrưnghóacấutrúccủalờigiảitốiưu.2.Địnhnghĩagiátrịcủalờigiảitốiưumộtcáchđệquy.3.Tínhtrịcủalờigiảitốiưutheokiểutừdướilên.4.Cấutạolờigiảitốiưutừnhữngthôngtinđãđượctính toán. 3Thí dụ1: Nhân xâu ma trậnChomộtchuỗigồmnmatrận,vàtamuốntínhtíchcácmatrận.A1A2…An (5.1)Tíchcủaxâumatrậnnàyđượcgọilàmởđóngngoặcđầyđủ(fullyparenthesized)nếunólàmộtmatrậnđơnhoặclàtíchcủahaixâumatrậnmởđóngngoặcđầyđủ.Thídụ:A1A2A3A4cóthểđượcmởđóngngoặcđầyđủtheo5cách: (A1(A2(A3A4))) (A1((A2A3)A4) ((A1A2)(A3A4)) (A1(A2A3))A4) (((A1A2)A3)A4) 4Cáchmàtamởđóngngoặcmộtxâumatrậncóảnhhưởngrấtlớnđếnchiphítínhtíchxâumatrận.Thídụ: A1 10 100A2 100 5A3 5 50((A1A2)A3))thựchiện10.100.5+10.5.50=5000+2500=7500phépnhânvôhướng.(A1(A2A3))thựchiện100.5.50+10.100.50=25000+50000=75000phépnhânvôhướng.Haichiphítrênrấtkhácbiệtnhau. 5Phát biểu bài toán nhân xâu ma trậnBàitoántínhtíchxâumatrận:‘Chomộtchuỗigồmnmatrận,vớimỗii=1,2,…,n,matrậnAicókíchthướcpi1 pi,tamở đóngngoặctíchnàysaochotốithiểuhóatổngsốphép nhânvôhướng”.Đâylàmộtbàitoántốiưuhóathuộcloạikhó. 6Cấu trúc của một cách mở đóng ngoặc tối ưuBước1:Đặctrưnghóacấutrúccủamộtlờigiảitốiưu.DùngAi..jđểkýhiệumatrậnkếtquảcủaviệctínhAiAi+1…Aj.MộtsựmởđóngngoặctốiưucủatíchxâumatrậnA1.A2…AnTáchxâungaytạivịtrínằmgiữaAkvàAk+1vớimộttrịnguyênk,1 kDiễn tả lời giải một cách đệ quyỞđây,nhữngbàitoánconcủatalàbàitoánxácđịnhchiphítốiưuứngvớisựmởđóngngoặcchochuỗiAi.Ai+1…Ajvới1 i j n.Đặtm[i,j]làtổngsốtốithiểucácphépnhânvôhướngđượcđòihỏiđểtínhmatrậnAi..j.ChiphícủacáchrẻnhấtđểtínhA1..nsẽđượcghiởm[1,n].GiảsửrằngsựmởđóngngoặctốiưutáchđôitíchchuỗiAiAi+l…AjtạigiữaAkandAk+l,vớii kMột công thức đệ quyNhưvậy,địnhnghĩađệquychochiphítốithiểucủamộtsựmởđóngngoặcchoAiAi+l…Ajlànhưsau:m[i,j]=0 nếui=j, =min{m[i,k]+m[k+1,j]+pi1pkpj.} nếuiMột nhận xét quan trọngMộtnhậnxétquantrọnglàSựmởđóngngoặccủaxâuconA1A2....AkbêntrongsựmởđóngngoặctốiưucủaxâuA1A2…Ancũngphảilàmộtsựmởđóngngoặctốiưu.Nhưvậy,mộtlờigiảitốiưuchobàitóantíchxâumatrậnchứađựngtrongnónhữnglờigiảitốiưucủanhữngbàitoáncon.Bướcthứhaicủaphươngphápquihoạchđộnglàđịnhnghĩatrịcủalờigiảitốiưumộtcáchđệquytheonhữnglờigiảitốiưucủanhữngbàitoáncon. 10 Tính những chi phí tối ưuThayvìtínhlờigiảidựavàocôngthứcchoở(5.2)bằngmộtgiảithuậtđệquy,chúngtađithựchiệnBước3củaquihoạchđộng:tínhchiphítốiưubằngcáchtiếpcậntừdướilên.GiảsửmatrậnAicókíchthướcpi1 pivớii=1,2,..,n.Đầuvàolàchuỗitrịsố.Thủtụcdùngmộtbảngm[1..n,1..n]đểlưucácchiphím[i,j]vàbảngs[1..n,1..n]đểlưugiátrịnàocủavịtríkmàthựchiệnđượcchiphítốiưukhitínhm[i,j].ThủtụcMATRIXCHAINORDERtrảvềhaimảngmvàs. 11Thủ tục tính hai bảng m và sprocedureMATRIXCHAINORDER(p,m,s);beginn:=length[p]1;fori:=1tondom[i,i]:=0;forl:=2tondo/*l ...