How to Reverse Greedy Algorithms
Reverse greedy algorithms – also known as Rgreedy algorithms – are not the “reverse” of greedy algorithms. They are also greedy algorithms, but they work in the reverse direction. Usually a Rgreedy algorithm solves a problem in the opposite direction or uses an opposite solution than the classical greedy algorithm solution. A greedy algorithm is one that takes what looks like the most advantageous step at every point in a process. Greedy algorithms do not always work, but they are almost always the simplest way to write an algorithm.
Other People Are Reading
Instructions
-
-
1
Start with the greedy algorithm. If there is no standard greedy algorithm solution for a problem, the problem of finding the reverse algorithm is moot. You cannot find the reverse of the typical way of doing something if there is no typical way. A good example of a greedy algorithm is the “minimum spanning tree of a graph” problem. A graph is a set of points connected by lines where the lines are labeled with numbers. The minimum spanning tree is a connected set of lines that connects all the points.
-
2
Look for the procedure in the greedy algorithm that can be reversed. Typically it will be the process that controls the algorithm; the process that, when exhausted, causes the algorithm to stop. The classic greedy algorithm for finding the minimal spanning tree is to start with the points and no connecting lines. At each step, add the smallest line between any two points. Continue the process until all the points are connected.
-
-
3
Find something to reverse if you want to build a Rgreedy algorithm. The Rgreedy algorithm for finding the minimum spanning tree starts with the map and all the lines. At each step, remove the line with the largest label that will leave the points connected. Continue this process until no more lines can be removed.
-
4
Check the Rgreedy algorithm to make sure it solves the problem. It is not really an algorithm if it does not solve the problem. Sometimes reversing a controlling process may introduce a situation where the algorithm does not address all elements of the problem or does not terminate the algorithm correctly. .
-
1
Tips & Warnings
In the minimum spanning tree problem, if the points are cities, the labels might be the distances between the cities. If the points represent substations of a cable company, the labels might be the cost of laying a cable between two substations. The minimal spanning tree is a set of lines that are connected to each other and that connect all the points. Both algorithms are greedy, but the greedy algorithm adds lines and the Rgreedy algorithm subtracts lines.
Not all greedy algorithms have a Rgreedy counterpoint. Even if it does, there is no reason to suspect that it will work better than the greedy algorithm. Some problems are not solvable by greedy algorithms. For example, solving the Rubik’s cube with a greedy algorithm that always chooses the move that increases the numbers of correct colors -- or decreases the number of incorrect colors -- is doomed to fail. Some problems require more global solutions.
References
Resources
- Photo Credit Comstock/Comstock/Getty Images
