Bài giảng Toán rời rạc - Bài 20: Quy hoạch động - Trần Vĩnh Đức

Quy hoạch động Trần Vĩnh Đức HUST Ngày 7 tháng 9 năm 2019 1 / 61 Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006. 2 / 61 Nội dung Đường đi ngắn nhất trên DAG Dãy con tăng dài nhất Khoảng cách soạn thảo Bài toán cái túi Nhân nhiều ma trận Đường đi ngắn nhất Tập độc lập trên cây Đồ thị phi chu trình (DAG): Nhắc lại Trong đồ thị phi chu trình, ta có thể sắp xếp thứ tự các đỉnh sao cho nó chỉ có cung đi đi từ trái sang phải. Chapter 6 Dynamic programming In the preceding chapters we have seen some elegant design principles—such as divide-and- conquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency. 6.1 Shortest paths in dags, revisited At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is especially easy in directed acyclic graphs (dags). Let’s recapitulate this case, because it lies at the heart of dynamic programming. The special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why this helps with shortest paths, suppose we want to figure out distances from node S to the other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its Figure 6.1 A dag and its linearization (topological ordering). B DC A S E 1 2 4 1 6 3 1 2 S C A B D E4 6 3 1 2 1 1 2 169Hình: Đồ thị phi chu trình G và biểu diễn dạng tuyến tính của nó. 4 / 61 Đường đi ngắn nhất trên DAG Chapter 6 Dynamic programming In the preceding chapters we have seen some elegant design principles—such as divide-and- conquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency. 6.1 Shortest paths in dags, revisited At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is especially easy in directed acyclic graphs (dags). Let’s recapitulate this case, because it lies at the heart of dynamic programming. The special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why this helps with shortest paths, suppose we want to figure out distances from node S to the other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its Figure 6.1 A dag and its linearization (topological ordering). B DC A S E 1 2 4 1 6 3 1 2 S C A B D E4 6 3 1 2 1 1 2 169Hình: Đồ thị phi chu trình G và biểu diễn dạng tuyến tính của nó. ▶ Xét nút D của đồ thị, cách duy nhất để đi từ S đến D là phải qua B hoặc C. ▶ Vậy, để tìm đường đi ngắn nhất từ S tới D ta chỉ phải so sánh hai đường: dist(D) = min{dist(B) + 1,dist(C) + 3} 5 / 61 Thuật toán tìm đường đi ngắn nhất cho DAG Chapter 6 Dynamic programming In the preceding chapters we have seen some elegant design principles—such as divide-and- conquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency. 6.1 Shortest paths in dags, revisited At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is especially easy in directed acyclic graphs (dags). Let’s recapitulate this case, because it lies at the heart of dynamic programming. The special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why this helps with shortest paths, suppose we want to figure out distances from node S to the other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its Figure 6.1 A dag and its linearization (topological ordering). B DC A S E 1 2 4 1 6 3 1 2 S C A B D E4 6 3 1 2 1 1 2 169Thuật toán Khởi tạo mọi giá trị dist(.) bằng ∞ dist(s) = 0 for each v ∈ V \ {s}, theo thứ tự tuyến tính: dist(v) = min(u,v)∈E{dist(u) + `(u, v)} 6 / 61 Chapter 6 Dynamic programming In the preceding chapters we have seen some elegant design principles—such as divide-and- conquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency. 6.1 Shortest paths in dags, revisited At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is especially easy in directed acyclic graphs (dags). Let’s recapitulate this case, because it lies at the heart of dynamic programming. The special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why this helps with shortest paths, suppose we want to figure out distances from node S to the other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its Figure 6.1 A dag and its linearization (topological ordering). B DC A S E 1 2 4 1 6 3 1 2 S C A B D E4 6 3 1 2 1 1 2 169Bài tập Làm thế nào để tìm đường đi dài nhất trong DAG? 7 / 61 Ý tưởng quy hoạch động Chapter 6 Dynamic programming In the preceding chapters we have seen some elegant design principles—such as divide-and- conquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. Predictably, this generality often comes with a cost in efficiency. 6.1 Shortest paths in dags, revisited At the conclusion of our study of shortest paths (Chapter 4), we observed that the problem is especially easy in directed acyclic graphs (dags). Let’s recapitulate this case, because it lies at the heart of dynamic programming. The special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right (Figure 6.1). To see why this helps with shortest paths, suppose we want to figure out distances from node S to the other nodes. For concreteness, let’s focus on node D. The only way to get to it is through its Figure 6.1 A dag and its linearization (topological ordering). B DC A S E 1 2 4 1 6 3 1 2 S C A B D E4 6 3 1 2 1 1 2 169 Hình: Để giải bài toán D ta cần giải bài toán con C và B. ▶ Quy hoạch động là kỹ thuật giải bài toán bằng cách xác định một tập các bài toán con và giải từng bài toán con một, nhỏ nhất trước, ▶ dùng câu trả lời của bài toán nhỏ để hình dung ra đáp án của bài toán lớn hơn, ▶ cho tới khi toàn bộ các bài toán được giải. 8 / 61 Nội dung Đường đi ngắn nhất trên DAG Dãy con tăng dài nhất Khoảng cách soạn thảo Bài toán cái túi Nhân nhiều ma trận Đường đi ngắn nhất Tập độc lập trên cây Bài toán dãy con tăng dài nhất Cho dãy số a1, a2, . . . , an. Một dãy con là một tập con các số lấy theo thứ tự, nó có dạng ai1 , ai2 , . . . , aik ở đó 1 ≤ i1 < i2 < · · · < ik ≤ n, và dãy tăng là dãy mà các phần tử tăng dần. Nhiệm vụ của bạn là tìm dãy tăng có số phần tử nhiều nhất. Ví dụ Dãy con dài nhất của dãy 5, 2, 8, 6, 3, 6, 9, 7 là: 10 / 61 Bài tập Hãy tìm dãy con tăng dài nhất của dãy 5, 3, 8, 6, 2, 6, 9, 7. 11 / 61 DAG của dãy tăngS. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 171 Figure 6.2 The dag of increasing subsequences. 5 2 8 3 9 766 In this example, the arrows denote transitions between consecutive elements of the opti- mal solution. More generally, to better understand the solution space, let’s create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence, that is, whenever i < j and ai < aj (Figure 6.2). Notice that (1) this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and (2) there is a one-to-one correspondence between increasing subsequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag! Here is the algorithm: for j = 1, 2, . . . , n: L(j) = 1 +max{L(i) : (i, j) ∈ E} return maxj L(j) L(j) is the length of the longest path—the longest increasing subsequence—ending at j (plus 1, since strictly speaking we need to count nodes on the path, not edges). By reasoning in the same way as we did for shortest paths, we see that any path to node j must pass through one of its predecessors, and therefore L(j) is 1 plus the maximum L(·) value of these predecessors. If there are no edges into j, we take the maximum over the empty set, zero. And the final answer is the largest L(j), since any ending position is allowed. This is dynamic programming. In order to solve our original problem, we have defined a collection of subproblems {L(j) : 1 ≤ j ≤ n} with the following key property that allows them to be solved in a single pass: (*) There is an ordering on the subproblems, and a relation that shows how to solve a subproblem given the answers to “smaller” subproblems, that is, subproblems that appear earlier in the ordering. In our case, each subproblem is solved using the relation L(j) = 1 +max{L(i) : (i, j) ∈ E}, Hình: DAG G = (V,E) của dãy 5, 2, 8, 6, 3, 6, 9, 7. Ta xây dựng DAG G = (V,E) cho dãy a1, a2, . . . , an như sau: ▶ V = {a1, a2, . . . , an}, và ▶ có cung (ai, aj) ∈ E nếu i < j và ai < aj. Bài toán tìm dãy tăng dài nhất được đưa về bài toán tìm đường đi dài nhất trên DAG. 12 / 61 Tìm đường đi dài nhất trên DAG for j = 1, 2, . . . ,n: L(j) = 1 +max{L(i) : (i, j) ∈ E} return maxj L(j) ▶ L(j) là độ dài của đường đi dài nhất kết thúc tại j. 13 / 61 Bài tập Hãy tìm đường đi dài nhất trên DAG sau: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 171 Figure 6.2 The dag of increasing subseque ces. 5 2 8 3 9 766 In this example, the arrows denote transitions between consecutive elements of the opti- mal solution. More generally, to better understand the solution space, let’s create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence, that is, whenever i < j and ai < aj (Figure 6.2). Notice that (1) this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and (2) there is a one-to-one correspondence between increasing subsequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag! Here is the algorithm: for j = 1, 2, . . . , n: L(j) = 1 +max{L(i) : (i, j) ∈ E} return maxj L(j) L(j) is the length of the longest path—the longest increasing subsequence—ending at j (plus 1, since strictly speaking we need to count nodes on the path, not edges). By reasoning in the same way as we did for shortest paths, we see that any path to node j must pass through one of its predecessors, and therefore L(j) is 1 plus the maximum L(·) value of these predecessors. If there are no edges into j, we take the maximum over the empty set, zero. And the final answer is the largest L(j), since any ending position is allowed. This is dynamic programming. In order to solve our original problem, we have defined a collection of subproblems {L(j) : 1 ≤ j ≤ n} with the following key property that allows them to be solved in a single pass: (*) There is an ordering on the subproblems, and a relation that shows how to solve a subproblem given the answers to “smaller” subproblems, that is, subproblems that appear earlier in the ordering. In our case, each subproblem is solved using the relation L(j) = 1 +max{L(i) : (i, j) ∈ E}, 14 / 61 Tìm đường đi dài nhất S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 171 Figure 6.2 The dag of increasing subsequences. 5 2 8 3 9 766 In this example, the arrows denote transitions between consecutive elements of the opti- mal solution. More generally, to better understand the solution space, let’s create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for ai and aj to be consecutive elements in an increasing subsequence, that is, whenever i < j and ai < aj (Figure 6.2). Notice that (1) this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and (2) there is a one-to-one correspondence between increasing subsequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag! Here is the algorithm: for j = 1, 2, . . . , n: L(j) = 1 +max{L(i) : (i, j) ∈ E} return maxj L(j) L(j) is the length of the longest path—the longest increasing subsequence—ending at j (plus 1, since strictly speaking we need to count nodes on the path, not edges). By reasoning in the same way as we did for shortest paths, we see that any path to node j must pass through one of its predecessors, and therefore L(j) is 1 plus the maximum L(·) value of these predecessors. If there are no edges into j, we take the maximum over the empty set, zero. And the final answer is the largest L(j), since any ending position is allowed. This is dynamic programming. In order to solve our original problem, we have defined a collection of subproblems {L(j) : 1 ≤ j ≤ n} with the following key property that allows them to be solved in a single pass: (*) There is an ordering on the subproblems, and a relation that shows how to solve a subproblem given the answers to “smaller” subproblems, that is, subproblems that appear earlier in the ordering. In our case, each subproblem is solved using the relation L(j) = 1 +max{L(i) : (i, j) ∈ E}, ▶ Làm thế nào tìm được đường đi dài nhất từ các L-giá trị? ▶ Ta quản lý các cạnh trên đường đi bởi con trỏ ngược prev(j) giống như tro g tìm đường đi ngắn nhất. ▶ Dãy tối ưu có thể tìm được theo con trỏ ngược này. 15 / 61 Ta có nên dùng đệ quy? Có nên dùng đệ quy để tính công thức sau? L(j) = 1 +max{L(i) : (i, j) ∈ E} 16 / 61 Nội dung Đường đi ngắn nhất trên DAG Dãy con tăng dài nhất Khoảng cách soạn thảo Bài toán cái túi Nhân nhiều ma trận Đường đi ngắn nhất Tập độc lập trên cây Khoảng cách soạn thảo ▶ Khi chương trình kiểm tra chính tả bắt gặp lỗi chính tả, nó sẽ tìm trong từ điển một từ gần với từ này nhất. ▶ Ký hiệu thích hợp cho khái niệm gần trong trường hợp này là gì? Ví dụ Khoảng cách giữa hai xâu SNOWY và SUNNY là gì? S - N O W Y S U N N - Y Chi phí: 3 - S N O W - Y S U N - - N Y Chi phí: 5 18 / 61 Khoảng cách soạn thảo Định nghĩa Khoảng cách soạn thảo của hai xâu x và y là số tối thiểu phép toán soạn thảo (xóa, chèn, và thay thế) để biến đổi xâu x thành xâu y. Ví dụ Biến đổi xâu SNOWY thành xâu SUNNY. S - N O W Y S U N N - Y ▶ chèn U, ▶ thay thế O → N, và ▶ xóa W. 19 / 61 Lời giải quy hoạch động Câu hỏi Bài toán con là gì? ▶ Để tìm khoảng cách soạn thảo giữa hai xâu x[1 . . .m] và y[1 . . .n], ▶ ta xem xét khoảng cách soạn thảo giữa hai khúc đầu x[1 . . . i] và y[1 . . . j]. ▶ Ta gọi đây là bài toán con E(i, j). ▶ Ta cần tính E(m,n). 20 / 61 Ví dụ Hình: Bài toán con E(7, 5) Để giải bài toán E(8, 6), ta xem xét các khả năng gióng hàng của hai ký tự ở vị trí x[8] và y[6]: x[8] − hoặc − y[6] hoặc x[8] y[6] Cụ thể T − hoặc − O hoặc T O 21 / 61 Bài toán con ▶ Làm thế nào để tính E(i, j) từ các bài toán con? ▶ Làm thế nào để gióng hàng x[1 . . . i] và y[1 . . . j]? ▶ Việc gióng hàng ở cột phải nhất có thể chia làm ba trường hợp: x[i] − hoặc − y[j] hoặc x[i] y[j] Ta có công thức E(i, j) = min  E(i− 1, j) + 1, E(i, j− 1) + 1, E(i− 1, j− 1) + diff(i, j) ở đó diff(i, j) = 0 nếu x[i] = y[j] và 1 nếu ngược lại. 22 / 61 Đưa về bài toán nhỏ hơn E(i, j) = min  E(i− 1, j) + 1, E(i, j− 1) + 1, E(i− 1, j− 1) + diff(i, j) ở đó diff(i, j) = 0 nếu x[i] = y[j] và 1 nếu ngược lại. 23 / 61 Thuật toán quy hoạch động for i = 0, 1, . . . ,m : E(i, 0) = i for j = 1, 2, . . . ,n : E(0, j) = j for i = 1, 2, . . . ,m : for j = 1, 2, . . . ,n : E(i, j) = min  E(i− 1, j) + 1, E(i, j− 1) + 1, E(i− 1, j− 1) + diff(i, j) 24 / 61 Bài tập Hãy đánh giá độ phức tạp của thuật toán. for i = 0, 1, . . . ,m : E(i, 0) = i for j = 1, 2, . . . ,n : E(0, j) = j for i = 1, 2, . . . ,m : for j = 1, 2, . . . ,n : E(i, j) = min  E(i− 1, j) + 1, E(i, j− 1) + 1, E(i− 1, j− 1) + diff(i, j) 25 / 61 Ví dụ E(i, j) = min{1+E(i−1, j), 1+E(i, j−1), diff(i, j)+E(i−1, j−1)} ở đó diff(i, j) = 0 nếu x[i] = y[j] và 1 nếu ngược lại. 26 / 61 DAG của bài toán & đường đi độ dài 6 27 / 61 DAG của bài toán Xây dựng đồ thị G = (V,E) với ▶ tập đỉnh ứng với các vị trí (i, j) trong bảng, ▶ các cung (i−1, j)→ (i, j), (i, j−1)→ (i, j), (i−1, j−1)→ (i, j) đều có trọng số 1, ngoại trừ cung {(i− 1, j− 1)→ (i, j) : x[i] = y[j]} có trọng số 0. Ta cần tìm đường đi ngắn nhất từ đỉnh s = (0, 0) tới t = (m,n). Trên đường đi này: sang phải (thêm), đi xuống (xóa), đi chéo (thay thế). 28 / 61 Số lượng các bài toán con ▶ Đầu vào x1, x2, . . . , xn và một bài toán con là x1, x2, . . . , xi. Số bài toán con là tuyến tính. ▶ Đầu vào x1, x2, . . . , xn và y1, y2, . . . , ym. bài toán con là x1, x2, . . . , xi và y1, y2, . . . , yj. Số bài toán con là O(mn). ▶ Đầu vào x1, x2, . . . , xn và bài toán con là xi, xi+1, . . . , xj. Số bài toán con là O(n2). 29 / 61 Số lượng các bài toán con (2) 178 Algorithms Common subproblems Finding the right subproblem takes creativity and experimentation. But there are a few standard choices that seem to arise repeatedly in dynamic programming. i. The input is x1, x2, . . . , xn and a subproblem is x1, x2, . . . , xi. x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 The number of subproblems is therefore linear. ii. The input is x1, . . . , xn, and y1, . . . , ym. A subproblem is x1, . . . , xi and y1, . . . , yj. x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 y1 y2 y3 y4 y5 y6 y7 y8 The number of subproblems is O(mn). iii. The input is x1, . . . , xn and a subproblem is xi, xi+1, . . . , xj . x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 The numb