Greedy Algorithms
A
greedy algorithm always makes the choice that looks best at the
moment. That is, it makes a locally optimal choice in the hope that this choice
will lead to a globally optimal solution.
Greedy
algorithms do not always yield optimal solutions, but for many problems they
do. The greedy method is quite powerful and works well for a wide range of
problems.
Greedy is an algorithmic paradigm that builds up a solution piece by
piece, always choosing the next piece that offers the most obvious and
immediate benefit. Greedy algorithms are used for optimization problems.
An
optimization problem can be solved using Greedy if the problem has the
following property: At every step, we can
make a choice that looks best at the moment, and we get the optimal solution of
the complete problem.
If a Greedy Algorithm can solve a problem, then
it generally becomes the best method to solve that problem as the Greedy
algorithms are in general more efficient than other techniques like Dynamic
Programming. But Greedy algorithms cannot always be applied.
Elements of the greedy strategy
Greedy
algorithms are designed according to the following sequence of steps:
1.
Cast the optimization problem as one in which we make a choice and are left with
one sub problem to solve.
2.
Prove that there is always an optimal solution to the original problem that
makes the greedy choice, so that the greedy choice is always safe.
3.
Demonstrate optimal substructure by showing that, having made the greedy
choice, what remains is a sub problem with the property that if we combine an optimal
solution to the sub problem with the greedy choice we have made, we arrive at an
optimal solution to the original problem.
Elements
of the greedy strategy are
2. Optimal
substructure
1) Greedy-choice property: A globally optimal solution can be arrived at by
making a locally optimal (greedy) choice. Here is where greedy algorithms
differ from dynamic programming. In dynamic programming, we make a choice at
each step, but the choice may depend on the solutions to sub problems. In a
greedy algorithm, we make whatever choice seems best at the moment and then
solve the sub problems arising after the choice is made.
2) Optimal substructure: If an optimal
solution to the problem contains within it optimal solutions to sub problems
0 comments:
Post a Comment