Article directory
- What is greedy algorithm
- Practical analysis of greedy algorithm
-
- 1. Divide candies
- 2. Coin change
- 3. Interval coverage
- 4.Huffman coding
What is a greedy algorithm
Regarding the greedy algorithm, let’s look at an example first.
Suppose we have a backpack that can hold 100kg of items and can hold various items. We have the following 5 types of beans, each with a different total quantity and total value. In order to maximize the total value of the items in the backpack, how do we choose which beans to put in the backpack? How much of each type of beans should be packed? 
In fact, this question is very simple. I think you can figure it out at once. Yes, we only need to calculate the unit price of each item first and install them in order from high to low. The unit prices are arranged from high to low: black beans, mung beans, red beans, green beans, and soybeans. Therefore, we can put 20kg black beans, 30kg mung beans, and 50kg red beans in our backpack.
The solution to this problem is obvious, and it essentially relies on the greedy algorithm. Combined with this example, I will summarize the steps of solving the problem with the greedy algorithm. Let’s take a look at it together.
-
The first step is that when we see this kind of problem, we must first think of the greedy algorithm: for a set of data, we define the limit value and the expected value, and hope to select a few data from it. When the limit value is met, Expectations are the highest.
By analogy to the previous example, the limit value is that the weight cannot exceed 100kg, and the expected value is the total value of the item. This set of data is 5 kinds of beans. We select a portion of them that weighs no more than 100kg and has the greatest total value.
-
In the second step, we try to see if this problem can be solved with a greedy algorithm: each time, select the data that contributes the most to the expected value under the current situation and contributes the same amount to the limit value.
Analogy to the example just now, we select the beans with the highest unit price from the remaining beans every time, that is, the beans that contribute the most to the value under the same weight.
In fact, using greedy algorithms to solve problems does not always give the optimal solution.
Let me give you an example. In a weighted graph, we start from vertex S and find the shortest path to vertex T (the path has the smallest sum of edge weights). The solution to the greedy algorithm is to select an edge with the smallest weight connected to the current vertex each time until the vertex T is found. Following this idea, the shortest path we find is S->A->E->T, and the path length is 1 + 4 + 4=9.
However, with this greedy selection method, the final path is not the shortest path, because the path S->B->D->T is the shortest path, because the length of this path is 2 + 2 + 2=6. Why doesn’t the greedy algorithm work on this problem?
In this problem, the main reason why the greedy algorithm does not work is that the previous choice will affect the subsequent choice. If we walk from vertex S to vertex A in the first step, the vertices and edges we face next are completely different from the first step from vertex S to vertex B. Therefore, even if we choose the optimal move (the shortest edge) in the first step, it is possible that because of this choice, the choices in each subsequent step will be poor, and ultimately we will miss the global optimal solution.
Practical analysis of greedy algorithm
1. Share candies
We have m candies and n children. We now want to distribute candies to these children, but there are less candies and more children (m The sizes of each candy vary, and the sizes of these m candies are s1, s2, s3,…, sm. In addition, each child’s demand for candy size is also different. Only when the size of the candy is greater than or equal to the child’s demand for candy size, the child will be satisfied. Assume that the demand for candy sizes of these n children are g1, g2, g3,…, gn respectively.
My question is, how do I distribute the candy to satisfy the greatest number of children possible?
We can abstract this problem into, from n children, select a part of the children to distribute candies, so that the number of satisfied children (expected value) is the largest. The limit value of this problem is the number of candies m.
Let’s now see how to solve it using a greedy algorithm. For a child, if small candies are enough, we don’t need to use larger candies, so that the larger ones can be reserved for other children who have greater candy size needs. On the other hand, children with small candy size needs are more likely to be satisfied, so we can start allocating candies from children with small needs. Because satisfying a child with big needs has the same contribution to our expectations as satisfying a child with small needs.
Each time, we find the one with the smallest size demand for candy among the remaining children, and then give him the smallest candy among the remaining candies that can satisfy him. The distribution plan obtained in this way means that the maximum number of children is satisfied. plan.
2. Coin change
This problem is more common in our daily life. Suppose we have banknotes of 1 yuan, 2 yuan, 5 yuan, 10 yuan, 20 yuan, 50 yuan, and 100 yuan. Their numbers are c1, c2, c5, c10, c20, c50, and c100 respectively. We now need to use this money to pay K yuan. What is the minimum number of banknotes we need to use?
In life, we must pay with the one with the largest face value first. If it is not enough, continue to use the one with a smaller face value, and so on, and finally use 1 yuan to make up the rest.
In the case of contributing the same expected value (number of banknotes), we hope to contribute more, so that the number of banknotes can be reduced. This is a solution to a greedy algorithm. Intuition tells us that this approach is the best. In fact, to rigorously prove the correctness of this greedy algorithm requires more complex and skilled mathematical derivation. I don’t recommend you spend too much time on it, but if you are interested, you can study it yourself.
3. Interval coverage
Suppose we have n intervals, and the starting and ending endpoints of the intervals are [l1, r1], [l2, r2], [l3, r3], …, [ln, rn] respectively. We select a part of the intervals from these n intervals. This part of the interval satisfies that the two intervals are disjoint (the endpoints intersect are not considered intersections). How many intervals can be selected at most?
The idea of dealing with this problem is not so easy to understand, but I suggest you better understand it, because this processing idea is used in many greedy algorithm problems, such as task scheduling, teacher scheduling, etc.
The solution to this problem is as follows: we assume that the leftmost endpoint of these n intervals is lmin and the rightmost endpoint is rmax. This problem is equivalent to selecting several disjoint intervals and covering [lmin, rmax] from left to right. We sort these n intervals in order from small to large starting endpoints.
Every time we select, the left endpoint does not coincide with the previously covered interval, and the right endpoint is as small as possible, so that the remaining uncovered interval can be made as large as possible, and more intervals can be placed. This is actually a greedy selection method.
4.Huffman coding
Suppose I have a file containing 1000 characters. Each character occupies 1 byte (1byte=8bits). It takes a total of 8000bits to store these 1000 characters. Is there a more space-saving storage method?
Suppose we find through statistical analysis that these 1000 characters contain only 6 different characters, assuming they are a, b, c, d, e, and f. 3 binary bits can represent 8 different characters. Therefore, in order to minimize storage space, we use 3 binary bits to represent each character. Then it only takes 3000 bits to store these 1000 characters, which saves a lot of space than the original storage method. However, is there a more space-saving storage method?
a(000), b(001), c(010), d(011), e(100), f(101)
Huffman coding is coming. Huffman coding is a very effective coding method and is widely used in data compression. Its compression rate is usually between 20% and 90%.
Huffman coding not only looks at how many different characters there are in the text, but also looks at the frequency of each character, and selects codes of different lengths based on the frequency. Huffman coding attempts to use this unequal length coding method to further increase the compression efficiency. How to choose codes of different lengths for characters with different frequencies? Based on greedy thinking, we can use slightly shorter codes for characters that appear more frequently; use slightly longer codes for characters that appear less frequently.
For equal-length encodings, it is very simple for us to decompress them. For example, in the example just now, we use 3 bits to represent a character. When decompressing, we read 3-digit binary codes from the text each time and translate them into corresponding characters. However, Huffman codes are not of equal length. Should 1 bit be read each time, or 2 bits, 3 bits, etc. for decompression? This problem makes Huffman coding more complicated to decompress. In order to avoid ambiguity during the decompression process, Huffman encoding requires that between the encodings of each character, there will be no situation where one encoding is the prefix of another encoding.
Assume that the frequency of these 6 characters from high to low is a, b, c, d, e, f. We encode them like this. The encoding of any character is not the prefix of another. When decompressing, we will read the decompressible binary string as long as possible every time, so we will not There will be ambiguity. After this encoding and compression, these 1000 characters only require 2100 bits.
Although the idea of Huffman coding is not difficult to understand, how to encode different characters with different lengths according to the frequency of character occurrence? The processing here is a little trickier.
We treat each character as a node and auxiliary put the frequency into a priority queue. We take out the two nodes A and B with the smallest frequency from the queue, then create a new node C, set the frequency to the sum of the frequencies of the two nodes, and use this new node C as the parent node of nodes A and B. Finally, put the C node into the priority queue. Repeat this process until there is no more data in the queue.
Now, we add a weight to each edge. We mark the edges pointing to the left child node as 0, and the edges pointing to the right child node as 1. Then the path from the root node to the leaf node is the leaf node. The Huffman encoding of the character corresponding to the node.
