A greedy algorithm is an algorithm that follows 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.
For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps. In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.
Read more about Greedy Algorithm: Specifics, Types, Applications, Examples
Famous quotes containing the word greedy:
“Im a very smart guy. I havent a feeling or a scruple in the world. All I have the itch for is money. I am so money greedy that for twenty-five bucks a day and expenses, mostly gasoline and whisky, I do my thinking myself, what there is of it; I risk my whole future, the hatred of the cops ... I dodge bullets and eat saps, and say thank you very much, if you have any more trouble, I hope youll think of me, Ill just leave one of my cards in case anything comes up.”
—Raymond Chandler (18881959)