Chương 6: Những bài toán NP - đầy đủ

Chia sẻ: Ba Xoáy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

106
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giải thuật thời gian đa thức tất định và không tất định...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 6: Những bài toán NP - đầy đủ

Ch ng 6 Nh ng bài tóan NP- y 1. Gi i thu t th i gian a th c t t nh và không t t nh 2. V n NP- y 3. nh lý Cook 4. M t s bài toán NP- y 1
T 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. 2
Nh 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 3
1. Gi i thu t th i gian a th c t t nh và không t t nh P: 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 ) 4
Tí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. 5
Thí 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; Hàm choice(1:n) có kh for i:= 1 to n do n ng xác nh m t v trí begin úng trong t m tr t 1 n j := choice(1:n); n. if B[j] 0 then failure else B[j]:= A[i] end for i:= 1 to n-1 do if B[i] > B[i-1] then failure; print(B); success end; 6
Thí 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. 7
Gi 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”. 8
Gi 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. nh x n Thí d : Bài toán có t n t i l i i dài nh t t nh y là thu c l p NP. 9
Bài toán th a mãn m ch logic (circuit satisfiability 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à ~ di n t NOT. Bài toán CSP là xác nh xem có t n t i m t phép gán các tr logic vào các bi n logic sao cho toàn công th c tr thành true. CSP c ng là m t bài toán NP. Ghi chú: L p P là m t t p con c a l p NP. 10
2. V n NP- y Có m t danh sách nh ng bài toán mà ã bi t là thu c v l p NP nh ng không rõ có th thu c v l p P hay không. (T c là, ta gi i chúng d dàng trên m t máy không t t nh nh ng ch a ai có th tìm th y m t gi i thu t h u hi u ch y trên máy tính thông th ng gi i b t k m t bài toán nào c a chúng). Nh ng bài toán NP này l i có thêm m t tính ch t n a là: “N u b t k m t trong nh ng bài toán này có th gi i c trong th i gian a th c thì t t c nh ng bài toán thu c l p NP c ng s c gi i trong th i gian a th c trên m t máy t t nh.” 11
Nh ng bài toán nh v y c g i là nh ng bài toán (NP-complete) NP- y Hình 6.1 NP-complete NP P 12
Tính kh thu gi m a th c (Polynomial reducibility) L p NP- y là l p con c a nh ng bài toán khó nh t • trong l p NP. Công c chính ch ng minh m t bài toán thu c lo i NP- • là ý t ng v tính kh thu gi m a th c (polynomial y reducibility). B t c gi i thu t nào gi i c bài toán m i thu c lo i NP • có th c dùng gi i m t bài toán NP- y nào ó ã bi t b ng cách sau: bi n th m t th hi n b t k c a bài toán NP- y ã bi t thành m t th hi n c a bài toán m i, gi i bài toán này b ng gi i thu t ã có tìm ra m t l i gi i, r i bi n th l i gi i này tr v thành m t l i gi i c a bài toán NP- y ã bi t. 13
Tính kh thu gi m a th c (tt.) ch ng minh m t bài toán thu c lo i NP là NP- y , ta ch c n ch ng t r ng m t bài toán NP- y ã bi t nào ó thì kh thu gi m a th c v bài toán m i y. nh ngh a: (Thu gi m v ). Ta b o bài toán L1 thu gi m v (reduces to) bài toán L2, ký hi u là L1 L2 n u b t k gi i thu t nào gi i c L2 thì c ng có th c dùng gi i L1. 14
Tính kh thu gi m a th c (tt.) ch ng minh m t bài toán m i L là NP- y , chúng ta c n ch ng minh: 1. Bài toán L thu c l p NP 2. M t bài toán NP- y ã bi t thu gi m v L. Thí d : Cho hai bài toán  Bài toán ng i th ng gia du hành (TSP): cho m t t p các thành ph và kho ng cách gi a m i c p thành ph , tìm m t l trình i qua t t c m i thành ph sao cho t ng kho ng cách c a l trình nh h n M.  Bài toán chu trình Hamilton (HCP): Cho m t th , tìm m t chu trình n mà i qua t t c m i nh. 15
Tính kh thu gi m a th c (tt.) Gi s ta bi t HCP là NP- y và mu n xác nh xem TSP c ng là NP- y hay không. B t k gi i thu t nào có th c dùng gi i bài toán TSP c ng có th c dùng gi i bài toán HCP, thông qua s thu gi m sau: Cho m t th hi n c a bài toán HCP (m t th ), hãy t o ra m t th hi n c a bài toán TSP t ng ng nh sau: t o ra các thành ph c a bài toán TSP b ng cách dùng t p nh trong th ; v kho ng cách gi a hai c p thành ph ta gán giá tr 1 n u có t n t i m t c nh gi a hai nh t ng ng trong th và giá tr 2 n u không có c nh. R i thì dùng gi i thu t gi i TSP tìm m t l trình N (N là s nh trong th ). 16
Tính kh thu gi m a th c (tt.) Ngh a là HCP thu gi m v TSP, nh v y tính ch t NP- y c a HCP hàm ý tính ch t tính ch t NP- y c a TSP. S thu gi m HCP v TSP là n gi n vì hai bài toán có nh ng nét t ng t nhau. S thu gi m th i gian a th c có th s r t ph c t p khi chúng ta liên k t nh ng bài toán mà t ng i khác nhau. Thí d : Có th thu gi m bài toán tho mãn m ch logic (CSP) v bài toán HCP. 17
3. nh lý Cook Nh ng: Bài toán nào là bài toán NP- y u tiên? S.A. Cook (1971) ã xu t c m t ch ng minh tr c ti p u tiên r ng bài toán th a mãn m ch logic (CSP) là bài toán NP- y . “N u t n t i m t gi i thu t th i gian a th c gi i bài toán th a mãn m ch logic thì t t c m i bài toán trong l p NP có th c gi i trong th i gian a th c.” Ch ng minh c a Cook r t ph c t p nh ng ch y u d a vào máy Turing (Turing machine) t ng quát. 18
4. M t s bài toán NP- y Hàng nghìn bài toán khác nhau c bi t là NP- y . Danh sách này b t u b ng bài toán tho mãn m ch logic, bài toán ng i th ng gia du hành (TSP) và bài toán chu trình Hamilton. M t vài bài toán khác nh sau: - Bài toán phân ho ch s : Cho m t t p nh ng s nguyên, có th phân ho ch chúng thành hai t p con mà có t ng tr s b ng nhau? - Bài toán qui ho ch nguyên: Cho m t bài toán qui ho ch tuy n tính, li u có t n t i m t l i gi i toàn s nguyên? 19
- X p l ch công vi c trên a b x lý ( multiprocessor scheduling): Cho m t k h n (deadline) và m t t p các công tác có chi u dài th i gian khác nhau ph i c th c thi trên hai b x lý. V n là có th s p x p th c thi t t c nh ng công tác ó sao cho th a mãn k h n không? - Bài toán ph nh (VERTEX COVER): Cho m t th và m t s nguyên N, có th ki m c m t t p nh h n N nh mà ch m h t m i c nh trong th ? - Bài toán x p thùng (BIN PACKING): cho n món mà ph i t vào trong các thùng có s c ch a b ng nhau L. i òi h i li n v s c ch a c a thùng. M c ích Món là xác nh s thùng ít nh t c n ch a t t c n món ó. 20