Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9: Qui hoạch động - Đào Nam Anh

Data Structure and Algorithm 1 DATA STRUCTURE AND ALGORITHM Dynamic Programming CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Qui hoạch động Dr. Dao Nam Anh Data Structure and Algorithm 2 Resource - Reference Slides adapted from James B D Joshi, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 3 Divide and Conquer Chia và Trị • Một số chương trình đệ qui gọi chính nó cho hai tập dữ liệu có kích thước ½ Chia vấn đề này thành 2 phần và thực hiện từng phần • Chi phí thời gian: TN = Tk + TN-k + 1 • Many recursive programs use recursive calls on two subsets of inputs (two halves usually)  Divide the problem and solve them – divide and conquer paradigm  Complexity: TN = Tk + TN-k + 1 Data Structure and Algorithm 4 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 Data Structure and Algorithm 5 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 2 3 1 7 1 2 Data Structure and Algorithm 6 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 Data Structure and Algorithm 7 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 4 2 Data Structure and Algorithm 8 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 4 52 Data Structure and Algorithm 9 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 4 5 6 32 Data Structure and Algorithm 10 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 4 5 6 32 7 3 Data Structure and Algorithm 11 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 1 2 3 4 5 6 32 7 3 8 Data Structure and Algorithm 12 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 71 1 2 3 4 5 6 7 8 9 32 3 Data Structure and Algorithm 13 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 71 1 2 3 4 5 6 7 8 9 32 3 10 1 Data Structure and Algorithm 14 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 71 1 2 3 4 5 6 7 8 9 32 3 10 1 11 12 7 Data Structure and Algorithm 15 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 71 1 2 3 4 5 6 7 8 9 10 11 12 13 7132 73 Data Structure and Algorithm 16 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị Item max(Item a[], int l, int r) { Item u, v; int m = (l+r)/2; if (l == r) return a[l]; u = max(a, l, m); v = max(a, m+1, r); if (u > v) return u; else return v; } 2 3 1 7 32 2 3 1 7 71 1 2 3 4 5 6 7 8 9 10 11 12 13 1 7132 73 7 Data Structure and Algorithm 17 Dynamic programming Qui hoạch động • Các thuật toán đệ quy có ưu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình đệ quy, các chương trình này thường kéo theo những đòi hỏi lớn về không gian bộ nhớ và một khối lượng tính toán khổng lồ. • Quy hoạch động (Dynamic programming) là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại. Data Structure and Algorithm 18 Dynamic programming Qui hoạch động • Bản chất của quy hoạch động là thay thế mô hình tính toán “từ trên xuống” (Top-down) bằng mô hình tính toán “từ dưới lên” (Bottom-up). • Từ “programming” ở đây không liên quan gì tới việc lập trình cho máy tính, đó là một thuật ngữ mà các nhà toán học hay dùng để chỉ ra các bước chung trong việc giải quyết một dạng bài toán hay một lớp các vấn đề. • Không có một thuật toán tổng quát để giải tất cả các bài toán quy hoạch động. Data Structure and Algorithm 19 Dynamic programming Qui hoạch động • Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa. • Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Data Structure and Algorithm 20 Dynamic programming Knapsack problem - Bài toán Cái túi • Trong siêu thị có n gói hàng, các gói hàng có trọng lượng khác nhau W[i], có giá trị khác nhau V[i]. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M. • Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất. • Knapsack problem  Given » N types of items of varying size and value » One knapsack (belongs to a thief!)  Find: the combination of items that maximize the total value Data Structure and Algorithm 21 Dynamic programming Knapsack problem - Bài toán Cái túi Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, , i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M]. Data Structure and Algorithm 22 Dynamic programming Knapsack problem - Bài toán Cái túi Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, , i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng: a. Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, , i - 1} với giới hạn trọng lượng là j. Tức là F[i, j] = F[i - 1, j] Data Structure and Algorithm 23 Dynamic programming Knapsack problem - Bài toán Cái túi b. Nếu có chọn gói thứ i (chỉ xét tới trường hợp này khi mà W[i] ≤ j) thì F[i, j] bằng giá trị gói thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, , i - 1} với giới hạn trọng lượng j - W[i]. Tức là về mặt giá trị thu được: F[i, j] = V[i] + F[i - 1, j - W[i]] Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2 giá trị thu được ở trên. Data Structure and Algorithm 24 Dynamic programming Knapsack problem - Bài toán Cái túi Knapsack size: 17 0 1 2 3 4 Item A B C D E Size 3 4 7 8 9 Val 4 5 10 11 13 int knap(int cap) { int i, space, max, t; for (i = 0, max = 0; i < N; i++) if ((space = cap - items[i].size) >= 0) if ((t = knap(space) + items[i].val) > max) max = t; return max; } int knap(int M) { int i, space, max, maxi, t; if (maxKnown[M] != unknown) return maxKnown[M]; for (i = 0, max = 0; i < N; i++) if ((space = M-items[i].size) >= 0) if ((t = knap(space) + items[i].val) > max) { max = t; maxi = i; } maxKnown[M] = max; itemKnown[M] = items[maxi]; return max; } Data Structure and Algorithm 25 Discussion – Câu hỏi • https://sites.google.com/site/daonamanhedu/data- structure-algorithm