Bài tiểu luận: Mô phỏng bài toán bằng thuật toán Minmax

Với mục đích giúp các bạn nắm vững các khái niệm của phương pháp chia để trị, các bước giải một bài toán dùng phương pháp chia để trị, nắm vững thuật toán bài toán Minmax,... Mời các bạn cùng tham khảo nội dung bài tiểu luận "Mô phỏng bài toán bằng thuật toán Minmax". Hy vọng đây là tài liệu phục vụ nhu cầu học tập và nghiên cứu cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài tiểu luận: Mô phỏng bài toán bằng thuật toán Minmax TRƯỜNGĐẠIHỌCTRẦNĐẠINGHĨA KHOACÔNGNGHỆTHÔNGTIN MÔPHỎNGBÀITOÁNBẰNGTHUẬTTOÁNMINMIAX Giáoviênhướngdẫn: Tiếnsĩ–PhùngThếBảo Ngườithựchiện: ĐinhHữuLuận ĐỗHoàngCương ĐoànAnhKhoa NguyễnMaiChíTrungTP.HồChíMinh2015 MỞĐẦU Trongmọithờiđại,việctìmralờigiảitốiưuchomộtbàitoánnàođólàmộtvấnđềrấtkhóđểthựchiện.Đãcórấtnhiềunghiêncứuđểtìmracácphươngpháphữuhiệugiảiquyếtcácbàitoántốiưunày.Cólẽthuậttoánđượcsửdụngnhiềunhất,quantrọngnhấtlàkỹthuật“chiađểtrị”.KỷthuậtnàysẽchiabàitoánthànhNbàitoánnhỏhơn,thựchiệnlờigiảichotừngbàitoánnhỏnàyvàtừđóxâydựngthuậttoánchobàitoántổnghợp. Mộttrongnhữngbàitoántrongthựctếtathườnggặplà:SắpxếptrộnhoặctìmgiátrịMinMax……vànhữngbàitoántrêncóthểtìmralờigiảidễdàngbằngcáchsửdụngphươngphápchiađểtrị Hiểurõvàcàiđặtđượccácthuậttoán,cũngnhưtìmralờigiảitốiưuchomộtbàitoánnàođódựatrênnhữngtàiliệuđãhọclàmộtyêucầukhôngthểthiếuđốivớisinhviênnghànhTinhọc.Tuynhiên,tronggiớihạncủađềtài,chúngemkhôngthểtrìnhbàytấtcảcácthuậttoáncóliênquanđếnđồthịmàởđâyhúngemchỉtrìnhbày“bàitoánMinMax”.Đâycũnglànộidungchínhcủađềtàichúngemđãchọn. MỤCLỤC • Phần1:Mụctiêuvàhướnggiảiquyết • Phần2:Cởsởlýthuyết • Bàitoán • Ýtưởng • Giảithuật • Minhhọa • Đánhgiáđộphứctạp • Phần3:Môphỏngchươngtrình • Giớithiệuvềchươngtrình • Môtảbằnglời • Môtảbằngsơđồkhối • Kếtquả • Phần4:Tàiliệuthamkhảo PHẦN1 MỤCTIÊUVÀHƯỚNG GIẢIQUYẾT1.Mụctiêu: • Nắmvữngcáckháiniệmcủaphươngphápchia đểtrị,cácbướcgiảimộtbàitoándùngphương phápchiađểtrị • Nắmvữngthuậttoán“bàitoánMinMax”. 2.Yêucầucầnđạt: • Thiếtkếđánhgiáđượcbàitoán:ýtưởng,giải thuật,minhhọavàđánhgiáđộphứctạpcủa giảithuật. ̉ • Môphong:môph ỏngbằnglờivàbằngsơ đồ khối“bàitoánMinMax” 3.Hướnggiảiquyết: • Vềlýthuyết:tìmhiểucáckháiniệmphương phápchiađểtrị,giảithuậtđượcyêucầutrong đềtài. • Vềchươngtrình:SửdụngngônngữVisual Basic.Net(VisualBasic2008)đểviếtchương trình. PHẦN2 CƠSỞLÝTHUYẾT • GiớithiệuphươngphápchiađểtrịChiađểtrịlàmộttrongnhữngphươngphápthiếtkếgiảithuậtcơbảnbaogồmcácthaotác:Chia:chiabàitoáncầngiảithànhmộtloạtcácbàitoánconđộclậpTrị:đòihỏiviệcgiảiquyếtcácbàitoánconthuđượcTổnghợp:thựchiệnviệcxâydựnglờigiảicủabàitoánđặtratừ cáclờigiảicủabàitoáncon.SƠĐỒCHUNGSơđồchungcủathuậttoánchiađểtrị(DivideandConquer)gồm3thànhphần • Chia(Divide):chiabàitoáncầngiảiSrathànhcácbàitoán conS1,S2,S3…….. • Trị(conquer):giảicácbàitoánconmộtcáchđẹquy • Tổnghợp(Combie):tổnghợplờigiảicácbàitoánS1,S2, S3…..thànhlờigiảicủabàitoánS Đểphântíchđộphứctạpcủathuậttoáncóthểsửdụngcông thứcđệquy Vấnđềđặtralàcầngiảicácbàitoánconđộclậpbằngcách nào?đólàvấnđềtrungtâmcủabàitoán. • BàitoánMinMax • Phátbiểubàitoán TìmgiátrịMin,Maxtrongđoạna[1…r]củamảnga[1…n]. • Ýtưởng Tạimỗibước,chiađôiđoạncầntìmrồitìmMin,Maxcủatừng đoạn,sauđótổnghợpkếtquảlại Nếuđoạnchiachỉcó1phầntửthìMin=Maxvàbằngphầntửđó. Minhhọa:I 1 2 3 4 5 6 7 8A[i] 10 1 5 0 9 3 15 19 TìmgiátrịMin,Maxtrongđoạna[2….7]củamảnga[1…..7] Kýhiệu: MinMax(a,1,r,Min,Max)choMinvàMaxtrongđoạna[1….r] MinMax(a,2,7,Min,Max)choMin=0vàMax=15trongđoạn a[2..7] ...