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

Chương 7 trình bày về vấn đề NP-đầy đủ. Các nội dung chính trong chương này gồm có: Giải thuật thời gian đa thức tất định và không tất định, vấn đề NP-đầy đủ, định lý Cook, một số bài toán NP-đầy đủ, một số kỹ thuật để đối phó với những bài toán NP-đầy đủ. 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 7 - PGS.TS. Dương Tuấn Anh Chương 7 Vấn đề NP-đầy đủ 1. Giải thuật thời gian đa thức tất định và không tất định2. Vấn đề NP-đầy đủ3. Định lý Cook4. Một số bài toán NP-đầy đủ5. Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ 1Tồn tại hay không tồn tại giải thuật hữu hiệu• Đốivớinhiềubàitoánchúngtacónhữnggiảithuật hữuhiệuđểgiải.• Tuynhiên,córấtnhiềubàitoánkháckhôngcógiải thuậthữuhiệuđểgiải.• Vàđốivớimộtlớpkhálớncủanhữngbàitoánnhư vậy,chúngtakhôngthểnóicótồntạigiảithuật hữuhiệuđểgiảinóhaykhông. 2Những bài toán khó và những bài toán dễ• Nhiềunghiêncứuđãđượcthựchiệnvàcónhữngcơchế đểphânloạinhữngbàitoánmớilà“khóbằng”mộtsốbài toáncũđãbiết.• Tuynhiên,đôikhiranhgiớigiữanhữngbàitoán“khó”và nhữngbàitoán“dễ”làkhátếnhị..Thídụ: Dễ:Cótồntạimộtlốiđitừxđếnymàtrongsốnhỏhơn M? KHó:Cótồntạimộtlốiđitừxđếnymàtrọngsố M? Bàitoán1BFS–thờigiantuyếntính Bàitoán2–thờigianhàmmũ 31. Giải thuật thời gian đa thức tất định và không tất địnhP: Tậphợptấtcảnhữngbàitoáncóthểgiảiđượcbằng nhữnggiảithuậttấtđịnhtrongthờigianđathức.“Tất định” (Deterministic) : khigiảithuậtđanglàmgì, cũngchỉcómộtviệcduynhấtcóthểđượcthựchiệnkế tiếp.(whateverthealgorithmisdoing,thereisonlyone thingitcoulddonext).Thídụ: XếpthứtựbằngphươngphápchènthuộclớpP vìcóđộphứctạpđathứcO(N2) 4Tính không tất định Mộtcáchđểmởrộngquyềnnăngcủamáytínhlàchonó cónănglựclàmviệckhôngtấtđịnh(nondeterminism). Không tất định: khimộtgiảithuậtgặpmộtsựlựa chọngiữanhiềukhảnăng,nócóquyềnnăng“tiênđóan” đểbiếtchọnmộtkhảnăngthíchđáng.Giảithuậtkhôngtấtđịnh(nondeterministicalgorithm)Thídụ:ChoAlàmộtmảngsốnguyên.Mộtgiảithuật khôngtấtđịnhNSORT(A,n)sắpthứtựcácsốtheothứ tựtăngvàxuấtchúngratheothứtựnày. 5Thí dụ về một giải thuật không tất định// An array B is used as temporary array.procedure NSORT(A,n) // sort n positive integers //begin for i:= 1 to n do B[i]:= 0; // guessing stage for i:= 1 to n do begin Hàmchoice(1:n)cókhả j := choice(1:n); năngxácđịnhmộtvịtrí if B[j] 0 then failure đúngtrongtầmtrịtừ1đến else B[j]:= A[i] end n.// verification stage for i:= 1 to n-1 do if B[i] > B[i-1] then failure; print(B); successend; 6Thí dụ về một giải thuật không tất định (tt.) Sựphângiảimộtgiảithuậtkhôngtấtđịnhcóthểđược thựchiệnbằngmộtsựsongsonghóakhônghạnchế (unboundedparallelism).Mỗilầncóbướclựachọnphảithựchiện,giảithuật tạoranhiềubảnsaocủachínhnó(copiesofitself).Mỗi bảnsaođượcthựchiệnchokhảnănglựachọn.Như vậynhiềukhảnăngđượcthựchiệncùngmộtlúc. - Bảnsaođầutiênkếtthúcthànhcôngthìlàmkếtthúc tấtcảcácquátrìnhtínhtóankhác. - Nếumộtbảnsaokếtthúcthấtbạithìchỉbảnsao ấykếtthúcmàthôi. 7Giải thuật không tất định (tt.)Thậtra,mộtmáytínhkhôngtấtđịnhkhôngtạoranhững bảnsaocủagiảithuậtmộtkhiphảithựchiệnmộtlựa chọn.Mà,nócóquyềnnăngchọnmộtyếutố“đúng”từmộttập nhữngkhảnănglựachọnmỗiphảithựchiệnmộtlựa chọn. Mộtyếutố“đúng”đượcđịnhnghĩanhưlàmộtchuỗi ngắnnhấtcủanhữnglựachọn(shortestsequenceof choices)màdẫnđếnsựkếtthúcthànhcông. Trongtrườnghợpkhôngtồntạimộtchuỗinhữnglựa chọnmàdẫnđếnsựkếtthúcthànhcôngtagiảđịnh rằnggiảithuậtdừngvàinrathôngbáo“tínhtoánkhông thànhcông”. 8Giải thuật không tất định (tt.)Ghichú:  Cácthôngbáosuccessvàfailurelàtươngđươngvới phátbiểustoptrongmộtgiảithuậttấtđịnh.  ĐộphứctạptínhtoáncủaNSORTlàO(n). NP:tậphợptấtcảnhữngbàitoánmàcóthểđược giảibằnggiảithuậtkhôngtấtđịnhtrongthờigian đathức.Thídụ:Bàitoáncótồntạilốiđidàinhấttừđỉnhx đếnđỉnhylàthuộclớpNP. 9Bài toán thỏa mãn mạch logic (circuitsatisfiability problem)Chomộtcôngthứclogiccódạng(x1+x3+x5)*(x1+~x2+x4 ...