Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy Đủ

Mời các bạn cùng tham khảo "Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy Đủ" để nắm bắt được những nội dung về khái niệm cơ bản NP-Đầy Đủ, hình thức hóa khái niệm bài toán, bài toán trừu tượng, bài toán quyết định, bài toán tối ưu, mã hóa.
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 12: NP-Đầy Đủ NPĐầyĐủ13.11.2004 Ch.12:NPCompleteness 1 Vàikháiniệmcơbảnª Bàitoán – cácthamsố – cáctínhchấtmàlờigiảicầnphảithỏamãnª Mộtthựcthể(instance)củabàitoánlàbàitoánmàcácthamsốcótrị cụthể.13.11.2004 Ch.12:NPCompleteness 2 Hìnhthứchóakháiniệmbàitoánª Vídụ:bàitoánSHORTESTPATHlà – “khônghìnhthức”:bàitoántìmđườngđingắnnhấtgiữahai đỉnhchotrướctrongmộtđồthịvôhướng,khôngcótrọngsốG =(V,E). – “hìnhthức”: ° Mộtthựcthểcủabàitoánlàmộtcặpbagồmmộtđồthịcụ thểvàhaiđỉnhcụthể. ° Mộtlờigiảilàmộtdãycácđỉnhcủađồthị. ° BàitoánSHORTESTPATHlàquanhệkếthợpmỗithực thểgồmmộtđồthịvàhaiđỉnhvớimộtđườngđingắnnhất (nếucó)trongđồthịnốihaiđỉnh: SHORTESTPATH I S13.11.2004 Ch.12:NPCompleteness 3 Bàitoántrừutượngª Địnhnghĩa:mộtbàitoántrừutượngQlàmộtquanhệnhịphântrên mộttậpI,đượcgọilàtậpcácthựcthể(instances)củabàitoán,và mộttậpS,đượcgọilàtậpcáclờigiảicủabàitoán: Q I S13.11.2004 Ch.12:NPCompleteness 4 Bàitoánquyếtđịnhª MộtbàitoánquyếtđịnhQlàmộtbàitoántrừutượngmàquanhệ nhịphânQlàmộthàmtừIđếnS={0,1},0tươngứngvới“no”,1 tươngứngvới“yes”.ª Vídụ:bàitoánquyếtđịnhPATHlà ChomộtđồthịG=(V,E),haiđỉnhu,v V,vàmộtsốnguyên dươngk. Đặti= G,u,v,k ,mộtthựcthểcủabàitoánquyếtđịnhPATH, – PATH(i)=1(yes)nếutồntạimộtđườngđigiữauvàvcóchiều dài k – PATH(i)=0(no)trongcáctrườnghợpkhác.13.11.2004 Ch.12:NPCompleteness 5 Bàitoántốiưuª Mộtbàitoántốiưulàmộtbàitoántrongđótacầnxácđịnhtrịlớn nhấthaytrịnhỏnhấtcủamộtđạilượng.ª ĐốitượngcủalýthuyếtNPđầyđủlàcácbàitoánquyếtđịnh,nên taphảiép(recast)cácbàitoántốiưuthànhcácbàitoánquyếtđịnh. Vídụ:tađãépbàitoántốiưuđườngđingắnnhấtthànhbàitoán quyếtđịnhPATHbằngcáchlàmchậnkthànhmộtthamsốcủabài toán.13.11.2004 Ch.12:NPCompleteness 6 Mãhoá(encodings)ª Đểmộtchươngtrìnhmáytínhgiảimộtbàitoántrừutượngthìcác thựcthểcủabàitoáncầnđượcbiểudiễnsaochochươngtrìnhmáy tínhcóthểđọcvà“hiểu”chúngđược.ª Tamãhóa(encode)cácthựcthểcủamộtbàitoántrừutượngđể mộtchươngtrìnhmáytínhcóthểđọcchúngđược. – Vídụ:MãhoátậpN 0,1,2,3,4,...}thànhtậpcácchuỗi 0,1, 10,11,100,...}.Trongmãhoánày,e 17 =10001. – Mãhóamộtđốitượngđahợp(chuỗi,tập,đồthị,...)bằngcách kếthợpcácmãhóacủacácthànhphầncủanó.13.11.2004 Ch.12:NPCompleteness 7 Mãhoá(tiếp)ª Mộtbàitoáncụthểlàmộtbàitoánmàtậpcácthựcthểcủanólà tậpcácchuỗinhịphân.ª MộtgiảithuậtgiảimộtbàitoáncụthểtrongthờigianO T n )nếu, khiđưanómộtthựcthểicóđộdàin i ,thìnósẽchoralờigiải trongthờigianO T n ).ª Mộtbàitoáncụthểlàcóthểgiảiđượctrongthờigianđathứcnếu tồntạimộtgiảithuậtgiảinótrongthờigianO nk vớimộthằngsố knàođó.13.11.2004 Ch.12:NPCompleteness 8 LớpPª Địnhnghĩa:LớpP(complexityclassP)làtậpcácbàitoánquyếtđịnh cụthểcóthểgiảiđượctrongthờigianđathức.13.11.2004 Ch.12:NPCompleteness 9 Bàitoántrừutượngvàbàitoáncụthểª Tadùngmãhoáđểánhxạcácbàitoántrừutượngđếncácbàitoán cụthể. – ChomộtbàitoánquyếtđịnhtrừutượngQ,Qánhxạmộttập cácthựcthểIđến{0,1},tacóthểdùngmộtmãhóae:I {0, 1} đểsinhramộtbàitoánquyếtđịnhcụthểtươngứng,ký hiệue(Q). Mãhóaephảithõađiềukiện ° NếuQ(i) {0,1}làlờigiảichoi I,thìlờigiảichothực thểe(i) {0,1} củabàitoánquyếtđịnhcụthểe(Q)cũnglà Q(i). Q I {0,1} e(Q) {0,1}*13.11.2004 Ch.12:NPCompleteness 10 ...