Bài giảng Toán rời rạc - Bài 19: Thuật toán tham lam - Trần Vĩnh Đức

Thuật toán tham lam Trần Vĩnh Đức HUST Ngày 1 tháng 9 năm 2019 1 / 64 Tài liệu tham khảo I S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006. 2 / 64 Nội dung Cây bao trùm nhỏ nhất Mã hóa Huffman Công thức Horn Phủ các tập Bài toán P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Greedy algorithms A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences. This sort of myopic behavior is easy and convenient, making it an attractive algorith- mic strategy. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees. 5.1 Minimum spanning trees Suppose you are asked to network a collection of computers by linking selected pairs of them. This translates into a graph problem in which nodes are computers, undirected edges are potential links, and the goal is to pick enough of these edges that the nodes are connected. But this is not all; each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network? A B C D E F 4 1 4 3 4 2 5 6 4 One immediate observation is that the optimal set of edges cannot contain a cycle, because removing an edge from this cycle would reduce the cost without compro- mising connectivity: Property 1 Removing a cycle edge cannot disconnect a graph. So the solution must be connected and acyclic: undirected graphs of this kind are called trees. The particular tree we want is the one with minimum total weight, known as the minimum spanning tree. Here is its formal definition. 127 I Bạn cần xây dựng mạng máy tính bằng cách kết nối từng cặp máy. I Cần chọn một số kết nối để mạng liên thông; I nhưng không phải tất cả các cặp: Mỗi kết nối tốn một chi phí (tiền bảo trì). I Mạng với chi phí nhỏ nhất là gì? 4 / 64 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Greedy algorithms A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences. This sort of myopic behavior is easy and convenient, making it an attractive algorith- mic strategy. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees. 5.1 Minimum spanning trees Suppose you are asked to network a collection of computers by linking selected pairs of them. This translates into a graph problem in which nodes are computers, undirected edges are potential links, and the goal is to pick enough of these edges that the nodes are connected. But this is not all; each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network? A B C D E F 4 1 4 3 4 2 5 6 4 One immediate observation is that the optimal set of edges cannot contain a cycle, because removing an edge from this cycle would reduce the cost without compro- mising connectivity: Property 1 Removing a cycle edge cannot disconnect a graph. So the solution must be connected and acyclic: undirected graphs of this kind are called trees. The particular tree we want is the one with minimum total weight, known as the minimum spanning tree. Here is its formal definition. 127 Tính chất Xóa một cạnh trên chu trình không làm mất tính liên thông của đồ thị. Vậy, mạng với chi phí nhỏ nhất phải là một cây. 5 / 64 Bài toán Cây bao trùm nhỏ nhất (Minimal Spaning Tree) I Input: Đồ thị vô hướng G = (V,E); mỗi cạnh có trọng số we. I Output: Một cây T = (V,E′) với E′ ⊆ E, với tổng trọng số weight(T) = ∑ e∈E′ we là nhỏ nhất. 6 / 64 Tìm cây bao trùm P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Greedy algorithms A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences. This sort of myopic behavior is easy and convenient, making it an attractive algorith- mic strategy. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees. 5.1 Minimum spanning trees Suppose you are asked to network a collection of computers by linking selected pairs of them. This translates into a graph problem in which nodes are computers, undirected edges are potential links, and the goal is to pick enough of these edges that the nodes are connected. But this is not all; each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network? A B C D E F 4 1 4 3 4 2 5 6 4 One immediate observation is that the optimal set of edges cannot contain a cycle, because removing an edge from this cycle would reduce the cost without compro- mising connectivity: Property 1 Removing a cycle edge cannot disconnect a graph. So the solution must be connected and acyclic: undirected graphs of this kind are called trees. The particular tree we want is the one with minimum total weight, known as the minimum spanning tree. Here is its formal definition. 127 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 128 5.1 Minimum spanning trees Input: An undirected graph G = (V, E ); edge weights we. Output: A tree T = (V, E ′), with E ′ ⊆ E , that minimizes weight(T) = ∑ e∈E ′ we. In the prec ding example, the minimum spanning tree has a cost of 16: A B C D E F 1 4 2 5 4 However, this is not the only optimal solution. Can you spot another? 5.1.1 A greedy approach Kruskal’s minimum spanning tree algorithm starts with the empty graph and then selects edges from E according to the following rule. Repeatedly add the next lightest edge that doesn’t produce a cycle. In o r words, it constructs the tree ed e by edge and, apart from taking care to avoid cycles, simply picks whichever edge is cheapest at themoment. This is a greedy algorithm: every decision it makes is the one with the most obvious immediate advantage. Figure 5.1 shows an example. We start with an empty graph and then attempt to add edges in increasing order of weight (ties are broken arbitrarily): B − C , C − D, B − D, C − F , D − F , E − F , A− D, A− B, C − E , A− C . The first two succeed, but the third, B − D, would produce a cycle if added. So we ignore it and move along. The final result is a tree with cost 14, the minimum possible. Figure 5.1 The minimum spanning tree found by Kruskal’s algorithm. B A 6 5 3 42 FD C E 5 4 1 2 4 B A FD C E Đây có phải lời giải tối ưu không? 7 / 64 Thuật toán Kruskal P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Greedy algorithms A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences. This sort of myopic behavior is easy and convenient, making it an attractive algorith- mic strategy. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees. 5.1 Minimum spanning trees Suppose you are asked to network a collection of computers by linking selected pairs of them. This translates into a graph problem in which nodes are computers, undirected edges are potential links, and the goal is to pick enough of these edges that the nodes are connected. But this is not all; each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network? A B C D E F 4 1 4 3 4 2 5 6 4 One immediate observation is that the optimal set of edges cannot contain a cycle, because removing an edge from this cycle would reduce the cost without compro- mising connectivity: Property 1 Removing a cycle edge cannot disconnect a graph. So the solution must be connected and acyclic: undirected graphs of this kind are called trees. The particular tree we want is the one with minimum total weight, known as the minimum spanning tree. Here is its formal definition. 127 Bắt đầu với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau. Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành chu trình. 8 / 64 Ví dụ: Thuật toán Kruskal 1 2 3 4 5 6 7 7 8 5 9 7 5 15 6 8 9 11 Hình: Nguồn: tikz examples 9 / 64 Nhát cắt Định nghĩa Xét đồ thị G = (V,E). Một nhát cắt là một cách chia tập đỉnh thành hai nhóm: S và V− S. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 130 5.1 Minimum spanning trees Figure 5.2 T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a cycle. This cycle must contain at least one other edge, s own here as e′, across the cut (S,V − S). e S V − S e The correctness of Kruskal’s method follows from a certain cut property, which is general enough to also justify a whole slew of other minimum spanning tree algorithms. 5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of aminimum spanning tree of G = (V, E ). Pick any subset of nodes S for which X does not cross between S and V − S, and let e be the lightest edge across this partition. Then X ∪ {e} is part of some MST. A cut is any partition of the vertices into two groups, S and V − S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V − S), provided X has no edges across the cut. Let’s see why this holds. Edges X are part of some MST T ; if the new edge e also happens to be part of T , then there is nothing to prove. So assume e is not in T . We will construct a different MST T ′ containing X ∪ {e} by altering T slightly, changing just one of its edges. Add edge e to T . Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e′ across the cut (S,V − S) (Figure 5.2). If we now remove this edge, we are left with T ′ = T ∪ {e}− {e′}, which we will show to be a tree. T ′ is connected by Property 1, since e′ is a cycle edge. And it has the same number of edges as T ; so by Properties 2 and 3, it is also a tree. Moreover, T ′ is a minimum spanning tree. Compare its weight to that of T : weight(T ′) = weight(T)+ w(e)−w(e′). Hình: Nhát cắt và các cạnh nối giữa hai phân hoạch. 10 / 64 Tính chất Cắt Giả sử các cạnh X là một phần của một MST nào đó của G = (V,E). Chọn một tập đỉnh bất kỳ S sao cho không có cạnh nào của X nối giữa S và V− S, và xét e là cạnh có trọng số nhỏ nhất nối hai phân hoạch này. Khi đó, X∪ {e} là một phần của một MST nào đó. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Algorithms 131 Figure 5.3 The cut property at work. (a) An undirected graph. (b) Set X has three edges, and is part of the MST T on the rig t. (c) If S = {A, B,C , D}, then one of the minimum-weight edges across the cut (S,V − S) is e = {D, E}. X ∪ {e} is part of MST T ′, shown on the right. (a) A B C E FD 2 2 3 3 41 1 2 1 (b) Edges X: A B C E FD MST T : A B C E FD (c) The cut: A B C E FD e S V − S MST T : A B C E FD Both e and e′ cross between S and V − S, and e is specifically the lightest edge of this type. Therefore w(e) ≤ w(e′), and weight(T ′) ≤ weight(T). Since T is an MST, it must be the case that weight(T ′) = weight(T) and that T ′ is also an MST. Figure 5.3 shows an example of the cut property. Which edge is e′? 5.1.3 Kruskal’s algorithm We are ready to justify Kruskal’s algorithm. At any given moment, the edges it has already chosen form a partial solution, a collection of connected components each of which has a tree structure. The next edge e to be added connects two of these components; call them T1 and T2. Since e is the lightest edge that doesn’t produce a cycle, it is certain to be the lightest edge between T1 and V − T1 and therefore satisfies the cut property. Now we fill in some implementation details. At each stage, the algorithm chooses an edge to add to its current partial solution. To do so, it needs to test each candi- date edge u− v to see whether the endpoints u and v lie in different components; otherwise the edge produces a cycle. And once an edge is chosen, the correspond- ing components need to be merged. What kind of data structure supports such operations? P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Algorithms 131 Figure 5.3 The cut property at work. (a) An undirected graph. (b) Set X has three edges, and is part of the MST T on the right. (c) If S = {A, B,C , D}, then one of the minimum-weight edges across the cut (S,V − S) is e = {D, E}. X ∪ {e} is part of MST T ′, shown on the right. (a) A B C E FD 2 2 3 3 41 1 2 1 (b) Edges X: A B C E FD MST T : A B C E FD (c) The cut: A B C E FD e S V − S MST T : A B C E FD Both e and e′ cross between S and V − S, and e is specifically the lightest edge of this type. Therefore w(e) ≤ w(e′), and weight(T ′) ≤ weight(T). Since T is an MST, it must be the case that weight(T ′) = weight(T) and that T ′ is also an MST. Figure 5.3 shows an example of the cut property. Which edge is e′? 5.1.3 Kruskal’s algorithm We are ready to justify Kruskal’s algorithm. At any given moment, the edges it has already chosen form a partial solution, a collection of connected components each of which has a tree structure. The next edge e to be added connects two of these components; call them T1 and T2. Since e is the lightest edge that doesn’t produce a cycle, it s certain to be the lightest edge between T1 and V − T1 and therefore satisfies the cut prop rty. Now we fill in some implementation details. At each stage, the algorithm chooses an edge to add to its current partial solution. To do so, it needs to test each candi- date edge u− v to see whether the endpoints u and v lie in different components; otherwise the edge produces a cycle. And once an edge is chosen, the correspond- ing components need to be merged. What kind of data structure supports such operations? 11 / 64 Ví dụ P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Algorithms 131 Figure 5.3 The cut property at work. (a) An undirected graph. (b) Set X has three edges, and is part of the MST T on the right. (c) If S = {A, B,C , D}, then one of the minimum-weight edges across the cut (S,V − S) is e = {D, E}. X ∪ {e} is part of MST T ′, shown on the right. (a) A B C E FD 2 2 3 3 41 1 2 1 (b) Edges X: A B C E FD MST T : A B C E FD (c) The cut: A B C E FD e S V − S MST T : A B C E FD Both e and e′ cross between S and V − S, and e is specifically the lightest edge of this type. Therefore w(e) ≤ w(e′), and weight(T ′) ≤ weight(T). Since T is an MST, it must be the case that weight(T ′) = weight(T) and that T ′ is also an MST. Figure 5.3 shows an example of the cut property. Which edge is e′? 5.1.3 Kruskal’s algorithm We are ready to justify Kruskal’s algorithm. At any given moment, the edges it has already chosen form a partial solution, a collection of connected components each of which has a tree structure. The next edge e to be added connects two of these components; call them T1 and T2. Since e is the lightest edge that doesn’t produce a cycle, it is certain to be the lightest edge between T1 and V − T1 and therefore satisfies the cut property. Now we fill in some implementation details. At each stage, the algorithm chooses an edge to add to its current partial solution. To do so, it needs to test each candi- date edge u− v to see whether the endpoints u and v lie in different components; otherwise the edge produces a cycle. And once an edge is chosen, the correspond- ing components need to be merged. What kind of data structure supports such operations? P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Algorithms 131 Figure 5.3 The cut property at work. (a) An undirected graph. (b) Set X has three edges, and is part of the MST T on the right. (c) If S = {A, B,C , D}, then one of the minimum-weight edges across the cut (S,V − S) is e = {D, E}. X ∪ {e} is part of MST T ′, shown on the right. (a) A B C E FD 2 2 3 3 41 1 2 1 (b) Edges X: A B C E FD MST T : A B C E FD (c) The cut: A B C E FD e S V − S MST T : A B C E FD Both e and e′ cross between S and V − S, and e is specifically the lightest edge of this type. Therefore w(e) ≤ w(e′), and weight(T ′) ≤ weight(T). Since T is an MST, it must be the case that weig t(T ′) = weight(T) and that T ′ is also an MST. Figure 5.3 shows an example of the cut property. Which edge is e′? 5.1.3 Kruskal’s algorithm We are ready to justify Kruskal’s algorithm. At any given moment, the edges it has already chosen form a partial solution, a collection of connected components each of which has a tree structure. The n xt edge e to be added connects two of these components; call them T1 and T2. Since e is the lightest edge that doesn’t produce a cycle, it is certain to be the lightest edge between T1 and V − T1 and therefore satisfies the cut property. Now we fill in some implementation details. At each stage, the algorithm chooses an edge to add to its current partial solution. To do so, it needs to test each candi- date edge u− v to see whether the endpoints u and v lie in different components; otherwise the edge produces a cycle. And once an edge is chosen, the correspond- ing components need to be merged. What kind of data structure supports such operations? Nhát cắt S và V− S và một cây bao trùm nhỏ nhất. 12 / 64 Chứng minh Tính chất Cắt P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 130 5.1 Minimum spanning trees Figure 5.2 T ∪ {e}. T e addi ion of e (dotted) to T (solid lines) produces a cycle. This cycle must contain at least one other edge, shown here as e′, across the cut (S,V − S). e S V − S e The correctness of Kruskal’s method follows from a certain cut property, which is general enough to also justify a whole slew of other minimum spanning tree algorithms. 5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of aminimum spanning tree of G = (V, E ). Pick any subset of nodes S for which X does not cross between S and V − S, and let e be the lightest edge across this partition. Then X ∪ {e} is part of some MST. A cut is any partition of the vertices into two groups, S and V − S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V − S), provided X has no edges across the cut. Let’s see why this holds. Edges X are part of some MST T ; if the new edge e also happens to be part of T , then there is nothing to prove. So assume e is not in T . We will construct a different MST T ′ containing X ∪ {e} by altering T slightly, changing just one of its edges. Add edge e to T . Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e′ across the cut (S,V − S) (Figure 5.2). If we now remove this edge, we are left with T ′ = T ∪ {e}− {e′}, which we will show to be a tree. T ′ is connected by Property 1, since e′ is a cycle edge. And it has the same number of edges as T ; so by Properties 2 and 3, it is also a tree. Moreover, T ′ is a minimum spanning tree. Compare its weight to that of T : weight(T ′) = weight(T)+ w(e)−w(e′). Xét X là một phần của MST T; nếu cạnh e cũng là một phần của T thì Tính chất Cắt đúng. 13 / 64 Chứng minh Tính chất Cắt (2) P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 130 5.1 Minimum spanning trees Figure 5.2 T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a cycle. This cycle must contain at least one other edge, shown here as e′, across the cut (S,V − S). e S V − S e The correctness of Kruskal’s method follows from a certain cut property, which is general enough to also justify a whole slew of other minimum spanning tree algorithms. 5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of aminimum spanning tree of G = (V, E ). Pick any subset of nodes S for which X does not cross between S and V − S, and let e be the lightest edge across this partition. Then X ∪ {e} is part of some MST. A cut is any partition of the vertices into two groups, S and V − S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V − S), provided X has no edges across the cut. Let’s see why this holds. Edges X are part of some MST T ; if the new edge e also happens to be part of T , then there is nothing to prove. So assume e is not in T . We will construct a different MST T ′ containing X ∪ {e} by altering T slightly, changing just one of its edges. Add edge e to T . Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e′ across the cut (S,V − S) (Figure 5.2). If we now remove this edge, we are left with T ′ = T ∪ {e}− {e′}, which we will show to be a tree. T ′ is connected by Property 1, since e′ is a cycle edge. And it has the same number of edges as T ; so by Properties 2 and 3, it is also a tree. Moreover, T ′ is a minimum spanning tree. Compare its weight to that of T : weight(T ′) = weight(T)+ w(e)−w(e′). I Giả sử e không thuộc MST T. Xét T ∪ {e}. I Việc thêm cạnh e vào T sẽ tạo ra một chu trình. I Chu trình này chứa ít nhất một cạnh e′ khác đi qua nhát cắt. 14 / 64 Chứng minh Tính chất Cắt (3) P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 130 5.1 Minimum spanning trees Figure 5.2 T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a cycle. This cycle must contain at least one other edge, shown here as e′, across the cut (S,V − S). e S V − S e The correctness of Kruskal’s method follows from a certain cut property, which is general enough to also justify a whole slew of other minimum spanning tree algorithms. 5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of aminimum spanning tree of G = (V, E ). Pick any subset of nodes S for which X does not cross between S and V − S, and let e be the lightest edge across this partition. Then X ∪ {e} is part of some MST. A cut is any partition of the vertices into two groups, S and V − S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V − S), provided X has no edges across the cut. Let’s see why this holds. Edges X are part of some MST T ; if the new edge e also happens to be part of T , then there is nothing to prove. So assume e is not in T . We will construct a different MST T ′ containing X ∪ {e} by altering T slightly, changing just one of its edges. Add edge e to T . Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e′ across the cut (S,V − S) (Figure 5.2). If we now remove this edge, we are left with T ′ = T ∪ {e}− {e′}, which we will show to be a tree. T ′ is connected by Property 1, since e′ is a cycle edge. And it has the same number of edges as T ; so by Properties 2 and 3, it is also a tree. Moreover, T ′ is a minimum spanning tree. Compare its weight to that of T : weight(T ′) = weight(T)+ w(e)−w(e′). I Xét đồ thị T′ = (T ∪ {e})− {e′}. I T′ là một cây. Tại sao? G = (V,E) là một cây nếu và chỉ nếu G liên thông và |E| = |V| − 1; 15 / 64 Chứng minh Tính chất Cắt (3) P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 130 5.1 Minimum spanning trees Figure 5.2 T ∪ {e}. The addition of e (dotted) to T (solid lines) produces a cycle. This cycle must contain at least one other edge, shown here as e′, across the cut (S,V − S). e S V − S e The correctness of Kruskal’s method follows from a certain cut property, which is general enough to also justify a whole slew of other minimum spanning tree algorithms. 5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of aminimum spanning tree of G = (V, E ). Pick any subset of nodes S for which X does not cross between S and V − S, and let e be the lightest edge across this partition. Then X ∪ {e} is part of some MST. A cut is any partition of the vertices into two groups, S and V − S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V − S), provided X has no edges across the cut. Let’s see why this holds. Edges X are part of some MST T ; if the new edge e also happens to be part of T , then there is nothing to prove. So assume e is not in T . We will construct a different MST T ′ containing X ∪ {e} by altering T slightly, changing just one of its edges. Add edge e to T . Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e′ across the cut (S,V − S) (Figure 5.2). If we now remove this edge, we are left with T ′ = T ∪ {e}− {e′}, which we will show to be a tree. T ′ is connected by Property 1, since e′ is a cycle edge. And it has the same number of edges as T ; so by Properties 2 and 3, it is also a tree. Moreover, T ′ is a minimum spanning tree. Compare its weight to that of T : weight(T ′) = weight(T)+ w(e)−w(e′). I Xét đồ thị T′ = T ∪ {e} − {e′}. I T′ là một cây. I Cây T′ cũng là cây bao trùm nhỏ nhất vì: weight(T′) = weight(T) + w(e)− w(e′) và w(e) ≤ w(e′). 16 / 64 Tính đúng đắn của Thuật toán Kruskal? P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch05 GTBL020-Dasgupta-v10 August 10, 2006 22:46 Chapter 5 Greedy algorithms A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences. This sort of myopic behavior is easy and convenient, making it an attractive algorith- mic strategy. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees. 5.1 Minimum spanning trees Suppose you are asked to network a collection of computers by linking selected pairs of them. This translates into a graph problem in which nodes are computers, undirected edges are potential links, and the goal is to pick enough of these edges that the nodes are connected. But this is not all; each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network? A B C D E F 4 1 4 3 4 2 5 6 4 One immediate observation is that the optimal set of edges cannot contain a cycle, because removing an edge from this cycle would reduce the cost without compro- mising connectivity: Property 1 Removing a cycle edge cannot disconnect a graph. So the solution must be connected and acyclic: undirected graphs of this kind are called trees. The particular tree we want is the one with minimum total weight, known as the minimum spanning tree. Here is its formal definition. 127 Bắt đầu với đồ thị rỗng và chọn cạnh từ E theo quy tắc sau. Lặp lại việc thêm cạnh nhỏ nhất mà không tạo thành chu trình. 17 / 64 Cài đặt thuật toán Kruskal Sử dụng cấu trúc dữ liệu disjoint sets: mỗi tập là một thành phần liên thông. Disjoint sets có ba phép toán: I makeset(x): tạo ra một tập chỉ chứa phần tử x. I find(x): x thuộc tập nào? I union(x, y): hợp hai tập chứa x và y. 18 / 64 procedure kruskal(G,w) Input: đồ thị liên thông vô hướng G = (V,E); với trọng số cạnh we Output: MST định nghĩa bởi tập cạnh X. for all u ∈ V: makeset(u) X = ∅ Sắp xếp các cạnh e theo trọng số for all {u, v} ∈ E, lấy không giảm theo trọng số: if find(u) ̸= find(v): thêm cạnh {u, v} vào X union(u, v) 19 / 64 Cấu trúc dữ liệu Disjoint sets I Lưu trữ tập dùng cây có hướng. I Các nút là các phần tử của tập. I Mỗi nút x có một con trỏ tới nút cha pi(x) của nó. I Ngoài ra mỗi nút có một rank để lưu trữ độ cao của cây con từ nút này. I Phần tử ở gốc là đại diện, hoặc là tên, của tập. I Cha của gốc là chính nó. 20 / 64 Ví dụ Cây có hướng biểu diễn hai tập {B,E} và {A,C,D,F,G,H} 144 Algorithms Figure 5.4 Kruskal’s minimum spanning tree algorithm. procedure kruskal(G,w) Input: A connected undirected graph G = (V,E) with edge weights we Output: A minimum spanning tree defined by the edges X for all u ∈ V : makeset(u) X = {} Sort the edges E by weight for all edges {u, v} ∈ E, in increasing order of weight: if find(u) ̸= find(v): add edge {u, v} to X union(u, v) And whenever we add an edge, we are merging two components. union(x, y): merge the sets containing x and y. The final algorithm is shown in Figure 5.4. It uses |V | makeset, 2|E| find, and |V | − 1 union operations. 5.1.4 A data structure for disjoint sets Union by rank One way to store a set is as a directed tree (Figure 5.5). Nodes of the tree are elements of the set, arranged in no particular order, and each has parent pointers that eventually lead up to the root of the tree. This root element is a convenient representative, or name, for the set. It is distinguished from the other elements by the fact that its parent pointer is a self-loop. Figure 5.5 A directed-tree representation of two sets {B,E} and {A,C,D,F,G,H}. E H B C F A D G 21 / 64 Cài đặt Disjoint sets procedure markset(x) pi(x) = x rank(x) = 0 function find(x) while x ̸= pi(x): x = pi(x) return x Ở đây, pi(x) chỉ đến cha của x. 22 / 64 procedure union(x, y) rx= find(x) ry= find(y) if rx = ry: return if rank(rx) > rank(ry): pi(ry) = rx else: pi(rx) = ry if rank(rx) = rank(ry): rank(ry) = rank(rx) + 1 23 / 64 Bài tập Hãy vẽ cây biểu diễn disjoint sets sau các phép toán sau: I makeset(A), makeset(B),..., makeset(G) I union(A,D), union(B,E), union(C,F) I union(C,G), union(E,A) I union(B,G) 24 / 64 Tính chất của union-find Tính chất Với mọi x, ta luôn có rank(x) < rank(pi(x)). Tính chất Mọi nút gốc r với rank k có ít nhất 2k nút trong cây của nó. Tính chất Nếu có n phần tử, có nhiều nhất n/2k nút có rank k. 25 / 64 Cải tiến: Path Compression Gán nút gốc là cha của mọi nút x function find(x) if x ̸= pi(x): pi(x) = find(pi(x)) (Gán nút gốc là cha của x) return pi(x) 26 / 64 Ví dụ: find(I) rồi find(K) 148 Algorithms Figure 5.7 The effect of path compression: find(I) followed by find(K). B0 D0 I0 J0 K0 H0 C1 1 G1 A3 F E2 −→ B0 0D K0 J0 I0 H0 C1 F1 G1 A3 E2 −→ B0 D H0 J0 I0 K0 G1C1 F1E2 A 0 3 to n to bring it down to 1 (or below 1). For instance, log∗ 1000 = 4 since log log log log 1000 ≤ 1. In practice there will just be the first five of the intervals shown; more are needed only if n ≥ 265536, in other words never. In a sequence of find operations, some may take longer than others. We’ll bound the overall running time using some creative accounting. Specifically, we will give each node a certain amount of pocket money, such that the total money doled out is at most n log∗ n dollars. We will then show that each find takes O(log∗ n) steps, plus some additional amount of time that can be “paid for” using the pocket money of the nodes involved—one dollar per unit of time. Thus the overall time for m find’s is O(m log∗ n) plus at most O(n log∗ n). In more detail, a node receives its allowance as soon as it ceases to be a root, at which point its rank is fixed. If this rank lies in the interval {k + 1, . . . , 2k}, the node receives 2k dollars. By Property 3, the number of nodes with rank > k is bounded by n 2k+1 + n 2k+2 + · · · ≤ n 2k . Therefore the total money given to nodes in this particular interval is at most n dollars, and since there are log∗ n intervals, the total money disbursed to all nodes is ≤ n log∗ n. 27 / 64 Thuật toán tổng quát dựa trên tính chất cắt X = { } Lặp lại các bước sau cho đến khi |X| = |V| − 1: I Chọn một tập S ⊂ V thỏa mãn: X không chứa cạnh nối giữa nhát cắt S và V− S. I Xét e ∈ E là cạnh có trọng số nhỏ nhất nối giữa nhát cắt S và V− S I X = X ∪ {e} 28 / 64 Thuật toán Prim X = { } Lặp lại các bước sau cho đến khi |X| = |V| − 1: I Chọn một tập S ⊂ V thỏa mãn: X không chứa cạnh nối giữa nhát cắt S và V− S. I Xét e ∈ E là cạnh có trọng số nhỏ nhất nối giữa nhát cắt S và V− S I X = X ∪ {e} Thuật toán Prim I Tập cạnh X luôn tạo ra một cây con, và I Tập S được chọn là tập đỉnh của cây con này. 29 / 64 S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 151 Figure 5.8 Prim’s algorithm: the edges X form a tree, and S consists of its vertices. e S V − S X growing to include the vertex v ̸∈ S of smallest cost: cost(v) = min u∈S w(u, v). This is strongly reminiscent of Dijkstra’s algorithm, and in fact the pseudocode (Figure 5.9) is almost identical. The only difference is in the key values by which the priority queue is ordered. In Prim’s algorithm, the value of a node is the weight of the lightest incoming edge from set S, whereas in Dijkstra’s it is the length of an entire path to that node from the starting point. Nonetheless, the two algorithms are similar enough that they have the same running time, which depends on the particular priority queue implementation. Figure 5.9 shows Prim’s algorithm at work, on a small six-node graph. Notice how the final MST is completely specified by the prev array. Thuật toán Prim I Tập cạnh X luôn tạo r một cây con, và I Tập S được chọn là tập đỉnh của cây con này. 30 / 64 Ví dụ: Thuật toán Prim 1 2 3 4 5 6 7 7 8 5 9 7 5 15 6 8 9 11 Hình: Nguồn: tikz examples 31 / 64 Thuật toán Prim vs Dijkstra S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 151 Figure 5.8 Prim’s algorithm: the edges X form a tree, and S consists of its vertices. e S V − S X growing to include the vertex v ̸∈ S of smallest cost: cost(v) = min u∈S w(u, v). This is strongly reminiscent of Dijkstra’s algorithm, and in fact the pseudocode (Figure 5.9) is almost identical. The only difference is in the key values by which the priority queue is ordered. In Prim’s algorithm, the value of a node is the weight of the lightest incoming edge from set S, whereas in Dijkstra’s it is the length of an entire path to that node from the starting point. Nonetheless, the two algorithms are similar enough that they have the same running time, which depends on the particular priority queue implementation. Figure 5.9 shows Prim’s algorithm at work, on a small six-node graph. Notice how the final MST is completely specified by the prev array. I Mỗi bước lặp, cây con X sẽ được thêm một cạnh. I Đây là cạnh có trọng số nhỏ nhất nối giữa một đỉnh trong S và một đỉnh ngoài S. I Có nghĩa rằng, thêm vào S đỉnh v /∈ S có cost nhỏ nhất: cost(v) = min u∈S w(u, v) 32 / 64 Ví dụ 152 Algorithms Figure 5.9 Top: Prim’s minimum spanning tree algorithm. Below: An illustration of Prim’s algorithm, starting at node A. Also shown are a table of cost/prev values, and the final MST. procedure prim(G,w) Input: A connected undirected graph G = (V,E) with edge weights we Output: A minimum spanning tree defined by the array prev for all u ∈ V : cost(u) =∞ prev(u) = nil Pick any initial node u0 cost(u0) = 0 H = makequeue (V ) (priority queue, using cost-values as keys) while H is not empty: v = deletemin(H) for each {v, z} ∈ E: if cost(z) > w(v, z): cost(z) = w(v, z) prev(z) = v decreasekey(H, z) B A 6 5 3 42 FD C E 5 41 24 B A FD C E Set S A B C D E F {} 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil A 5/A 6/A 4/A ∞/nil ∞/nil A,D 2/D 2/D ∞/nil 4/D A,D,B 1/B ∞/nil 4/D A,D,B,C 5/C 3/C A,D,B,C, F 4/F Tập S A B C D E F {} 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil A 5/A 6/A 4/A ∞/nil ∞/nil A,D 2/D 2/D ∞/nil 4/D A,D,B 1/B ∞/nil 4/D A,D,B,C 5/C 3/C A,D,B,C,F 4/F 33 / 64 procedure prim(G,w) Input: đồ thị vô hướng G = (V,E) với cạnh có trọng số we. Output: MST định nghĩa bởi mảng prev. for all u ∈ V: cost(u) = ∞ prev(u) = nil (đỉnh trước u khi xây dựng cây) Chọn tùy ý một đỉnh ban đầu u0 cost(u0) = 0 H = makequeue(V) (dùng các giá trị cost làm khóa) while H khác rỗng: v = deletemin(H) for all edges {v, z} ∈ E: if cost(z) > w(v, z): cost(z) = w(v, z) prev(z) = v (đỉnh trước z là v) decreasekey(H, z) 34 / 64 Nội dung Cây bao trùm nhỏ nhất Mã hóa Huffman Công thức Horn Phủ các tập Sơ đồ nén MP3 1. Số hóa bằng cách lấy mẫu theo khoảng. Tạo ra một dãy số thực s1, s2, . . . , sT Ví dụ, với tốc độ 44, 100 mẫu trên giây, bản giao hưởng 50 phút có T = 50×60×44, 100 ≈ 130 triệu. 2. Lượng hóa. Xấp xỉ si bởi giá trị gần nhất thuộc tập hữu hạn Γ. 3. Mã hóa. Xâu s1s2 . . . sT trên bảng chữ Γ được mã hóa ở dạng nhị phân. (Dùng mã Huffman) 36 / 64 Mã hóa Ký hiệu Số lần xuất hiện A 70 triệu B 3 triệu C 20 triệu D 37 triệu I Bảng chữ Γ = {A,B,C,D} và T = 130 triệu. I Nếu mã hóa dùng 2 bit cho mỗi ký hiệu, ví dụ A→ 00, B→ 01, C→ 10, D→ 11 ta cần 260 megabits. I Liệu ta có thể dùng mã độ dài thay đổi để giảm kích thước bản mã? 37 / 64 Mã độ dài thay đổi I Dùng các dãy bit độ dài khác nhau để mã hóa các chữ cái. I Chữ cái xuất hiện thường xuyên hơn sẽ được mã bằng dãy bit ngắn hơn. I Vấn đề: Làm thế nào xác định được mỗi chữ bắt đầu và kết thúc ở đâu trong dãy bit.? Ví dụ Cách mã hóa A→ 0, C→ 01, D→ 11, B→ 001 gây ra nhập nhằng khi giải mã 001→ AC 001→ B 38 / 64 Mã tiền tố Định nghĩa Mã tiền tố là tập xâu thỏa mãn không có xâu nào là khúc đầu của xâu khác. Hãy giải mã dãy bit 10100100? 39 / 64 Kích thước bản mã Ký hiệu Số lần xuất hiện Từ mã A 70 triệu 0 B 3 triệu 100 C 20 triệu 101 D 37 triệu 11 I Kích thước bản mã = (1× 70 + 3× 3 + 3× 20 + 2× 37) megabits = 213 megabits I Cải thiện 17% so với 260 megabits khi dùng mã độ dài cố định. 40 / 64 Bài toán I Cho n ký hiệu có tần suất f1, f2, . . . , fn. I Hãy tìm cây ở đó mỗi lá ứng với một ký hiệu và có chi phí cực tiểu. Chi phí của cây = n∑ i=1 fi · (độ sâu ký hiệu thứ i trong cây) 41 / 64 Hãy tính chi phí của cây sau. Chi phí của cây = n∑ i=1 fi · (độ sâu ký hiệu thứ i trong cây) 42 / 64 I Tần suất nút lá là fi. I Tần suất nút trong là tổng tần suất của các lá con cháu của nó. Mệnh đề Chi phí của cây là tổng tần suất của mọi nút ngoại trừ nút gốc. 43 / 64 Tối ưu hàm chi phí Chi phí của cây = n∑ i=1 fi · (độ sâu của ký hiệu thứ i trong cây) Nhận xét Hai ký hiệu với tần suất nhỏ nhất sẽ phải ở đáy của cây tối ưu. 44 / 64 Xây dựng cây một cách tham lam I Tìm hai ký hiệu có tần suất nhỏ nhất, gọi là i và j, và tạo nút cha của chúng với tần suất fi + fj. Để đơn giản ký hiệu, ta giả sử chúng là f1 và f2. I Mọi cây trong đó f1 và f2 là nút lá anh em có chi phí f1 + f2 cộng với chi phí cho cây gồm n− 1 nút lá của các tần suất: (f1 + f2), f3, f4, . . . , fn. I Ta đưa về bài toán kích thước nhỏ hơn. Ta loại bỏ f1 và f2 khỏi dãy tần suất và thêm (f1 + f2) vào, và lặp lại . 45 / 64 Xây dựng cây một cách tham lam S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 155 f1 f2 f3f5 f4 f1 + f2 The latter problem is just a smaller version of the one we started with. So we pull f1 and f2 off the list of frequencies, insert (f1 + f2), and loop. The resulting algorithm can be described in terms of priority queue operations (as defined on page 120) and takes O(n log n) time if a binary heap (Section 4.5.2) is used. procedure Huffman(f) Input: An array f [1 · · ·n] of frequencies Output: An encoding tree with n leaves let H be a priority queue of integers, ordered by f for i = 1 to n: insert(H, i) for k = n+ 1 to 2n− 1: i = deletemin(H), j = deletemin(H) create a node numbered k with children i, j f [k] = f [i] + f [j] insert(H,k) Returning to our toy example: can you tell if the tree of Figure 5.10 is optimal? Hình: Loại f1, f2 và thêm f1 + f2 vào dãy tần suất. 46 / 64 procedure Huffman(f) Input: mảng f[1 · · ·n] của các tần suất Output: Một cây mã hóa với n lá Xét H là hàng đợi ưu tiên của các số nguyên, thứ tự bởi f for i = 1 to n: insert(H, i) for k = n+ 1 to 2n− 1: i = deletemin(H), j = deletemin(H) Tạo một nút đánh số k với các con là i, j f[k] = f[i] + f[j] insert(H, k) 47 / 64 Nội dung Cây bao trùm nhỏ nhất Mã hóa Huffman Công thức Horn Phủ các tập Biến Boolean I Đối tượng cơ sở trong công thức Horn là biến Boolean, nhận giá trị true hoặc false. I Một literal là một biến x hoặc nghịch đảo của nó x (“NOT x”). Ví dụ Biến x, y và z ký hiệu các khả năng sau đây: x ≡ vụ giết người xảy ra trong bếp y ≡ người quản gia vô tội z ≡ ngài đại tá đã ngủ lúc 8 giờ tối 49 / 64 Công thức Horn Trong công thức Horn, tri thức về các biến được biển diễn bởi hai loại mệnh đề: 1. Kéo theo, vế trái là một AND của một số các literal dương và vế phải là một literal dương. Các khẳng định này có dạng “nếu mệnh đề vế trái mà đúng, thì vế phải cũng phải đúng”. Ví dụ, (x ∧ w)⇒ u Một trường hợp riêng là dạng đơn ⇒ x với ý nghĩa rằng “x là true”. 2. Toàn phủ định, bao gồm một OR của một số literal âm. Ví dụ (u ∨ v ∨ y) (“không thể tất cả cùng vô tội”). 50 / 64 Bài toán nhất quán I Cho một tập các mệnh đề kéo theo hoặc toàn phủ định; I Hãy xác định liệu chúng có nhất quán. Tức là, có cách gán true/false cho các biến để thỏa mãn mọi mệnh đề. Đây cũng gọi là phép gán thỏa được. Câu hỏi Hãy xác định liệu các mệnh đề sau có nhất quán: (w ∧ y ∧ z)⇒ x, (x ∧ z)⇒ w, x⇒ y, ⇒ x, (x ∧ y)⇒ w, (w ∨ x ∨ y), (z). 51 / 64 Thuật toán tham lam Input: Một công thức Horn Output: Một phép gán thỏa được, nếu tồn tại Đặt mọi biến bằng false while còn phép kéo theo chưa thỏa mãn: Đặt biến ở vế phải của phép kéo theo này bằng true if mọi mệnh đề toàn phủ định được thỏa mãn: return phép gán else: return ``công thức không thỏa mãn'' 52 / 64 Bài tập Hãy chạy thuật toán với công thức Horn gồm các mệnh đề sau: (w ∧ y ∧ z)⇒ x, (x ∧ z)⇒ w, x⇒ y, ⇒ x, (x ∧ y)⇒ w, (w ∨ x ∨ y), (z). 53 / 64 Tính đúng đắn của thuật toán I Nếu return một phép gán, thì phép gán này phải thỏa mãn cả các mệnh đề kéo theo và các mệnh đề toàn phủ định. I Ngược lại, ta có bất biến trong vòng lặp while: Nếu một biến được đặt bằng true, vậy thì nó phải bằng true trong mọi phép gán thỏa được. Nếu có một phép gán được tìm thấy sau vòng lặp while mà không thỏa mãn mệnh đề toàn phủ định, vậy không có phép gán nào thỏa được. 54 / 64 Nội dung Cây bao trùm nhỏ nhất Mã hóa Huffman Công thức Horn Phủ các tập Xây trường học trong các thị trấn I Mỗi trường phải ở trong một thị trấn và không ai phải đi hơn 30 dặm để tới trường. I Số trường tối thiểu cần xây là bao nhiêu? 56 / 64 Xây trường học trong các thị trấn I Mỗi thị trấn x, đặt Sx là tập thị trấn cách x trong vòng 30 dặm. Một trường tại x sẽ “phủ” các thị trấn này. I Cần lấy bao nhiêu tập Sx để phủ mọi thị trấn? 57 / 64 Bài toán phủ tập I Input: Một tập B; và các tập S1,S2, . . . ,Sm ⊆ B I Output: Một cách chọn các Si sao cho hợp của chúng là B I Chi phí: Số tập được chọn 58 / 64 Thuật toán tham lam Lặp lại cho đến khi mọi phần tử của B được phủ: Chọn tập Si với nhiều phần tử chưa được phủ nhất. 59 / 64 Bài tập Hãy tìm phủ tối ưu cho tập thị trấn như sau: 60 / 64 Khẳng định Giả sử B chứa n phần tử và phủ tối ưu gồm k tập. Thuật toán tham lam sẽ dùng nhiều nhất k lnn tập. 61 / 64 Chứng minh I Xét nt là số phần tử vẫn chưa được phủ sau t lần lặp của thuật toán tham lam. Ta có n0 = n. I Vì các phần tử này bị phủ bởi k tập tối ưu, nên phải có một tập với ít nhất nt/k phần tử trong số k tập này. I Vậy chiến lược tham lam đảm bảo nt+1 ≤ nt − ntk = nt ( 1− 1k ) < nt−1 ( 1− 1k )2 < n0 ( 1− 1k )t+1 I Do 1− x ≤ e−x, ta được nt ≤ n0 ( 1− 1k )t < n0(e−1/k)t = ne−t/k I Khi t = k lnn, thì nt < ne− lnn = 1, tức là không còn phần tử nào cần phủ. 62 / 64 160 Algorithms which is most easily proved by a picture: x0 11− x e−x Thus nt ≤ n0 ( 1− 1 k )t < n0(e −1/k)t = ne−t/k. At t = k lnn, therefore, nt is strictly less than ne− lnn = 1, which means no elements remain to be covered. The ratio between the greedy algorithm’s solution and the optimal solution varies from input to input but is always less than lnn. And there are certain inputs for which the ratio is very close to lnn (Exercise 5.33). We call this maximum ratio the approximation factor of the greedy algorithm. There seems to be a lot of room for improvement, but in fact such hopes are unjustified: it turns out that under certain widely-held complexity assumptions (which will be clearer when we reach Chapter 8), there is provably no polynomial-time algorithm with a smaller approximation factor. Hình: Chỉ ra rằng 1− x ≤ e−x với mọi x, đẳng thức nếu và chỉ nếu x = 0. 63 / 64 Tỉ suất của thuật toán tham lam I Tỉ lệ giữa nghiệm của thuật toán tham lam và nghiệm tối ưu thay đổi theo dữ liệu vào nhưng luôn nhỏ hơn lnn. I Có một số input tỉ lệ rất gần với lnn. I Ta gọi tỉ lệ lớn nhất là tỉ suất của thuật toán tham lam. Nhận xét Dưới một số giả sử được thừa nhận rộng rãi, ta có thể chứng minh được rằng: không có thuật toán thời gian đa thức với tỉ suất xấp xỉ nhỏ hơn. 64 / 64