CÁC BÀI TOÁN NP – KHÓ VÀ NP - ĐẦY ĐỦ

Tham khảo tài liệu các bài toán np – khó và np - đầy đủ, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
CÁC BÀI TOÁN NP – KHÓ VÀ NP - ĐẦY ĐỦ CHƯƠNG 19 CÁC BÀI TOÁN NP – KHÓ VÀ NP - ĐẦY ĐỦ Chúng ta đã biết nhiều bài toán, điển hình là bài toán người bánhàng, bài toán balô, bài toán chu trình Hamilton, … Các thu ật toán t ốt nh ấtđể giải quyết các bài toán này đều có thời gian ch ạy không ph ải là th ờigian đa thức, chẳng hạn thuật toán quy hoạch động cho bài toán ng ườibán hàng có thời gian chạy O(n22n), … Cho tới nay chưa có ai tìm ra đượcthuật toán thời gian đa thức cho bất kỳ bài toán nào trong lớp các bài toántrên. Vấn đề đặt ra là có tồn tại hay không thuật toán th ời gian ch ạy đathức cho các bài toán trên? Các vấn đề lý thuyết được trình bày trong ch ương này không kh ẳngđịnh rằng, không tồn tại thuật toán thời gian đa thức cho các bài toán trên.Điều mà các nhà nghiên cứu đã làm được là ch ỉ ra rằng, nhi ều bài toánchưa có thuật toán giải trong thời gian đa thức là có liên quan v ới nhau v ềmặt tính toán. Cụ thể là, chúng ta sẽ thiết lập hai lớp: l ớp các bài toán NP– khó (NP-hard) và lớp các bài toán NP- đầy đủ (NP – complete). M ột bàitoán là NP-đầy đủ có tính chất rằng, nó có thể giải được trong th ời gianđa thức nếu và chỉ nếu tất cả các bài toán NP-đầy đủ khác giải đượctrong thời gian đa thức. Nếu một bài toán NP- khó giải được trong th ờigian đa thức thì tất cả các bài toàn NP-đầy đủ giải được trong thời gian đathức. Người ta đã chỉ ra rằng, lớp NP-đầy đủ là lớp con của lớp NP – khó,nhưng có bài toán là NP – khó nhưng không phải là NP-đầy đủ. Các lớp bài toán NP–khó và NP - đầy đủ là rất giàu có. Tất cả cácbài toán nổi tiếng mà ta đã quen biết (bài toán người bán hàng, bài toánchiếc balô, và rất nhiều bài toán tổ hợp, các bài toán của lý thuyết đồ thị…) đều là NP – khó. 245 Các lớp NP – khó và NP - đầy đủ liên quan tới sự tính toán khôngđơn định (nondeterministic computations). Không thể thực hiện được s ựtính toán không ổn định trong thực tế, bởi vậy về mặt trực quan, chúng tacó thể phỏng đoán (chưa chứng minh được) rằng, các bài toán NP - đầyđủ hoặc NP – khó không giải được trong thời gian đa thức. Chúng ta sẽ cố gắng trình bày các vấn đề đã nêu trên một cách đ ơngiản, không hình thức, không đi sâu vào các chứng minh phức tạp. THUẬT TOÁN KHÔNG ĐƠN ĐỊNH19.1 Khái niệm thuật toán mà chúng ta sử dụng cho đến nay có tính ch ấtrằng, kết quả thực hiện mỗi phép toán là được xác định duy nhất. Thuậttoán với tính chất này được gọi là thuật toán đơn định (deterministicalgorithm). Định nghĩa 1. Lớp P bao gồm tất cả các bài toán giải được bởithuật toán đơn định trong thời gian đa thức (tức là tồn tại thuật toán giảiquyết nó với thời gian chạy đa thức). Để xác định lớp NP các bài toán, chúng ta cần phải đưa vào kháiniệm thuật toán không đơn định (nondeterministic algorithm). Sự mởrộng khái niệm thuật toán đơn định thành khái niệm thuật toán không đ ơnđịnh cũng hoàn toàn tương tự như khi ta mở rộng khái niêm otomat hữuhạn đơn định thành otomat hữu hạn không đơn định. Trong các thuật toánkhông đơn định chúng ta được phép đưa vào các phép toán mà kết quả củanó không phải là một giá trị được xác định duy nhất mà là một t ập h ữuhạn các giá trị. Các phép toán đó được biểu diễn bởi hàm lựa chọn: choice(S)Đây là hàm đa trị, giá trị của nó là các phần tử của tập hữu hạn S. Ngoàihàm choice, để mô tả các thuật toán không đơn định chúng ta đ ưa vào hailệnh: 246 success failureCác lệnh này là các lệnh dừng, hiệu quả của chúng sẽ được mô tả dướiđây. Các thuật toán không đơn định được thực hiện như thế nào? Đểthực hiện thuật toán không đơn định, chúng ta cần th ực hiện các tính toántheo dòng điều khiển được quy định bởi các câu lệnh nh ư khi ta th ực hiệnthuật toán đơn định, chỉ có một điều khác biệt so với thuật toán đơn đ ịnhlà, khi gặp hàm lựa chọn choice(S) thì sự tính toán đ ược phân thành nhi ềunhánh, mỗi nhánh tương ứng với một giá trị được chọn ra từ tập S, t ất c ảcác nhánh này sẽ làm việc đồng thời và độc lập với nhau. Mỗi nhánh tínhtoán đó khi gặp một hàm lựa chọn khác choice(S’) lại được phân thànhnhiều nhánh tính toán khác. Và như vậy, khi thực hiện thuật toán khôngđơn định, chúng ta cần phải thực hiện đồng thời và đ ộc l ập nhi ều đ ườngtính toán (được tạo thành từ các nhánh tương ứng với các lựa chọn). Dođó, ta có thể quan niệm rằng, thuật toán không đơn định mô tả s ự tínhtoán song song không hạn chế. Khi mà một đường tính toán gặp lệnhsuccess, thì có nghĩa là đường tính toán đó đã được tạo thành t ừ các lựachọn đúng đắn và đã thành công cho ra nghiệm của bài toán, khi đó t ất c ảcác đường tính toán đều dừng làm việc. Còn nếu một đường tính toán gặplệnh failure, thì có nghĩa là đường tính toán này đã thất bại, không cho ranghiệm của bài toán, và chỉ riêng đường này dừng làm việc. Máy có khảnăng thực hiện thuật toán không đơn định sẽ được gọi là máy không đơnđịnh (nondeterministic machine). Không tồn tại các máy không đơn địnhtrong thực tế. Sau đây chúng ta sẽ đưa ra một vài ví dụ về thuật toánkhông đơn định. Ví dụ 1. Xét bài toán tìm xem phần tử x có trong mảng A[0 … n -1], n ≥ 1, hay không ? Nếu có ta cần in ra ch ỉ số i mà A[i] = x, n ếu khôngthì in ra n. Thuật toán không đơn định là như sau: 247 Search (x, A, n) // Tìm x trong mảng A[0… n - 1]. { i = choice( 0: n – 1); if (A[i] = = x) { print(i); success; } else { print(n); failure ; } } Chú ý rằng, lệnh gán i = choice( 0 : n – 1) cho k ết qu ả là bi ến iđược gán một tr ...