Read · 1 min
A greedy algorithm, or greedy strategy is used to solve problems relating to the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.( in polynomial time)
For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity, ) is this idea: "At each stage visit an unvisited city nearest to the current city". This idea need not find a best solution, but finishes in a reasonable number of steps; finding an optimal solution normally needs way too many steps. To find the actual optimum route, the most primitive strategy is to just try all possible connections and find the best one. To get a solution that is close to the optimum, a greedy algorithm might be the solution. Even if it isn't, then it can't hurt as it takes millionths of a second for a computer to find a greedy algorithm!
Wikipedia user Swfung8 made this GIF that really helps show what a greedy algorithm is.
When optimizing stuff, combinatorial problems like The Travelling Salesman Problem have a greedy algorithm if the combinatorial game in question has the properties of matroids. The Kruskal algorithm is a greedy strategy and it is optimal.