intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng NP - Complete

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
38
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng NP - Complete trình bày một số bài toán tối ưu rời rạc; lớp P; lớp NP; NP-đầy đủ; bài toán CNF-SAT. Để nắm chi tiết nội dung nghiên cứu mời các bạn cùng tham khảo bài giảng.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng NP - Complete

  1. NP - Complete
  2. Một số bài toán tối ưu rời rạc Bài toán người du lịch: Cho n điểm trên mặt phẳng (thành phố), giữa hai thành phố bất kỳ được xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố nào đó, qua n thành phố và quay về nơi xuất phát. OP (Optimization Problem): Tìm hành trình * có tổng chi phí bé nhất. DP (Decision Problem): Có tồn tại một hành trình với chi phí D? 2013-11-25 2
  3. Một số bài toán tối ưu rời rạc Bài toán tô màu đồ thị: Cho đồ thị G ={V,E}. OP: Số màu ít nhất để tô đồ thị G? DP: Cho số nguyên K. Có tồn tại hay không cách tô màu đồ thị G với số màu không quá K? Một cách tô màu đồ thị là một phương án gán cho mỗi đỉnh một màu, sao cho hai đỉnh liền kề có hai màu khác nhau. 2013-11-25 3
  4. Một số bài toán tối ưu rời rạc Bài toán cái túi: Cho n đồ vật với kích thước là các số nguyên s1, s2, ..., sn và các túi với kích thức là số nguyên T. OP: Tìm số túi ít nhất để xếp các đồ vật. DP: Cho số nguyên K. Có tồn tại cách xếp các đồ vật vào không quá K túi với sức chứa T? 2013-11-25 4
  5. Một số bài toán tối ưu rời rạc Bài toán tập con: Cho số nguyên dương T và tập X gồm n số nguyên dương a1, a2, ..., an. OP: Xác định tập con của X sao cho tổng của chúng gần nhất và không quá T. DP: Có tồn tại tập con sao cho tổng kích thước đúng bằng T. 2013-11-25 5
  6. Một số bài toán tối ưu rời rạc Bài toán phân công công việc: Giả thiết có n công việc:  Mỗi thời điểm chỉ thực hiện một công việc,  Thời gian thực hiện t1, t2, ..., tn,  Thời hạn hoàn thành d1, d2, ..., dn (tính từ khi bắt đầu công việc đầu tiên),  Mức phạt đối với mỗi công việc bị chậm là p1, p2, ..., pn. Phân công công việc là một hoán vị  của tập J={1, 2,..., n}: J(1), J(2), ..., J(n). Tổng giá trị phạt của phân công : n P   if t (1 )  ...  t  ( j )  d  ( j ) then p  ( j ) else 0  j 1 OP: Tìm lịch sắp xếp công việc có giá trị hàm phạt thấp nhất P()  min. DP: Cho trước k, xác định lịch  có mức phạt không quá k: P()  k. 2013-11-25 6
  7. Lớp P Thuật toán có độ phức tạp O(f(n)) nếu với mọi bộ số liệu có độ dài n, số phép tính phải thực hiện không quá C*f(n), với C >0. Thuật toán có độ phức tạp O(p(n)), với p(n) là một đa thức, gọi là có độ phức tạp đa thức. Định nghĩa: P là lớp các bài toán được giải với thời gian đa thức. Chú ý:  Không phải mọi bài toán thuộc lớp P đã có thuật toán hiệu quả.  Nếu bài toán không thuộc lớp P thì đều phải trả giá rất đắt về thời gian hoặc thậm chí không giải được nó trong thực tế. 2013-11-25 7
  8. Lớp NP (Nondeterministic Polynomial) NP là lớp các bài toán quyết định mà việc kiểm tra lời giải đối với dữ liệu vào được thực hiện với thời gian đa thức. 2013-11-25 8
  9. Lớp NP (Nondeterministic Polynomial) Thuật toán bất định (nondeterministic algorithm): Pha bất định: Một xâu kí tự S bất kỳ được sinh ra trong bộ nhớ, có thể coi như lời giải đề nghị. Pha tiền định: Đọc dữ liệu vào (S có thể bị bỏ qua). Thuật toán có thể kết thúc với khẳng định “Yes”, “No”, hoặc rơi vào vòng lặp không dừng. Có thể coi là pha kiểm tra lời giải đề nghị S. NP là lớp bài toán giải được bằng thuật toán bất định với thời gian đa thức (nondeterministic polynomial bouded). Thuật toán bất định là đa thức nếu tồn tại đa thức p sao cho với mỗi dữ liệu vào có kích thước n và có trả lời “yes” với tính toán của thuật toán là đa thức. 2013-11-25 9
  10. Lớp NP 2 5 Ví dụ: 1 3 đồ thị có 5 đinh, 8 cạnh và k =4: V ={1, 2, 3, 4, 5}, E={(1,2), (1,4), (2,4), (2,3), (3,5), (2,5), (3,4), (4,5)} 4 Kí hiệu: R (Red), B (Blue), G (Green), O (Orange), Y (Yellow). S Output Reason RGRBG No Đỉnh 2 và 5 cùng màu RGRB No Đỉnh 5 không được tô màu RBYGO No Dùng tới 5 màu RGRBY Yes Dùng 4 màu, các cặp đỉnh kề khác màu 2013-11-25 10
  11. Lớp P vs. NP Hiển nhiên: P  NP NP \ P = ? (NP  P?) NP P Bài toán cái túi Sắp xếp Cây khung bé nhất Bài toán ba lô Nhân ma trận Bài toán người du lịch Tìm kiếm tuần tự Đường đi ngắn nhất ... 2013-11-25 11
  12. NP-đầy đủ (NP-complete) Hiển nhiên: P  NP. Nhưng: NP \ P = ? NP Chứng minh được: P Trong NP có những bài toán khó không kém bất cứ bài toán nào khác trong NP. Bài toán cái túi Sắp xếp Cây khung bé nhất Bài toán ba lô  A NP: nếu có một thuật toán đa thức Nhân ma trận Bài toán người nào giải được A thì với mọi bài toán B Tìm kiếm tuần tự du lịch Đường đi ngắn nhất NP đều có thuật toán đa thức để giải B. ... Bài toán A được gọi là NP-đầy đủ. Nói cách khác, A NP được gọi là NP- đầy đủ nếu A P thì suy ra P=NP. 2013-11-25 12
  13. NP-đầy đủ (NP-complete) Hiển nhiên: P  NP. Nhưng: NP \ P = ? Chứng minh được: P NP 1. Nếu NP ≠ P thì có bài Sắp xếp toán thuộc NP nhưng Cây khung bé nhất Nhân ma trận không thuộc P và cũng Tìm kiếm tuần tự NP- không phải NP-đầy đủ. Đường đi ngắn nhất đầy ... đủ 2. Nhiều bài toán là NP-đầy đủ. 2013-11-25 13
  14. NP-đầy đủ (NP-complete) P NP Sắp xếp Cây khung bé nhất NP- Nhân ma trận Tìm kiếm tuần tự đầy Đường đi ngắn đủ nhất ... Như vậy, để chỉ ra một bài toán nào đó là NP-đầy đủ cần chỉ ra rằng: Tồn tại một thuật toán đa thức bất định để giải nó (tức là chỉ ra nó thuộc lớp NP); Có một bài toán NP-đầy đủ dẫn về nó. 2013-11-25 14
  15. NP-đầy đủ (NP-complete) Giả thiết cần giải bài toán A và có thuật toán giải bài toán B. Giả sử có ánh xạ T chuyển mỗi dữ liệu vào x của bài toán A thành dữ liệu vào T(x) của bài toán B T: x T(x) sao cho: Lời giải y của bài toán A với dữ liệu vào x tương ứng với Lời giải z của bài toán B với dữ liệu vào T(x) (nếu y là ”yes” thì z cũng là ”yes”). Thuật toán giải bài toán A = {Ánh xạ T + Thuật toán giải B} 2013-11-25 15
  16. Bài toán CNF-SAT Mô tả: 1) Biến logic nhận một trong hai giá trị: true hoặc false. Kí hiệu a là biến logic, là phủ định của a. Nếu a nhận giá trị true thì nhận giá trị false và ngược lại, nếu a nhạn giá trị false thì nhận giá trị true. Một tên biến là một biến logic hoặc phủ định của biến logic (cũng là một biến logic). 2) Một mệnh đề là một dãy các tên biến được xen kẽ bới phép toán logic OR (). 3) Một biểu thức logic trong dạng liên kết chuẩn (conjunction nomal form - CNF) là một dãy các mệnh đề được kết nối bới phép toán AND (). Bài toán quyết định: Khi các biến nhận giá trị true hoặc false, biểu thức có nhận giá trị true hay không? 2013-11-25 16
  17. Bài toán CNF-SAT Định lý Cook: Bài toán CNF-SAT là NP-đầy đủ Cần chỉ ra rằng bất kỳ bài toán NP nào (A) cũng dẫn chuyển về CNF-SAT: Cần xây dựng ánh xạ T dẫn chuyển input x của bài toán A về một biểu thức logic. Lời giải của bài toán quyết định A trùng với giá trị true hoặc false của CNF-SAT. 2013-11-25 17
  18. Bài toán CNF-SAT Định lý Cook: Bài toán CNF-SAT là NP-đầy đủ CNF-SAT “yes” x T(x) dữ liệu T hoặc “no” vào của A Algorithm for A 2013-11-25 18
  19. Bài toán CNF-SAT Ví dụ: Xét bài toán 3-CG: a c Đồ thị G ={V,E} như hình vẽ có tô được bằng 3 màu? b d Chuyển dẫn bài toán 3-CG về bài toán CNF-SAT? 2013-11-25 19
  20. Bài toán CNF-SAT u1 u2 Ký hiệu: xkj – đỉnh k tô bởi màu j Xét 32 mệnh đề: C(k) = {xk1, xk2, xk3}, đỉnh k được tô bởi ít nhất 1 màu A(k) = {xk1, xk2,}, đỉnh k không cùng được tô màu 1 và 2 u3 u4 B(k) = {xk2, xk3}, đỉnh k không cùng được tô màu 2 và 3 C(k) = {xk1, xk3}, đỉnh k không cùng được tô màu 1 và 3 k = a, b, c, d M = C(a) & ..&C(d)&A(a)&..&A(d)&B(a)&..&B(d)&C(a)&..&C(d) M = true nếu mỗi đỉnh được tô bởi đúng 1 trong ba màu {1, 2, 3} 2013-11-25 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2