Greedy Algorithm

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 AlgorithmSpecifics, Types, Applications, Examples

Other articles related to "greedy algorithm, greedy, algorithm":

Egyptian Fraction - Medieval Mathematics
... For more information on this subject, see Liber Abaci and Greedy algorithm for Egyptian fractions ... In the rare case that these other methods all fail, Fibonacci suggests a greedy algorithm for computing Egyptian fractions, in which one repeatedly chooses the unit fraction ... after the first such expansion, but he also gives examples in which this greedy expansion was iterated until a complete Egyptian fraction expansion was constructed and As ...
Malfatti Circles - Malfatti's Problem
... original Italian text, observed that for some triangles a larger area can be achieved by a greedy algorithm that inscribes a single circle of maximal radius ... triangle using their classification, they proved that the greedy algorithm always finds three area-maximizing circles, and they provided a formula for determining which ... thesis, Melissen conjectured more generally that, for any integer n, the greedy algorithm finds the area-maximizing set of n circles within a given triangle the conjecture is known to be true for ...
Greedy Algorithm For Egyptian Fractions
... In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions ... It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction ... He includes the greedy method as a last resort for situations when several simpler methods fail see Egyptian fraction for a more detailed listing of these ...
Greedy Algorithm - Examples
... The game has a demo mode, where the game uses a greedy algorithm to go to every crystal ... The Matching pursuit is an example of greedy algorithm applied on signal approximation ... A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles it is conjectured that the same greedy algorithm ...
Partition Problem - Approximation Algorithm Approaches - The Greedy Algorithm
... the way children choose teams for a game, is the greedy algorithm, which iterates through the numbers in descending order, assigning each of them to whichever ... of a set upon which this heuristic "breaks" is S = {5, 5, 4, 3, 3} For the above input, the greedy approach would build sets S1 = {5, 4} and S2 = {5, 3, 3} which are ... This greedy approach is known to give a 4/3-approximation to the optimal solution of the optimization version (if the greedy algorithm gives two sets, then ) ...

Famous quotes containing the word greedy:

    Don’t make your enemies happy.
    Make up with your lover,
    who’s greedy to be back
    in your good graces.
    because you’ve taken anger to extremes,
    you won’t amount
    to a hill of beans.
    Hla Stavhana (c. 50 A.D.)