Greedy Algorithms
A greedy algorithm (like a normal algorithm) is a rule or process that provides a solution to a problem. But a greedy algorithm is not an algorithm proper--it is a heuristic, it works in stages, making a series of short-term decisions that will be the best possible at the present time, without regard for what might happen in the future. In essence a greedy algorithm takes a series of immediate, local optimums in the hope that, when the process terminates, it has achieved a global optimum as well.
Making change is one example of a greedy algorithm since one generally wants to use the smallest number of coins possible. If one is asked for 74 cents and the coins on hand have values of 25, 10, 5 and 1 cents, the person receiving the change would get two 25 cent pieces, then two 10 cent pieces, and finally four 1 cent pieces. Any other combination would give the person a larger number of coins and be a less efficient process.
The process of creating a minimal spanning tree for any set of connected vertices can be done by employing Kruskal's algorithm. This greedy algorithm works as follows: First, sort the edges from shortest (or least expensive) to longest, then add edges to the spanning tree one by one, starting with the shortest edge. If an edge would create a cycle, or loop, discard that edge from the tree and proceed to the next edge. Once all of the edges have been added or discarded, the vertices will be connected by the shortest (or cheapest) set of edges possible.
A computer network can use greedy algorithms to process the messages and files that it sends between nodes in its network. Each edge that connects two nodes can be given a "weight" to represent the time it takes for a message to travel from one node to another. This weight can take into account the distance traveled, the composition of the material traveled through (fiber optic cable, copper wire, etc.), the speed of the processor on the receiving end, the time of day, and any other factor that affects the transmission speed. The different paths of edges connecting any two nodes can then be compared to determine which path is the shortest.
Greedy algorithms sometimes fail due their short-term outlook. If, in the money-changing example above, the coin pool also included an 8 cent coin, the greedy algorithm would still give the person the same set of coins, even though a more efficient solution exists, that is, two 25 cent pieces and three 8 cent pieces.
Even when a greedy algorithm fails to provide the best solution to a problem, it usually provides a good estimate of what the actual solution is. Such is the case with the traveling salesman problem, in which a salesman tries to visit a certain number of cities without repetition while traveling the least possible distance. The only algorithms known for this problem are exponential; the time required to find a solution increases by a factor of 2 for each city added to the salesman's route. A variation of Kruskal's algorithm--one which adds the shortest edge possible that doesn't create a vertex of degree three and that doesn't complete a cycle unless the number of edges equals the number of vertices--gives a reasonably good solution to this problem while taking much less time than the "real" algorithm.
Before using a greedy algorithm, one should determine how far answers derived with it deviate from answers produced by an actual algorithm.
This is the complete article, containing 587 words
(approx. 2 pages at 300 words per page).
