[go: up one dir, main page]
Scribd
Upload
46 views4 pages

Greedy Algorithms

Greedy algorithms attempt to find an optimal solution to a problem by making locally optimal choices at each step to optimize an objective function. They work by starting with a well-understood initial configuration and iteratively selecting the choice that best improves the objective, resulting in a sequence of optimal choices. To apply greedy algorithms successfully, the problem must exhibit optimal substructure and the greedy-choice property.

Uploaded by

r232994b
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
46 views4 pages

Greedy Algorithms

Greedy algorithms attempt to find an optimal solution to a problem by making locally optimal choices at each step to optimize an objective function. They work by starting with a well-understood initial configuration and iteratively selecting the choice that best improves the objective, resulting in a sequence of optimal choices. To apply greedy algorithms successfully, the problem must exhibit optimal substructure and the greedy-choice property.

Uploaded by

r232994b
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Greedy algorithms

Introduction
 This algorithm design paradigm involves repeatedly making choices that optimize some
objective function,
 The greedy method is applied to optimization problems—that is, problems that involve
searching through a set of configurations to find one that minimizes or maximizes an
objective function defined on these configurations.
 in order to solve a given optimization problem, we proceed by a sequence of choices.
 The sequence of choices starts from some well-understood starting configuration, and then
iteratively makes the decision that is best from all of those that are currently possible, in
terms of improving the objective function
 greedy-choice property - the property that a global optimal
configuration can be reached by a series of locally optimal choices
 Optimal choices- choices that are the best from among the possibilities available at the
time , starting from a well-defined configuration.
 Optimal substructure -A problem exhibits optimal substructure if an optimal solution to
the problem contains within it optimal solutions to subproblems.

You might also like