A step-by-step method is used in a grepite algorithm (Greedy Method). At each stage, a decision that looks optimal (under certain standards). Once the decision makes it, it is no longer possible. The basis of greed decisions is called greedy criterion.
Example 1-4 [Looking for a change] A child bought a sugar worth less than $ 1, and handed a $ 1 money to the salesman. The salesperson hopes to use the least amount of coins to find the child. Suppose it provides an unlimited face value of 2 5 cents, 1,0 cents, 5 cents, and 1 cents. The salesperson is divided into the number of changes to find, and each time you join a coin. The greedy standards used when choosing coins are as follows: Each choice should increase the number of changes to the number of changes. In order to ensure the feasibility of the solution (ie: the change given is equal to the number of change to be found), the selected coin should not make the total number of change in the total number of changes.
Suppose you need to find a child 6 7 cents, first selected two 2 5 cents coins, the third entrance is selected from 2 5 cents, otherwise the choice of coins will not be feasible (the total number of zero is more than 6 7 Universal), the third should choose 1 0 cents, then 5 cents, and finally join two 1 cents.
The greedy algorithm has intuitive tendencies. When you find a change, Intuitive tells us that the number of coins that should be found (at least close to the minimum). It can be proved that the number of coins used when using the above greedy algorithm to find changes (see Exercise 1).
Example 1-5 [Machine Scheduling] There is an existing N task and an unlimited number of machines, and the task can be processed on the machine. The start time of each task is Si, the completion time is Fi, Si If there is N = 7 tasks, the labels are A to G. Their start and completion time is shown in Figure 13-1A. If task A is distributed to the machine M1, the task B is distributed to the machine M2 ,................................... But it is not optimal allocation, because there are other allocation schemes to make the number of machines that can be used, for example, you can assign tasks A, B, and D to the same machine, then the number of machines is reduced to five. A greedy method for obtaining optimal allocation is to gradually allocate tasks. Each step is assigned a task, and allocated in a non-delivery time in the task start time. If there is at least one task assigned to a machine, it is said that this machine is old; if the machine is not old, it is new. When choosing a machine, use the following greedy guidelines: Based on the start time of the task, if there is an old machine available, the task is given to the old machine. Otherwise, assign tasks to a new machine. According to the data in the example, the greedy algorithm is divided into n = 7 steps, the order in which the task assignment is A, F, B, C, G, E, D. The first step is not an old machine, thus assigns a new machine (such as M1). This machine is in a busy state at 0 to 2. In the second step, consider the task f. Since the old machine is still busy when F is started, the F is allocated to a new machine (set to M2). Third step considering the task B, since the old machine M1 is already in the idle state at SB = 3, the B is allocated to M1, and the next time the next time the next time it becomes FB = 7, the available time of M2 becomes FF = 5. Step 4, consider the task C. Since there is no old machine available at SC = 4, C is allocated to a new machine (M3), and the next time available for this machine is Fc = 7. Step 5 Consider the task G, assign it to the machine M2, and the sixth step is assigned to the machine M1, and finally in the seventh step, task 2 is assigned to the machine M3. (Note: Task D can also be assigned to machine M2). The above greedy algorithm can lead to a proof of the optimal machine allocation to leave the exercise (Exercise 7). A greedy algorithm for complexity O (NL O GN) can be implemented as follows: first use a sorting algorithm of O (NL O GN) (such as a heap sort) to arrange each task in the increment order of Si, then use A minimum pile of available time for older machines. Example 1-6 [Shortest Path] gives a communication network, the length of the path is defined as the sum of the times the path passed by the path. Require a shortest path from the initial vertex S to the purpose of the target. The greedy algorithm constructs this path step by step, and each step is added to a vertex. Suppose the current path has reached the vertices q, And the vertex q is not a destination vertex d. The greedy criterion used to join the next vertex is to select the vertices nearest from Q and are not currently not in the path. This greedy algorithm does not necessarily obtain the shortest path. For example, it is assumed that the shortest path from the vertices 1 to the vertex 5 is desired in Fig. 1 3 - 2, and the above greedi algorithm is used to start and look for the most recent vertices of the top point 1 in the path. Arrived at the vertices 3, the length of only 2 units, the most recent vertex that can be reached from the vertex 3 is 4, from the vertex 4 to the vertices 2, and finally reach the target vertex 5. The established path is 1, 3, 4, 2, 5, and its length is 1 zero. This path is not a shortest path from 1 to 5 in the figure. In fact, there are several shorter paths, such as the length of paths 1, 4, 5. According to the three examples above, recall some of the applications inspected in the previous chapters, and several algorithms are also greedy algorithms. For example, the Hoffmann algorithm uses N-1 step to establish a binary tree of the smallest weight external path. Each step is merged into one, and the greed guidelines used in the algorithm are: elected from the available binary tree. Two of the smallest weight. L P T scheduling rules are also a greedy algorithm that uses N step to schedule N jobs. First, the job will be sorted by time, and then assign a machine to a task in each step. Select the greedy criteria used by the machine: the shortest scheduling time. Scandard the new job to the first machine (that is, the first idle machine). Note that in the machine scheduling problem, the greedy algorithm does not guarantee optimal, however, that is a intuitive tendency and generally the result is always very close to the optimal value. The rules it use is the rules used in the actual environment to scheduling. The algorithm does not guarantee the optimal results, but the result of the usual result is not much different from the optimal solution, which is also referred to as a heuristic method (HE e U R I S I c s). Therefore, the L P T method is a heuristic machine scheduling method. Theorem 9 - 2 states the relationship between the completion time of the L P T scheduling and the completion time of the optimal scheduling, so the L P T heuristic method has a definitive performance (Bounded Performance). The heuristic method having limited performance is called an approximate algorithm (A P P R O X I m a T I O Na L G O R I T H m). The rest of this chapter will introduce several greedy algorithms. In some applications, the results produced by the greedy algorithm are always the best solution. But for other applications, the generated algorithm is just a heuristic method, which may not be an approximate algorithm. Reprinted from Shada Studio
