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

định

2. Vấn đề NP-đầy đủ

3. Định lý Cook

4. 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

1

NP-đầy đủ

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.

ấ

ả

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

ố ớ ộ ớ

ớ ủ

ư • Và đ i v i m t l p khá l n c a nh ng bài toán nh

ậ

i gi

i thu t

ậ v y, chúng ta không th  nói  ể ả ệ ữ h u hi u đ  gi

ể i nó hay không

ữ ồ ạ ả có t n t .

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

ứ ữ ớ ể ộ ố khó b ngằ ” m t s  bài

ệ ạ đ  phân lo i nh ng bài toán m i là “ 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 ..

ồ ạ ộ ố ừ ố ỏ ơ ế i m t l i đi t x đ n y mà trong s  nh  h n

ữ Thí dụ: ễ  D : Có t n t M?

 KHó: Có t n t

ồ ạ ộ ố ọ ế i đi t i m t l x đ n y mà tr ng s ố (cid:0) M?

ờ ế

3

ừ Bài toán 1 ­ BFS – th i gian tuy n tính ờ Bài toán 2 – th i gian hàm mũ

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

t c  nh ng bài toán có th  gi ể ả ượ ằ i đ c b ng

ậ ấ ị P: T p h p t ậ ợ ấ ả ữ ả ữ 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 th c hi n k

ế

cũng ch  có m t vi c duy nh t có th  đ ti p. (whatever the algorithm is doing, there is only one  thing it could do next).

ứ ự ằ ộ ớ ế b ng ph

4

Thí dụ: X p th  t ộ ứ ạ ứ ươ vì có đ  ph c t p đa th c O( ng pháp chèn thu c l p P  N2 )

Tính không tất định

ộ

ự ấ ị

non­determinism). ộ ự ự 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 Không tất định: khi m t gi ộ ả ủ t đ nh ( 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”  ể ế t ch n m t kh  năng thích đáng. đ  bi ậ ả i thu t không t

ố ả ộ ấ ị t đ nh  Gi ộ Thí dụ: Cho A là m t m ng s  nguyên. M t gi

ấ ị ắ (nondeterministic algorithm) ộ ả ậ i thu t  ứ ố  các s  theo th t đ nh NSORT(A, n) s p th  t

5

ứ ự ấ không t ự t tăng và xu t chúng ra theo th  t ứ ự  này.

ế  1 đ n

Hàm choice(1:n) có kh  ả ộ ị ị năng xác đ nh m t v  trí  ị ừ ầ đúng trong t m tr  t n.

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; // guessing stage for i:= 1 to n do begin j := choice(1:n); if B[j] <> 0 then failure else B[j]:= A[i] end // verification stage 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.)

ậ ấ ị i thu t không t c

ệ S  phân gi ự t đ nh có th  đ ộ ự song song hóa không h n chạ ể ượ ế

ệ ậ i thu t

ả ướ ự c l a ch n ph i th c hi n, gi ả

ả ự ự

ự ư c th c hi n cho kh  năng l a ch n. Nh   ả ệ ả copies of itself). M i ỗ ọ ộ c th c hi n cùng m t lúc.

ự ả ộ ả i m t gi ằ th c hi n b ng m t s   (unbounded parallelism).  ự ọ ỗ ầ    M i l n có b ủ ề b n sao c a chính nó ( ạ t o ra nhi u  ệ ượ ả b n sao đ ượ ề ậ v y nhi u kh  năng đ ế ế ầ - B n sao đ u tiên k t thúc thành công thì làm k t thúc

t c  các quá trình tính tóan khác. t

ộ ả ỉ ả ế ấ ạ - N u m t b n sao k t thúc th t b i thì ch  b n sao

7

ả ấ ả ế ấ ế y k t thúc mà thôi.

ấ ị

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  ả i thu t m t khi ph i th c hi n m t l a

ậ ả b n sao c a gi ch n. ọ

ề

ệ ọ ọ ả ự Mà, nó có quy n năng ch n m t y u t ả ừ ộ ậ ộ ế ố  “đúng” t  m t t p  ộ ự ự ỗ ph i th c hi n m t l a

ượ ị c đ nh nghĩa nh  là  ự ỗ ộ ư m t chu i  ọ  (shortest sequence of

ữ nh ng kh  năng l a ch n m i  ch n.ọ M t y u t ộ ế ố  “đúng” đ ữ ắ ng n nh t c a nh ng l a ch n ế ự ế choices) mà d n đ n s  k t thúc thành công.

ườ ồ ạ ộ ỗ ấ ủ ẫ ợ

ng h p không t n t ế ự ế ẫ ự i m t chu i nh ng l a   đ nh

ậ ừ ả i thu t d ng và in ra thông báo

8

Trong tr ữ ả ị ọ ch n mà d n đ n s  k t thúc thành công ta gi ằ “tính toán không  r ng gi thành công”.

Giải thuật không tất định (tt.)

Ghi chú:

 Các thông báo success và failure là t

ớ ng v i

phát bi u ể stop trong m t gi ươ ươ ng đ ậ ấ ị t đ nh. i thu t t

 Đ  ph c t p tính toán c a NSORT là O(n).

ộ ứ ạ ộ ả ủ

ậ ợ ấ ả ữ

ể ượ t c  nh ng bài toán mà có th  đ ờ ấ ị

ậ

c  t đ nh trong th i gian

i thu t không t

i b ng gi

NP: t p h p t ả ả ằ gi đa th c. ứ

ấ ừ ỉ

i l

i đi dài nh t t

đ nh

x

ế

ỉ

Thí dụ : Bài toán có t n t ồ ạ ố ộ ớ y là thu c l p NP.

đ n đ nh

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 ễ ễ ả ớ ả  OR, “*” di n t 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.

10

ủ ớ ộ ậ ớ Ghi chú: L p P là m t t p con c a l p NP .

2. Vấn đề NP-đầy đủ

ộ ữ ế ộ ề t là thu c v

ể

ễ ả Có m t danh sách nh ng bài toán mà đã bi ộ ề ớ i chúng d  dàng trên m t máy không

ư ể ậ

ệ i thu t  ể ả ấ ỳ i b t k

ớ ư l p NP nh ng không rõ có th  thu c v  l p P hay  ứ ộ không. (T c là, ta gi ộ ả ấ ư ấ ị t đ nh nh ng ch a ai có th  tìm th y m t gi t ườ ạ ữ ng đ  gi h u hi u ch y trên máy tính thông th ủ ộ m t bài toán nào c a chúng ).

ữ ấ ữ ộ

ữ ộ ạ    Nh ng bài toán NP này l       “N u ế b t kấ ỳ m t trong nh ng bài toán này có th  gi

ượ ờ c trong th i gian đa th c thì t

ẽ ượ ờ ả i có thêm m t tính ch t n a là: ể ả i  ữ t cấ ả nh ng bài toán  ứ i trong th i gian đa th c ứ c gi

11

ấ ị đ ộ ớ thu c l p NP cũng s  đ ộ t đ nh.” trên m t máy t

ư ậ ượ ọ ữ Nh ng bài toán nh  v y đ c g i là nh ng bài toán

ữ NP­đ y đ  ( ầ ủ NP­complete)

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

ầ ủ ủ ữ ớ ớ ấ

• Công c  chính đ  ch ng minh m t bài toán thu c lo i

ộ

ộ ả ứ ả ể ứ ưở ạ ề tính kh  thu gi m đa th c ng v

• B t c  gi

ớ trong l p NP. ụ ầ ủ NP­đ y đ  là ý t (polynomial reducibility).  i thu t nào gi ớ c bài toán m i thu c lo i

ể ượ ộ ạ ầ ủ i m t bài toán NP­đ y đ

ằ ấ ứ ả NP có th  đ nào đó đã bi

ả ượ ậ i đ ể ả ộ c dùng đ  gi tế  b ng cách sau: ể ộ ể ệ ấ ỳ ủ

ộ ể ệ ủ

ả i này tr  v  thành m t l ớ i gi ộ ờ ả ủ i gi ộ ờ ả ồ ế i c a bài toán

13

ế ế ầ ủ        bi n th  m t th  hi n b t k  c a bài toán NP­đ y đ   ả ế đã bi i bài toán  t thành m t th  hi n c a bài toán m i, gi ể ằ này b ng gi i thu t đã có đ  tìm ra m t l i, r i bi n  ể ờ ả i gi th  l ầ ủ NP­đ y đ  đã bi ậ ở ề t.

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  ầ ầ ủ ộ ộ

ỏ ằ ả ộ ứ ả ứ ề ớ ấ r ng m t bài toán NP­đ y đ  đã  t nào đó thì kh  thu gi m đa th c v  bài toán m i  y. ể ứ ỉ ầ ủ đ , ta ch  c n ch ng t ế bi

ị Đ nh nghĩa : (Thu gi m vả

(cid:0) ả ề). Ta b o bài toán ệ

ế ể ượ c L2 thì cũng có th  đ L1 thu gi m vả ề  ấ ỳ  L2 n u b t k   c dùng

14

(reduces to) bài toán L2, ký hi u là  L1  ả ả ượ gi i đ ể ả đ  gi ậ i thu t nào gi i L1.

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 ,  ấ ả ọ  trình đi qua t tìm m t l 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

ộ ồ ị

15

ộ ơ ấ ả ọ ỉ m t chu trình đ n mà đi qua t t c  m i đ nh.

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

ấ ỳ ả

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 ầ ủ ậ i thu t nào  ể ượ c dùng đ  gi c  i bài toán TSP cũng có th  đ ự ả i bài toán HCP, thông qua s  thu gi m sau: ạ ộ ồ ị ng  ng nh  sau:

ủ ằ thành phố c a bài toán TSP b ng cách dùng

ồ ị trong đ  th ;

TSP cũng là NP­đ y đ  hay không. B t k  gi ể ả ể ượ có th  đ ể ả dùng đ  gi ộ ộ       (cid:0)  t o ra các  ạ t p ậ đ nhỉ ề ả ặ

ữ ồ ạ ộ ạ ố ươ ứ ỉ

(cid:0) ế ồ ị ồ ạ ể ộ ộ i TSP đ  tìm m t l R i thì dùng gi trình N

16

ế ậ i thu t gi ồ ị ố ỉ (cid:0)  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  ị 2 n u không có c nh.  đ  th  và giá tr   ả ả (N là s  đ nh trong đ  th ).

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

ờ ế ữ ể ẽ ấ ươ ứ ạ ố ng đ i khác

ự chúng ta liên k t nh ng bài toán mà t nhau.

ụ ể ạ ả ả Thí d : Có th  thu gi m bài toán tho  mãn m ch logic

17

ề (CSP) v  bài toán HCP.

3. Định lý Cook

ư

ự ộ c m t ch ng minh tr c

ầ ế Nh ng: Bài toán nào là bài toán NP­đ y đ  đ u tiên? ề ấ ượ    S.A. Cook (1971) đã đ  xu t đ ỏ ầ ủ ầ ứ ạ ằ

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 thu t th i gian đa th c đ  gi ấ ả ọ i bài  ớ ỏ t c  m i bài toán trong l p

ể ượ ả i m t gi ạ toán th a mãn m ch logic thì t ờ c gi NP có th  đ 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

18

ổ vào máy Turing (Turing machine) t ng quát.

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 đ .  ạ ả

ắ ầ ằ ườ ươ i th

Danh sách này b t đ u b ng bài toán tho  mãn m ch  ng gia du hành (TSP) và bài  logic, bài toán ng 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  ồ ạ ộ ờ ả i m t l i gi ố i toàn s

19

ạ ạ ho ch tuy n tính, li u có t n t nguyên?

ệ ế ị ộ ử

ề

ấ ề ộ ậ ả ượ ể ắ ế

ộ ử ấ ả ữ ỏ t c  nh ng công tác đó sao cho th a mãn

ự ể ự ỳ ạ

­ 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 k  h n không? ủ ỉ

ể ế ộ ậ

ộ ồ ị : Cho m t đ  th   ỏ c m t t p nh   ồ ị ộ ố ỉ ọ ạ ơ ế

ứ ằ ứ

ơ ị ứ ứ ủ

ấ ầ ụ ố ị

20

ồ ­ Bài toán ph  đ nh (VERTEX COVER) ượ và m t s  nguyên N, có th  ki m đ ạ h n N đ nh mà ch m h t m i c nh trong đ  th  ?  (BIN PACKING): cho n món đ  ồ ế ­ Bài toán x p thùng ả ặ mà ph i đ t vào trong các thùng có s c ch a b ng  nhau L. Món đ  ồ i đòi h i ỏ li đ n v  s c ch a c a thùng.  ể ứ ấ t  M c đích là xác đ nh s  thùng ít nh t c n đ  ch a t c  ả n món đ  đó.

P (cid:0)

NP ?

Nh ng bài toán nêu trên và nhi u bài toán liên quan có

ữ ữ ứ ự ế ụ ọ nh ng  ng d ng th c t ề  quan tr ng.

ữ ấ ả S  ki n không có nh ng gi ậ ố ượ t đ c tìm th y

ấ ỳ ộ ằ ứ ạ ự ệ cho b t k  bài toán nào trong s  nh ng bài toán nêu trên  là m t b ng ch ng m nh m  r ng i thu t t ố ữ ẽ ằ P (cid:0) NP.

Dù cho P có khác NP hay không, m t s  ki n th c t

ữ

21

ộ ự ệ ả ậ ả ộ ữ ự ế  là  ể ả ả i  chúng ta không có nh ng gi i thu t đ m b o có th  gi ệ ầ ủ ấ ỳ ộ b t k  m t bài toán NP­đ y đ  nào m t cách h u hi u.

Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ

ậ ấ ỉ “(approximation algorithm)

ể 1. Dùng “gi ả i gi đ  tìm l i thu t x p x ờ ả ấ ỉ ố ư i x p x  t i  u (near­optimal).

ườ ng h p trung bình đ  phát

2. D a vào hi u năng c a tr ệ ộ ả ậ ợ ờ ả i gi ể ộ ố m t s

ủ i thu t mà tìm ra l ặ ệ ượ c trong

ợ ự ể tri n m t gi ườ ng h p tr ọ ườ m i tr i trong  ợ  nào đó, m c dù không làm vi c đ ng h p.

ả

3. S  d ng nh ng gi ữ ử ụ ư ữ ệ nh ng h u hi u, ví d  nh  gi ộ ứ ạ ậ i thu t có đ  ph c t p hàm mũ  ậ ụ ư ả i thu t quay lui.

ả ậ ể ệ 4. Đ a ư heuristic vào gi ả i thu t đ  tăng thêm hi u qu

ả ậ ủ c a gi i thu t.

22

5. S  d ng ử ụ metaheuristic.

Heuristic và meta heuristic

ẫ ờ ả ủ ắ

 Heuristic là tri th c v  bài toán c  th  đ ụ ể ượ ử ụ ứ ề ả i c a gi ậ ở ể c s  d ng đ   ờ ự i thu t. Nh  s   ệ i gi ả ậ ữ i thu t tr  nên h u hi u

d n d t quá trình tìm ra l thêm vào các heuristic mà gi h n.ơ

ụ ổ ể ạ  Meta heuristic là lo i heuristic t ng quát có th  áp d ng

ề ớ cho nhi u l p bài tóan.

ự ứ

ẽ ớ ự ề ạ

 G n đây meta heuristic là m t lãnh v c nghiên c u phát  ộ ầ ờ ủ ể tri n m nh m , v i s  ra đ i c a nhi u meta heuristic  nh :ư

ả ả ệ ề ỏ ậ ậ i thu t di truy n (genetic algorithm) i thu t mô ph ng luy n kim (simulated

­ gi ­ gi annealing)

23

ế

­ tìm ki m tabu (Tabu search)    v.v….

Đóng góp của vấn đề NP-đầy đủ

ự ầ ủ Có nhi u bài toán NP­đ y đ  trong các lãnh v c

ố ứ ự ế i tích s  (numerical analysis),   và tìm ki m,

ự (string processing),

ồ ị ử ề ả  gi ắ  s p th  t ử  x  lý dòng ký t ọ  Mô hình hóa hình h c (geometry modeling)   x  lý đ  th  (graph processing).

ấ ủ ọ ầ S  đóng góp quan tr ng nh t c a lý thuy t v  NP­đ y

ấ ị nó cung c p m t c  ch  đ  xác đ nh m t bài toán

24

ộ ơ ế ể ễ ự ế ề ự đ  là: ủ ộ ớ m i trong các lãnh v c trên là “d ” hay “khó”.

Bốn lớp bài toán phân theo độ khó

ữ ả

 Nh ng bài toán b t kh  quy t (Undecidable problems): i.

ế ư ề ậ ể ả ữ i thu t đ  gi

ế ị ươ ấ ả Đây là nh ng bài toán ch a h  có gi ộ     Thí dụ: Bài toán quy t đ nh xem m t ch ng trình có

ừ ộ d ng trên m t máy Turing.

ữ ữ

ậ ậ ả ồ ạ ả i gi ỉ ồ ạ ả i gi i (intractable)  : đây là nh ng bài  ờ ứ ể i thu t th i  gian đa th c đ   ể ờ i thu t th i gian hàm mũ đ

ộ ớ ặ ệ ủ

 Nh ng bài toán khó gi toán mà không t n t ả i chúng. Ch  t n t gi ả i chúng. gi ữ ữ

ầ ủ  Nh ng bài toán NP­đ y đ ầ ủ     Nh ng bài toán NP­đ y đ  là m t l p con đ c bi t c a

25

ữ ớ l p bài toán NP.  Nh ng bài toán P .