tailieunhanh - Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy Đủ

"Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy Đủ" để nắm bắt được những nội dung về khái niệm cơ bản NP-Đầy Đủ, hình thức hóa khái niệm bài toán, bài toán trừu tượng, bài toán quyết định, bài toán tối ưu, mã hóa. | Ch. 12: NP-Completeness NP-Đầy Đủ Ch. 12: NP-Completeness Vài khái niệm cơ bản Bài toán các tham số các tính chất mà lời giải cần phải thỏa mãn Một thực thể (instance) của bài toán là bài toán mà các tham số có trị cụ thể. Ch. 12: NP-Completeness Hình thức hóa khái niệm bài toán Ví dụ: bài toán SHORTEST-PATH là “không hình thức”: bài toán tìm đường đi ngắn nhất giữa hai đỉnh cho trước trong một đồ thị vô hướng, không có trọng số G = (V, E). “hình thức”: Một thực thể của bài toán là một cặp ba gồm một đồ thị cụ thể và hai đỉnh cụ thể. Một lời giải là một dãy các đỉnh của đồ thị . Bài toán SHORTEST-PATH là quan hệ kết hợp mỗi thực thể gồm một đồ thị và hai đỉnh với một đường đi ngắn nhất (nếu có) trong đồ thị nối hai đỉnh: SHORTEST-PATH I S Ch. 12: NP-Completeness Bài toán trừu tượng Định nghĩa: một bài toán trừu tượng Q là một quan hệ nhị phân trên một tập I, được gọi là tập các thực thể (instances) của bài toán, và một tập S, được gọi là tập các lời giải của bài toán: Q I S Ch. 12: NP-Completeness Bài toán quyết định Một bài toán quyết định Q là một bài toán trừu tượng mà quan hệ nhị phân Q là một hàm từ I đến S = {0, 1}, 0 tương ứng với “no”, 1 tương ứng với “yes”. Ví dụ: bài toán quyết định PATH là Cho một đồ thị G = (V, E), hai đỉnh u, v V, và một số nguyên dương k. Đặt i = G, u, v, k , một thực thể của bài toán quyết định PATH, PATH(i) = 1 (yes) nếu tồn tại một đường đi giữa u và v có chiều dài k PATH(i) = 0 (no) trong các trường hợp khác. Ch. 12: NP-Completeness Bài toán tối ưu Một bài toán tối ưu là một bài toán trong đó ta cần xác định trị lớn nhất hay trị nhỏ nhất của một đại lượng. Đối tượng của lý thuyết NP-đầy đủ là các bài toán quyết định, nên ta phải ép (recast) các bài toán tối ưu thành các bài toán quyết định. Ví dụ: ta đã ép bài toán tối ưu đường đi ngắn nhất thành bài toán quyết định PATH bằng cách làm chận k thành một tham số của bài toán. . | Ch. 12: NP-Completeness NP-Đầy Đủ Ch. 12: NP-Completeness Vài khái niệm cơ bản Bài toán các tham số các tính chất mà lời giải cần phải thỏa mãn Một thực thể (instance) của bài toán là bài toán mà các tham số có trị cụ thể. Ch. 12: NP-Completeness Hình thức hóa khái niệm bài toán Ví dụ: bài toán SHORTEST-PATH là “không hình thức”: bài toán tìm đường đi ngắn nhất giữa hai đỉnh cho trước trong một đồ thị vô hướng, không có trọng số G = (V, E). “hình thức”: Một thực thể của bài toán là một cặp ba gồm một đồ thị cụ thể và hai đỉnh cụ thể. Một lời giải là một dãy các đỉnh của đồ thị . Bài toán SHORTEST-PATH là quan hệ kết hợp mỗi thực thể gồm một đồ thị và hai đỉnh với một đường đi ngắn nhất (nếu có) trong đồ thị nối hai đỉnh: SHORTEST-PATH I S Ch. 12: NP-Completeness Bài toán trừu tượng Định nghĩa: một bài toán trừu tượng Q là một quan hệ nhị phân trên một tập I, được gọi là tập các thực thể (instances) của bài toán, và .