发帖
雷达卡
#2 of three algorithm design strategies - greedy algorithms
So-called greedy algorithms are short-sighted, in that they make each choice in isolation, doing what looks good right here, right now. In many ways, eager or impatient might be better names for them because other algorithms also usually try to find an answer that is as good as possible; it’s just that the greedy ones take what they can get at this moment, not worrying about the future. Designing and implementing a greedy algorithm is usually easy, and when they work, they tend to be highly efficient. The main problem is showing that they do work.
1 Staying Safe, Step by Step
The common setting for greedy algorithms is a series of choices (just like, as you’ll see, for dynamic programming). The greed involves making each choice with local information, doing what looks most promising without regard for context or future consequences, and then, once the choice has been made, never looking back. If this is to lead to a solution, we must make sure that each choice is safe - that it doesn’t destroy our future prospects. You’ll see many examples of how we can ensure this kind of safety (or, rather, how we can prove that an algorithm is safe), but let’s start out by looking at the “step by step” part.
The kind of problems solved with greedy algorithms typically build a solution gradually. It has a set of “solution pieces” that can be combined into partial, and eventually complete, solutions. These pieces can fit together in complex ways; there may be many ways of combining them, and some pieces may no longer fit once we’ve used certain others. You can think of this as a jigsaw puzzle with many possible solutions (see Figure 7-1). The jigsaw picture is blank, and the puzzle pieces are rather regular, so they can be used in several locations and combinations.
2. Algorithm Examples:
- The Knapsack Problem
- Huffman’s Algorithm
- Minimum Spanning Trees
3. Greed Works. But When?
Although induction is generally used to show that a greedy algorithm is correct, there are some extra “tricks” that can be employed.
#1. Keeping Up with the Best
#2. No Worse Than Perfect
#3. Staying Safe
Summary
Greedy algorithms are characterized by how they make decisions. In building a solution, step-by-step, each added element is the one that looks best at the moment it’s added, without concern for what went before or what will happen later. Such algorithms can often be quite simple to design and implement, but showing that they are correct (that is, optimal) is often challenging. In general, you need to show that making a greedy choice is safe - that if the solution you had was promising, that is, it could be extended to an optimal one, then the one after the greedy choice is also promising. The general principles, as always, is that of induction, though there are a couple of more specialized ideas that can be useful. For example, if you can show that a hypothetical optimal solution can be modified to become the greedy solution without loss of quality, then the greedy solution is optimal. Or, if you can show that during the solution building process, the greedy partial solutions in some sense keep up with a hypothetical optimal sequence of solutions, all the way to the final solution, you can (with a little care) use that to show optimality.
Important greedy problems and algorithms discussed in this chapter include the knapsack problem (selecting a weight-bounded subset of items with maximum value), where the fractional version can be solved greedily; Huffman trees, which can be used to create optimal prefix codes and are built greedily by combining the smallest trees in the partial solution; and minimum spanning trees, which can be built using Kruskal’s algorithm (keep adding the smallest valid edge) or Prim’s algorithm (keep connecting the node that is closest to your tree).
京公网安备 11010802022788号
