“Greedy” technique

What is it?

a simple algorithm, looking for the best (“greedy”) choice from the available alternatives

hoping that series of local optimal choices leads to a global optimal solution to big problem

used to solve optimisation problems

choice on each step should be:

• feasible
• local optimal
• irrevocable

disadvantage: does not operate exhaustively on all data, thus often fails to find globally optimal solution

Algorithms

• Dijkstra’s algorithm
• Prim’s algorithm
• Kruskal’s Algorithm