A greedy algorithm grabs data items in sequence, each time taking the one that is deemed best according to some
criterion, without regard for the choices it has made before or will make in the future. Algorithms of this kind often
lead to very efficient and simple solution.
Like dynamic programming, greedy algorithms are often used to solve optimization problems. However, the greedy approach
is more straightforward. A greedy algorithms arrives at a solution by making a sequence of choices, each of which simply looks
better at the moment. That is, each choice is locally optimal. The hope is that a globally optimal solution will be obtained,
but this is not always the case. For a given algorithm, we must determine whether the solution is always optimal.
Change problem.
Problem: provide a correct change giving as few coins as possible.
Greedy algorithm
The amount of change to give:
Number of quarters:
Number of dimes:
Number of nickels:
Number of pennies:
Total change given
Just to understand why the greedy approach doesn't always produce the globally optimal solution, pretend that there is
a 12-cent coin. If there is such a coin and we are to give 16 cents as change, then the greedy algorithm will give us
12 + 1 + 1 + 1 + 1, which is 5 coins, as well as the optimal solution contains only 3 coins (find the optimal solution).
Shortest Path Problem. Dijkstra's algorithm.
To illustrate the greedy technology one more time, we will apply the idea to the same
shortest path problem we solved using the Floyd algorithm. The dynamic method
we used last time produced an algorithm that gives us the shortest ways from each vertex to all other vertices. If we want
to know only the shortest path from one particular vertex to all the others, that algorithm would be performing too
much extra job. We will use the greedy approach to design another algorithm to do exactly this. This algorithm is due to
Dijkstra.
To explain the algorithm we will use the following notations:
N - the set of vertices whose shortest path from the given vertex has been determined;
D - the one dimensional array of distances between the given vertex and all other vertices of the graph.
Then we can describe the algorithm as
Initialization
We initialize the set N to contain source vertex. (Let's say this vertex is A.)
We initialize D(A) as zero, and D(v) as infinity for any other vertex v
of the graph.
Iterations: repeat until the instance is solved
First, we choose the vertex v from the set of vertices which are not in N,
that has the shortest path from A, using only the vertices in N as intermediate
add this vertex to the set N
update the set of distances D. We need to update the known minimal distances from the source
vertex A to all other vertices, which are not yet in the set N. These new distances are either
(whichever is less) the old known cost or the sum of the cost from A to the just added vertex and the weight
of the edge from the new vertex to the vertex whose distance is being updated
if the set N is equal to the set of all graph vertices, the instance is solved.
Because Dijkstra's algorithm always chooses the closest vertex in the set V-N (where V is
the set of all vertices), we say that it uses a greedy approach.
The following sequence of pictures illustrates the algorithm applied to a 5-vertex graph:
5-vertex graph
To implement the algorithm we will declare the following variables:
Wi,j - link cost from node i to node j. If nodes i and j
are not directly connected, then c(i,j)=¥.
D(v) - cost of the path from the source node to destination v that has currently (as the
iteration of the algorithm) the least cost.
P(v) - previous node (neighbor of v) along the current least-cost path from the source to
v.
N - set of nodes whose lest-cost path from the source is definitely known.
The algorithm goes as follows:
Initialization:
N = {A}
for all nodes vifv adjacent to A
thenD(v) = W(A, v)
elseD(v) = ¥
Loop
find w not in N such that D(w) is a minimum
add w to Nforv adjacent to w and not in N update D(v):
D(v) = min{ D(v), D(w)+W(w, v) }
/* new cost to v is either the old cost or known shortest path cost to w plus cost from w to v */
until all nodes in N
The following page illustrates how this algorithm works. This page also shows how to keep
track of the shortest paths, not only the smallest distances.
