发帖
雷达卡
- Reduction means transforming one problem to another. We normally reduce an unknown problem to one we know how to solve. The reduction may involve transforming both the input (so it works with the new problem) and the output (so it's valid for the original problem).
- Induction (mathematical induction) is used to show that a statement is true for a large class of objects (often the natural numbers). We do this by first showing it to be true for a base case (such as the number 1) and then showing that it "carries over" from one object to the next; for example, if it's true for n-1, then it is true for n.
- Recursion is what happens when a function calls itself.
1 Reduction example (compute the smallest differences items in an unsorted array)
without sorting, it costs n ^ 2.
with sorting, it costs nlogn
2 One, Two, Many (Induction)
P(n-1) --> P(n)
3 Mirror, Mirror (recursion)
BUT WHERE IS THE REDUCTION?
Finding a useful reduction is often a crucial step in solving an algorithmic problem. If you don’t know where to begin, ask yourself, where is the reduction?
However, it may not be entirely clear how the ideas in this section jibe with the picture of a reduction presented in Figure 4-1. As explained, a reduction transforms instances from problem A to instances of problem B and then transforms the output of B to valid output for A. But in induction and reduction, we’ve only reduced the problem size. Where is the reduction, really?
Oh, it’s there—it’s just that we’re reducing from A to A. There is some transformation going on, though. The reduction makes sure the instances we’re reducing to are smaller than the original (which is what makes the induction work), and when transforming the output, we increase the size again.
These are two major variations of reductions: reducing to a different problem and reducing to a shrunken version of the same. If you think of the subproblems as vertices and the reductions as edges, you get the subproblem graph discussed in Chapter 2, a concept I’ll revisit several times. (It’s especially important in Chapter 8.)
4 Designing with Induction (and Recursion)
Problem #1 - Finding a Maximum Permutation
Note: This is an example of what’s called a bipartite graph, which means that the nodes can be partitioned into two sets, where all the edges are between the sets (and none of them inside either). In other words, you could color the nodes using only two colors so that no neighbors had the same color.
Tip: When possible, try to use a representation that is as specific to your problem as possible. More general representations can lead to more bookkeeping and complicated code; if you use a representation that implicitly embodies some of the constraints of the problem, both finding and implementing a solution can be much easier.
#1. An early decision is always how to represent the objects in the problem instances. In this case, we might think in terms of a graph or perhaps a function that maps between the objects. However, in essence, a mapping like this is just a position (0...n–1) associated with each element (also 0...n–1), and we can implement this using a simple list. For example, the example in Figure 4-4 (if a = 0, b = 1, ...) can be represented as follows:
>>> M = [2, 2, 0, 5, 3, 5, 7, 4]
>>> M[2] # c is mapped to a
0
#2.1 Naive/Brute-force solution
#2.2 Impovements
The most wasteful operation is the repeated creation of the set B. If we could just keep track of which chairs are no longer pointed to, we could eliminate this operation entirely. One way of doing this would be to keep a count for each element. We could decrement the count for chair x when a person pointing to x is eliminated, and if x ever got a count of zero, both person and chair x would be out of the game.
There may be more than one element to be eliminated at any one time, but we can just put any new ones we come across into a “to-do” list and deal with them later. If we needed to make sure the elements were eliminated in the order in which we discover that they’re no longer useful, we would need to use a first-in, first-out queue such as the deque class (discussed in Chapter 5). We don’t really care, so we could use a set, for example, but just appending to and popping from a list will probably give us quite a bit less overhead. But feel free to experiment, of course. You can find an implementation of the iterative, linear-time version of the algorithm as following:
Problem Solving Advice
Advice for solving algorithmic problems and designing algorithms:
- Make sure you really understand the problem.
- What is the input? The output? What’s the precise relationship between the two? Try to represent the problem instances as familiar structures, such as sequences or graphs. A direct, brute-force solution can sometimes help clarify exactly what the problem is.
- What is the input? The output? What’s the precise relationship between the two? Try to represent the problem instances as familiar structures, such as sequences or graphs. A direct, brute-force solution can sometimes help clarify exactly what the problem is.
- Look for a reduction.
- Can you transform the input so it works as input for another problem that you can solve? Can you transform the resulting output so that you can use it? Can you reduce an instance of size n to an instance of size k < n and extend the recursive solution (inductive hypothesis) back to n?
- Together, these two form a powerful approach to algorithm design. I’m going to add a third item here, as well. It’s not so much a third step as something to keep in mind while working through the first two:
- Are there extra assumptions you can exploit?
- Integers in a fixed value range can be sorted more efficiently than arbitrary values. Finding the shortest path in a DAG is easier than in an arbitrary graph, and using only non-negative edge weights is often easier than arbitrary edge weights.
- Integers in a fixed value range can be sorted more efficiently than arbitrary values. Finding the shortest path in a DAG is easier than in an arbitrary graph, and using only non-negative edge weights is often easier than arbitrary edge weights.
京公网安备 11010802022788号
