Bài giảng NP - Complete

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.
Nội dung trích xuất từ tài liệu:
Bài giảng NP - CompleteNP - CompleteMộ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 2Mộ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 3Mộ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 4Mộ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 Một số bài toán tối ưu rời rạcBà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 6Lớ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 7Lớ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 8Lớ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 9Lớ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 O ...