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 number of subproblems is O(n2). iv. The input is a rooted tree. A subproblem is a rooted subtree. If the tree has n nodes, how many subproblems are there? We’ve already encountered the first two cases, and the others are coming up shortly. ▶ Đầu vào là một cây có gốc. Một bài toán con là một cây con có gốc. ▶ Nếu cây có n nút thì có thể có bao nhiêu bài toán con? 30 / 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 cái túi ▶ Trong một vụ cướp, tên trộm tìm thấy nhiều chiến lợi phẩm hơn anh ta dự kiến và phải quyết định xem lấy những gì. ▶ Chiếc túi của anh ấy (hay “knapsack”) chứa được tối đa là W pao. Có n vật để chọn có trọng lượng w1, . . . ,wn và có giá trị (theo đô la) là v1, . . . , vn. ▶ Hắn nên lấy những mặt hàng nào để được lợi nhất? Ví dụ Nên lấy đồ vật nào nếu mỗi đồ vật có số lượng vô hạn? Nếu mỗi đồ vật chỉ có một? Đồ vật Trọng lượng Giá trị ($) 1 6 30 2 3 14 3 4 16 4 2 9 32 / 61 Các đồ vật có thể lấy nhiều lần Câu hỏi Bài toán con là gì? bài toán với trọng lượng túi nhỏ hơn w ≤W hay với số đồ vật ít hơn. Ví dụ 1, . . . , j với j ≤ n. Đưa về bài toán con với trọng lượng túi nhỏ hơn Đặt K(w) = giá trị lớn nhất chọn được khi trọng lượng túi là w. Khi đó K(w) = K(w− wi) + vi với đồ vật i nào đó. Do không biết là đồ vật nào được thêm vào, ta sẽ thử mọi khả năng: K(w) = max i:wi≤w {K(w− wi) + vi}. 33 / 61 Thuật toán quy hoạch động K(0) = 0 for w = 1 to W : K(w) = max{K(w− wi) + vi : wi ≤ w} return K(W) Câu hỏi Độ phức tạp của thuật toán này là gì? 34 / 61 Mỗi đồ vật chỉ lấy một lần Câu hỏi Bài toán con là gì? Giá trị K(w− wn) rất lớn cũng không giúp gì vì ta không biết đồ vật n đã có trong lời giải con chưa. K(w, j) = giá trị lớn nhất chọn được khi trọng lượng túi là w và các đồ vật là 1, 2, . . . , j. 35 / 61 Đưa về bài toán nhỏ hơn K(w, j) = giá trị lớn nhất chọn được khi trọng lượng túi là w và các đồ vật là 1, 2, . . . , j. Để biểu diễn K(w, j) về các bài toán nhỏ hơn, ta xét hai trường hợp: ▶ đồ vật j cần cho giá trị tối ưu, ▶ hoặc không cần: K(w, j) = max{K(w− wj, j− 1) + vj, K(w, j− 1)}. 36 / 61 Thuật toán quy hoạch động Khởi tạo mọi K(0, j) = 0 và mọi K(w, 0) = 0 for j = 1 to n: for w = 1 to W: if wj > w: K(w, j) = K(w, j−1) else: K(w, j) = max{K(w−wj, j−1) + vj, K(w, j−1)} return K(W,n) Câu hỏi Độ phức tạp của thuật toán này là gì? 37 / 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 Ví dụ nhân nhiều ma trận ▶ Giả sử ta muốn nhân 4 ma trận A× B× C×D với số chiều là 50× 20, 20× 1, 1× 10, và 10× 100. ▶ Do tính chất kết hợp của phép nhân ma trận, ta có thể nhân theo nhiều cách. Cách đặt ngoặc Tính toán Chi phí A× ((B× C)×D) 20 · 1 · 10 + 20 · 10 · 100 + 50 · 20 · 100 120,200 (A× (B× C))×D 20 · 1 · 10 + 50 · 20 · 10 + 50 · 10 · 100 60, 200 (A× B)× (C×D) 50 · 20 · 1 + 1 · 10 · 100 + 50 · 1 · 100 7, 000 39 / 61 Hình: A× B× C×D = (A× (B× C))×D. 40 / 61 Mỗi phép nhân ứng với một cây nhị phân 41 / 61 Bài toán ▶ Ta cần tính A1 ×A2 × · · · × An trong đó các Ai có số chiều tương ứng là m0 ×m1, m1 ×m2, . . . mn−1 ×mn. ▶ Hãy xác định thứ tự tính toán tối ưu. 42 / 61 Bài toán con Đặt C(i, j) = chi phí tối thiểu để nhân Ai ×Ai+1 × · · · ×Aj. Cách tính tối ưu sẽ là một cách đặt ngoặc: (Ai ×Ai+1 × · · · ×Ak)× (Ak+1 ×Ak+2 · · · ×Aj) với chi phí tối thiểu là C(i, j) = C(i, k) + C(k+ 1, j) +mi−1 ·mk ·mj. Ta không biết vị trí k ở đâu nên phải thử mọi khả năng: C(i, j) = min i≤k<j {C(i, k) + C(k+ 1, j) +mi−1 ·mk ·mj}. 43 / 61 Thuật toán quy hoạch động for i = 1 to n: C(i, i) = 0 for s = 1 to n−1: for i = 1 to n−s: j = i+ s C(i, j) = min{C(i, k) + C(k+ 1, j) +mi−1 ·mk ·mj : i ≤ k < j} return C(1,n) Câu hỏi Độ phức tạp của thuật toán này là gì? 44 / 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 Đường đi tin cậy ngắn nhất186 Algorithms Figure 6.8 We want a path from s to t that is both short and has few edges. B DC A S 1 2 1 2 1 4 T5 3 5 6.6 Shortest paths We started this chapter with a dynamic programming algorithm for the elementary task of finding the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how these too can be accommodated by our powerful algorithmic technique. Shortest reliable paths Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture the whole truth. In a communications network, for example, even if edge lengths faithfully reflect transmission delays, there may be other considerations involved in choosing a path. For instance, each extra edge in the path might be an extra “hop” fraught with uncer- tainties and dangers of packet loss. In such cases, we would like to avoid paths with too many edges. Figure 6.8 illustrates this problem with a graph in which the shortest path from S to T has four edges, while there is another path that is a little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have to choose the latter path. Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t and an integer k, and we want the shortest path from s to t that uses at most k edges. Is there a quick way to adapt Dijkstra’s algorithm to this new task? Not quite: that algorithm focuses on the length of each shortest path without “remembering” the number of hops in the path, which is now a crucial piece of information. In dynamic programming, the trick is to choose subproblems so that all vital information is remembered and carried forward. In this case, let us define, for each vertex v and each integer i ≤ k, dist(v, i) to be the length of the shortest path from s to v that uses i edges. The starting values dist(v, 0) are ∞ for all vertices except s, for which it is 0. And the general update equation is, naturally enough, dist(v, i) = min (u,v)∈E {dist(u, i − 1) + ℓ(u, v)}. Need we say more? Hình: Ta muốn tìm đường đi từ s tới t vừa ngắn vừa ít cạnh. ▶ Trong mạng truyền thông, dù độ dài cạnh có liên quan đến độ trễ, ta có một số cân nhắc liên quan đến việc chọn đường đi. ▶ Mỗi cạnh thêm vào đường đi có thể gây ra nguy cơ mất gói tin. ▶ Ta muốn tránh đường đi có quá nhiều cạnh. 46 / 61 Bài toán đường đi tin cậy ngắn nhất ▶ Cho đồ thị trọng số G, hai đỉnh s và t, và một số nguyên dương k, ▶ ta muốn tìm đường đi ngắn nhất từ s tới t qua nhiều nhất k cạnh. dist(v, i) = độ dài đường đi ngắn nhất từ s đến v dùng i cạnh Ta có dist(v, i) = min (u,v)∈E {dist(u, i− 1) + ℓ(u, v)} 47 / 61 Bài toán tìm đường ngắn nhất giữa mọi cặp đỉnh Bài toán ▶ Các đỉnh của V = {1, 2, . . . ,n}. ▶ Ta cần tìm đường đi ngắn nhất giữa mọi cặp đỉnh. 186 Algorithms Figure 6.8 We want a path from s to t that is both short and has few edges. B DC A S 1 2 1 2 1 4 T5 3 5 6.6 Shortest paths We started this chapter with a dynamic programming algorithm for the elementary task of finding the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how these too can be accommodated by our powerful algorithmic technique. Shortest reliable paths Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture the whole truth. In a communications network, for example, even if edge lengths faithfully reflect transmission delays, there may be other considerations involved in choosing a path. For instance, each extra edge in the path might be an extra “hop” fraught with uncer- tainties and dangers of packet loss. In such cases, we would like to avoid paths with too many edges. Figure 6.8 illustrates this problem with a graph in which the shortest path from S to T has four edges, while there is another path that is a little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have to choose the latter path. Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t and an integer k, and we want the shortest path from s to t that uses at most k edges. Is there a quick way to adapt Dijkstra’s algorithm to this new task? Not quite: that algorithm focuses on the length of each shortest path without “remembering” the number of hops in the path, which is now a crucial piece of information. In dynamic programming, the trick is to choose subproblems so that all vital information is remembered and carried forward. In this case, let us define, for each vertex v and each integer i ≤ k, dist(v, i) to be the length of the shortest path from s to v that uses i edges. The starting values dist(v, 0) are ∞ for all vertices except s, for which it is 0. And the general update equation is, naturally enough, dist(v, i) = min (u,v)∈E {dist(u, i − 1) + ℓ(u, v)}. Need we say more? 48 / 61 Bài toán con dist(i, j, k) = độ dài đường đi ngắn nhất từ i tới j chỉ qua các đỉnh trung gian {1, 2, . . . , k} S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 187 All-pairs shortest paths What if we want to find the shortest path not just between s and t but between all pairs of vertices? One approach would be to execute our general shortest-path algorithm from Section 4.6.1 (since there may be negative edges) |V | times, once for each starting node. The total running time would then be O(|V |2|E|). We’ll now see a better alternative, the O(|V |3) dynamic programming-based Floyd-Warshall algorithm. Is there is a good subproblem for computing distances between all pairs of vertices in a graph? Simply solving the problem for more and more pairs or starting points is unhelpful, because it leads right back to the O(|V |2|E|) algorithm. One idea comes to mind: the shortest path u → w1 → · · · → wl → v between u and v uses some number of intermediate nodes—possibly none. Suppose we disallow intermediate nodes altogether. Then we can solve all-pairs shortest paths at once: the shortest path from u to v is simply the direct edge (u, v), if it exists. What if we now gradually expand the set of permissible intermediate nodes? We can do this one node at a time, updating the shortest path lengths at each stage. Eventually this set grows to all of V , at which point all vertices are allowed to be on all paths, and we have found the true shortest paths between vertices of the graph! More concretely, number the vertices in V as {1, 2, . . . , n}, and let dist(i, j, k) denote the length of the shortest path from i to j in which only nodes {1, 2, . . . , k} can be used as interme- diates. Initially, dist(i, j, 0) is the length of the direct edge between i and j, if it exists, and is ∞ otherwise. What happens when we expand the intermediate set to include an extra node k? We must reexamine all pairs i, j and check whether using k as an intermediate point gives us a shorter path from i to j. But this is easy: a shortest path from i to j that uses k along with possibly other lower-numbered intermediate nodes goes through k just once (why? because we assume that there are no negative cycles). And we have already calc lated the length of the shortest path from i to k and from k to j using only lower-numbered vertices: dist(k, j, k − 1) k j dist(i, k, k − 1) i dist(i, j, k − 1) Thus, using k gives us a shorter path from i to j if and only if dist(i, k, k − 1) + dist(k, j, k − 1) < dist(i, j, k − 1), in which case dist(i, j, k) should be updated accordingly. Here is the Floyd-Warshall algorithm—and as you can see, it takes O(|V |3) time. for i = 1 to n: for j = 1 to n: dist(i, j, 0) =∞ Đường đi i đến j qua đỉnh k sẽ ngắn hơn là không qua đỉnh k nếu và chỉ nếu: dist(i, k, k−1) + dist(k, j, k−1) < dist(i, j, k−1), 49 / 61 Thuật toán quy hoạch động for i = 1 to n: for j = 1 to n: dist(i, j, 0) =∞ for all (i, j) ∈ E: dist(i, j, 0) = ℓ(i, j) for k = 1 to n: for i = 1 to n: for j = 1 to n: dist(i, j, k) = min { dist(i, k, k−1) + dist(k, j, k−1), dist(i, j, k−1) 50 / 61 Bài toán người bán hàng du lịch 186 Algorithms Figure 6.8 We want a path from s to t that is both short and has few edges. B DC A S 1 2 1 2 1 4 T5 3 5 6.6 Shortest paths We started this chapter with a dynamic programming algorithm for the elementary task of finding the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how these too can be accommodated by our powerful algorithmic technique. Shortest reliable paths Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture the whole truth. In a communications network, for example, even if edge lengths faithfully reflect transmission delays, there may be other considerations involved in choosing a path. For instance, each extra edge in the path might be an extra “hop” fraught with uncer- tainties and dangers of packet loss. In such cases, we would like to avoid paths with too many edges. Figure 6.8 illustrates this problem with a graph in which the shortest path from S to T has four edges, while there is another path that is a little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have to choose the latter path. Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t and an integer k, and we want the shortest path from s to t that uses at most k edges. Is there a quick way to adapt Dijkstra’s algorithm to this new task? Not quite: that algorithm focuses on the length of each shortest path without “remembering” the number of hops in the path, which is now a crucial piece of information. In dynamic programming, the trick is to choose subproblems so that all vital information is remembered and carried forward. In this case, let us define, for each vertex v and each integer i ≤ k, dist(v, i) to be the length of the shortest path from s to v that uses i edges. The starting values dist(v, 0) are ∞ for all vertices except s, for which it is 0. And the general update equation is, naturally enough, dist(v, i) = min (u,v)∈E {dist(u, i − 1) + ℓ(u, v)}. Need we say more? ▶ Một người bán hàng thích du lịch đang sẵn sàng cho một chuyến đi bán hàng. ▶ Bắt đầu từ nhà, với chiếc vali trong tay, anh sẽ đi một hành trình trong đó mỗi thành phố cần đến sẽ được thăm đúng một lần trước khi quay về nhà. ▶ Cho khoảng cách dij giữa mỗi cặp thành phố i và j, anh ta nên thăm các thành phố theo thứ tự nào để tối ưu tổng khoảng cách? 51 / 61 Bài tập Người bán hàng nên thăm các thành phố theo thứ tự nào để tối ưu tổng khoảng cách? 186 Algorithms Figure 6.8 We want a path from s to t that is both short and has few edges. B DC A S 1 2 1 2 1 4 T5 3 5 6.6 Shortest paths We started this chapter with a dynamic programming algorithm for the elementary task of finding the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how these too can be accommodated by our powerful algorithmic technique. Shortest reliable paths Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture the whole truth. In a communications network, for example, even if edge lengths faithfully reflect transmission delays, there may be other considerations involved in choosing a path. For instance, each extra edge in the path might be an extra “hop” fraught with uncer- tainties and dangers of packet loss. In such cases, we would like to avoid paths with too many edges. Figure 6.8 illustrates this problem with a graph in which the shortest path from S to T has four edges, while there is another path that is a little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have to choose the latter path. Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t and an integer k, and we want the shortest path from s to t that uses at most k edges. Is there a quick way to adapt Dijkstra’s algorithm to this new task? Not quite: that algorithm focuses on the length of each shortest path without “remembering” the number of hops in the path, which is now a crucial piece of information. In dynamic programming, the trick is to choose subproblems so that all vital information is remembered and carried forward. In this case, let us define, for each vertex v and each integer i ≤ k, dist(v, i) to be the length of the shortest path from s to v that uses i edges. The starting values dist(v, 0) are ∞ for all vertices except s, for which it is 0. And the general update equation is, naturally enough, dist(v, i) = min (u,v)∈E {dist(u, i − 1) + ℓ(u, v)}. Need we say more? 52 / 61 Bài toán con186 Algorithms Figure 6.8 We want a path from s to t that is both short and has few edges. B DC A S 1 2 1 2 1 4 T5 3 5 6.6 Shortest paths We started this chapter with a dynamic programming algorithm for the elementary task of finding the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how these too can be accommodated by our powerful algorithmic technique. Shortest reliable paths Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture the whole truth. In a communications network, for example, even if edge lengths faithfully reflect transmission delays, there may be other considerations involved in choosing a path. For instance, each extra edge in the path might be an extra “hop” fraught with uncer- tainties and dangers of packet loss. In such cases, we would like to avoid paths with too many edges. Figure 6.8 illustrates this problem with a graph in which the shortest path from S to T has four edges, while there is another path that is a little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have to choose the latter path. Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t and an integer k, and we want the shortest path from s to t that uses at most k edges. Is there a quick way to adapt Dijkstra’s algorithm to this new task? Not quite: that algorithm focuses on the length of each shortest path without “remembering” the number of hops in the path, which is now a crucial piece of information. In dynamic programming, the trick is to choose subproblems so that all vital information is remembered and carried forward. In this case, let us define, for each vertex v and each integer i ≤ k, dist(v, i) to be the length of the shortest path from s to v that uses i edges. The starting values dist(v, 0) are ∞ for all vertices except s, for which it is 0. And the general update equation is, naturally enough, dist(v, i) = min (u,v)∈E {dist(u, i − 1) + ℓ(u, v)}. Need we say more? Với mỗi tập con các thành phố S = {1, 2, . . . ,n} có chứa 1, và j ∈ S, ta ký hiệu C(S, j) là độ dài của đường đi ngắn nhất thăm mỗi đỉnh của S đúng một lần, bắt đầu từ 1 và kết thúc tại j. 53 / 61 Đưa về bài toán nhỏ hơn ▶ Nếu ta bắt đầu tại 1 và kết thúc tại j; ta nên chọn đến đỉnh nào trước khi đến j? ▶ Đỉnh này sẽ là một đỉnh i ∈ S thỏa mãn: độ dài đường đi ngắn nhất từ 1 đến i cộng với dij là nhỏ nhất. C(S, j) = min i∈S:i̸=j C(S− {j}, i) + dij ▶ Khi |S| > 1, ta ký hiệu C(S, 1) =∞ vì đường đi không thể vừa bắt đầu và kết thúc ở 1. 54 / 61 Thuật toán quy hoạch động C({1}, 1) = 0 for s = 2 to n: for all tập con S ⊆ {1, 2, . . . ,n} thỏa mãn |S| = s và 1 ∈ S: C(S, 1) =∞ for all j ∈ S, j ̸= 1: C(S, j) = min{C(S− {j}, i) + dij : i ∈ S, i ̸= j} return minjC({1, . . . ,n}, j) + dj1 Có nhiều nhất 2n · n bài toán con, và mỗi bài mất thời gian tuyến tính để giải. Độ phức tạp là O(n2 · 2n). 55 / 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 Tập độc lập Định nghĩa Một tập con các đỉnh S ⊆ V là một tập độc lập của đồ thị G = (V,E) nếu không có cạnh giữa chúng. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 191 Figure 6.10 The largest independent set in this graph has size 3. 1 2 3 4 5 6 Figure 6.11 I(u) is the size of the largest independent set of the subtree rooted at u. Two cases: either u is in this independent set, or it isn’t. r u Exercises 6.1. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15,−30, 10,−5, 40, 10, then 15,−30, 10 is a contiguous subsequence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1, a2, . . . , an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10,−5, 40, 10, with a sum of 55. (Hint: For each j ∈ {1, 2, . . . , n}, consider contiguous subsequences ending exactly at position j.) 6.2. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. ▶ {1, 5} là một tập độc lập, nhưng {1, 4, 5} không phải. ▶ Tập độc lập lớn nhất là {2, 3, 6}. 57 / 61 Tập độc lập trên cây ▶ Bài toán tìm tập độc lập lớn nhất được nhiều người tin rằng không có thuật toán hiệu quả để giải nó. ▶ Nhưng khi đồ thị là một cây thì bài toán có thể giải trong thời gian tuyến tính. Bài toán con Lấy một nút r bất kỳ làm gốc của cây. Mỗi nút u bây giờ sẽ xác định một cây con gốc u. Ta xét bài toán con: I(u) = kích thước tập độc lập lớn nhất của cây con gốc u. Mục đích của ta là tìm I(r). 58 / 61 Đưa về bài toán nhỏ hơn S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 191 Figure 6.10 The largest independent set in this graph has size 3. 1 2 3 4 5 6 Figure 6.11 I(u) is the size of the largest independent set of the subtree rooted at u. Two cases: either u is in this independent set, or it isn’t. r u Exercises 6.1. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15,−30, 10,−5, 40, 10, then 15,−30, 10 is a contiguous subsequence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1, a2, . . . , an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10,−5, 40, 10, with a sum of 55. (Hint: For each j ∈ {1, 2, . . . , n}, consider contiguous subsequences ending exactly at position j.) 6.2. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. ▶ Giả sử ta đã biết tập độc lập lớn nhất của mọi cây con bắt đầu từ u; tức là ta đã biết I(w) cho mọi con cháu w của u. ▶ Làm thế nào để tính I(u)? ▶ Tách thành hai trường hợp: tập độc lập hoặc chứa u hoặc nó không chứa u. 59 / 61 Đưa về bài toán nhỏ hơn S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 191 Figure 6.10 The largest independent set in this graph has size 3. 1 2 3 4 5 6 Figure 6.11 I(u) is the size of the largest independent set of the subtree rooted at u. Two cases: either u is in this independent set, or it isn’t. r u Exercises 6.1. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15,−30, 10,−5, 40, 10, then 15,−30, 10 is a contiguous subsequence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1, a2, . . . , an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10,−5, 40, 10, with a sum of 55. (Hint: For each j ∈ {1, 2, . . . , n}, consider contiguous subsequences ending exactly at position j.) 6.2. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Hai trường hợp: tập độc lập hoặc chứa u hoặc nó không chứa u. I(u) = max { 1 + ∑ các cháu w của u I(w), ∑ các con w của u I(w) } 60 / 61 Độ phức tạp tính toán S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 191 Figure 6.10 The largest independent set in this graph has size 3. 1 2 3 4 5 6 Figure 6.11 I(u) is the size of the largest independent set of the subtree rooted at u. Two cases: either u is in this independent set, or it isn’t. r u Exercises 6.1. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15,−30, 10,−5, 40, 10, then 15,−30, 10 is a contiguous subsequence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1, a2, . . . , an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10,−5, 40, 10, with a sum of 55. (Hint: For each j ∈ {1, 2, . . . , n}, consider contiguous subsequences ending exactly at position j.) 6.2. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Bài tập Số cây con chính là số đỉnh. Liệu ta có thể cài đặt thuật toán chạy tro g O(|V|+ |E|)? 61 / 61