While designing a good solution algorithm is more art, unlike technology, there are still some operational algorithm design methods that can be used to solve many problems, you can use these methods to design algorithms, and observe How these algorithms work. In general, in order to achieve better performance, the algorithm must be meticulous. However, in some cases, the performance cannot achieve requirements after adjustment, and there must be additional methods to solve the problem.
This chapter first introduces the optimization concept, then introduces an intuitive problem solving method: greedy algorithm. Finally, the algorithm is applied to the discharge box, backpack problem, topology sorting problem, two-point coverage, shortest path problem, minimum price spike, etc.
1.1 optimization problem
Many examples in this chapter and subsequent chapters are Optimization Problem. Each optimization problem contains a set of restrictions and an optimization function (Optimization function), the problem solving solution in line with restrictions is called FeaSible Solution, enables the optimal function to achieve the optimal value of optimal sol. Example 1-1 [thirsty baby problem] There is a very thirsty, smart little baby, she may get something including a glass of water, a bucket of milk, multi-kind, many different kinds of different packs or jars Soda, that is, baby can get n different drinks. According to the previous experience of this N kinds of beverages, this baby knows that some of this drink is more comfortable, so the baby takes the following method to give each kind of satisfaction value: drink 1 ounce Group I drink, Relative evaluation is made, a value Si is given to the i kind of beverage as satisfaction. Typically, this baby will try to maximize the need for the best satisfaction value to maximize her quenching needs, but unfortunately: the beverage with the biggest satisfaction value sometimes does not have enough quantity to meet the needs of this baby. It is the total amount of the i kind of beverage (in an ounce), and this baby needs T ounces to quench, then how many different drinks need to meet the needs of infants? It is known to be satisfactory for various beverages. Let XI will be the amount of the i kind of beverage that the baby will drink, the problem that needs to be solved is: Find a set of real numbers (1 ≤ i ≤ N), make N? I = 1si xi largest, and satisfy: n? I = 1Xi = T and 0 ≤ xi ≤ As. It should be pointed out that if n? I = 1ai In this question, the restriction condition is n? I = 1 xi = T and 0 ≤ xi ≤ Ai, 1 ≤ i ≤ N. The optimization function is n? I = 1si xi. Any set of real numbers that meet the limit conditions are feasible, but make N? I = 1si Xi maximum feasible solution is the optimal solution. Example 1-2 [Loading Problem] There is a big ship ready to load the cargo. All storage goods are installed in the container and the size of all containers is the same, but the weight of the cargo box is different. It is set to the weight of the i-i (1 ≤ i ≤ N), while the maximum load capacity of the cargo ship is C, our purpose is to load the most cargo on the cargo ship. This problem can be described as an optimization problem: set there is a set of variables Xi, which may be 0 or 1. Such as xi is 0, then the container I will not be loaded with the ship; such as 1, the container I will be installed. Our goal is to find a set of Xi, which satisfies the limit condition N? I = 1wi xi ≤c and x i? {0, 1}, 1 ≤ i ≤ n. The corresponding optimization function is n? I = 1xi. Each set of XIs satisfying the restrictions is a canken, which makes the maximum value of n? I = 1xi to get the maximum value. Example 1-3 [Minimum Cost Communication Network] All possible communication connections between urban and cities can be considered a no-shaped figure, each side of the figure is given a weight, and the weight represents the completion of this edge. The consideration of the communication connection to be paid. Contains the connection sub-map of all vertices (cities) in the figure is a canken. All weight is not negative, then all possible verative solutions can represent a group of generated trees that are not mapped, and the optimal solution is a generating tree having the minimum cost. In this question, you need to select a subset of the border set in the figure, which must meet the following restrictions: all edges constitute a spanning tree. The optimization function is the sum of the weights of all the edges in the subset. Reprinted from Shada Studio
