Bài Giảng điện tử Phân tích và thiết kế giải thuật: Giải Những bài toán NP đầy đủ - Chương 6

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 6: Những bài toán NP đầy đủ. Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải. Tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải.
Nội dung trích xuất từ tài liệu:
Bài Giảng điện tử Phân tích và thiết kế giải thuật: Giải Những bài toán NP đầy đủ - Chương 6 Ch ng 6 Nh ng bài tóan NP- y1. Gi i thu t th i gian a th c t t nh và không t t nh2. V n NP- y3. nh lý Cook4. M t s 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• i v i nhi u bài toán chúng ta có nh ng gi i thu t h u hi u gi i.• Tuy nhiên, có r t nhi u bài toán khác không có gi i thu t h u hi u gi i.• Và i v i m t l p khá l n c a nh ng bài toán nh v y, chúng ta không th nói có t n t i gi i thu t h u hi u gi i nó hay không. 2Nh ng bài toán khó và nh ng bài toán d• Nhi u nghiên c u ã c th c hi n và có nh ng c ch phân lo i nh ng bài toán m i là “khó b ng” m t s bài toán c ã bi t.• Tuy nhiên, ôi khi ranh gi i gi a nh ng bài toán “khó” và nh ng bài toán “d ” là khá t nh ..Thí d : D : Có t n t i m t l i i t x n y mà trong s nh h n M? KHó: Có t n t i m t l i i t x n y mà tr ng s M? Bài toán 1 - BFS – th i gian tuy n tính Bài toán 2 – th i gian hàm m 31. Gi i thu t th i gian a th c t t nh và khôngt t nhP: T p h p t t c nh ng bài toán có th gi i c b ng nh ng gi i thu t t t nh trong th i gian a th c.“T t nh” (Deterministic) : khi gi i thu t ang làm gì, c ng ch có m t vi c duy nh t có th c th c hi n k ti p. (whatever the algorithm is doing, there is only one thing it could do next).Thí d : X p th t b ng ph ng pháp chèn thu c l p P vì có ph c t p a th c O(N2 ) 4Tính không t t nh M t cách m r ng quy n n ng c a máy tính là cho nó có n ng l c làm vi c không t t nh (non-determinism). Không t t nh: khi m t gi i thu t g p m t s l a ch n gi a nhi u kh n ng, nó có quy n n ng “tiên óan” bi t ch n m t kh n ng thích áng.Gi i thu t không t t nh (nondeterministic algorithm)Thí d : Cho A là m t m ng s nguyên. M t gi i thu t không t t nh NSORT(A, n) s p th t các s theo th t t ng và xu t chúng ra theo th 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; for i:= 1 to n do Hàm choice(1:n) có kh begin n ng xác nh m t v trí j := choice(1:n); úng trong t m tr t 1 n if B[j] 0 then failure n. else B[j]:= A[i] end 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ân gi i m t gi i thu t không t t nh có th c th c hi n b ng m t s song song hóa không h n ch (unbounded parallelism). M i l n có b c l a ch n ph i th c hi n, gi i thu t t o ra nhi u b n sao c a chính nó (copies of itself). M i b n sao c th c hi n cho kh n ng l a ch n. Nh v y nhi u kh n ng c th c hi n cùng m t lúc. - B n sao u tiên k t thúc thành công thì làm k t thúc t t c các quá trình tính tóan khác. - N u m t b n sao k t thúc th t b i thì ch b n sao y k t thúc mà thôi. 7Gi i thu t không t t nh (tt.)Th t ra, m t máy tính không t t nh không t o ra nh ng b n sao c a gi i thu t m t khi ph i th c hi n m t l a ch n.Mà, nó có quy n n ng ch n m t y u t “ úng” t m t t p nh ng kh n ng l a ch n m i ph i th c hi n m t l a ch n.M t y u t “ úng” c nh ngh a nh là m t chu i ng n nh t c a nh ng l a ch n (shortest sequence of choices) mà d n n s k t thúc thành công.Trong tr ng h p không t n t i m t chu i nh ng l a ch n mà d n n s k t thúc thành công ta gi nh r ng gi i thu t d ng và in ra thông báo “tính toán không thành công”. 8Gi i thu t không t t nh (tt.)Ghi chú:  Các thông báo success và failure là t ng ng v i phát bi u stop trong m t gi i thu t t t nh.  ph c t p tính toán c a NSORT là O(n). NP: t p h p t t c nh ng bài toán mà có th c gi i b ng gi i thu t không t t nh trong th i gian a th c.Thí d : Bài toán có t n t i l i i dài nh t t nh x n nh y là thu c l p NP. 9Bài toán th a mãn m ch logic (circuitsatisfiability problem)Cho m t công th c logic có d ng (x1 + x3 + x5)*(x1+ ~x2 + x4)*(~x3 + x4 +x5)* (x2 + ~x3 + x5) v i các bi n xi là các bi n logic (true or false), “+” di n t OR, “*” di n t AND, và ~ d ...