Greedy algorithm | greedy | Algorithm

Greedy algorithm

Greedy algorithm always makes the choice that look better at a brief period of time. i.e., it form a locally optimal choice in the hope that this choice will lead to globally optimal solution.

 The procedure is powerful and work in a good for wide range of problem.
An optimal problem is one in which you want to search, not only solution of problem, but better solution of a problem. Greedy algorithms works better for optimization problems.

A greedy algorithm works in different phases.
At each different phase:

You desire the better you can obtain right now, without consider for future result or effect.

You desire that by selecting a local optimum at every step, you will end up at global optimum.
Example: 

Suppose you want to count out a certain value of money, using the few possible bills and coins. A greedy algorithm would do this in the following steps:

To make $6.39, you can choice following coins

$5 bill
$1 bill to make $6
$25c coin, to make $6.25
10c coins to make $6.35
Four 1c coins to make $6.39

For US money the greedy algorithm always give the optimum solution.

Greedy algoritm

1. Huffman encoding
2.  Minimum spanning tree
3.  Kruskal’s algorithm
4. Prim’s algorithm