[go: up one dir, main page]
Scribd
Upload
75 views6 pages

Lecture 25 - Greedy Algorithms

This document discusses greedy algorithms and optimization problems. It begins by defining optimization problems as problems that find the best solution among many possible solutions by minimizing or maximizing cost, subject to constraints. It then explains that greedy algorithms work by making locally optimal choices at each step in the hope of reaching a global optimum. The key properties a problem must have for a greedy algorithm to work are the greedy choice property, where a locally optimal choice can lead to a globally optimal solution, and optimal substructure, where optimal solutions to subproblems make up the optimal solution to the overall problem.

Uploaded by

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

Lecture 25 - Greedy Algorithms

This document discusses greedy algorithms and optimization problems. It begins by defining optimization problems as problems that find the best solution among many possible solutions by minimizing or maximizing cost, subject to constraints. It then explains that greedy algorithms work by making locally optimal choices at each step in the hope of reaching a global optimum. The key properties a problem must have for a greedy algorithm to work are the greedy choice property, where a locally optimal choice can lead to a globally optimal solution, and optimal substructure, where optimal solutions to subproblems make up the optimal solution to the overall problem.

Uploaded by

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

Greedy Algorithms

Instructor: Dr. Zuhair Zafar

CS 854 Advanced Algorithm Analysis

Lecture # 25
Optimization Problems
⚫ Some problems can have many possible/ feasible
solutions with each solution having a specific cost. We
wish to find the best solution with the optimal cost.
⚫ Maximization problem finds a solution with
maximum cost
⚫ Minimization problem finds a solution with
minimum cost

⚫ A set of choices must be made in order to arrive at an


optimal (min/max) solution, subject to some constraints.

⚫ Is “Sorting a sequence of numbers” optimization problem?2


Optimization Problems
⚫ Two common techniques:
⚫ Greedy Algorithms (local)
⚫ Make the greedy choice and THEN

⚫ Solve sub-problem arising after the choice is made

⚫ The choice we make may depend on previous


choices, but not on solutions to sub-problems
⚫ Top down solution, problems decrease in size

⚫ Dynamic Programming (global)


⚫ We make a choice at each step

⚫ The choice depends on solutions to sub-problems

⚫ Bottom up solution, smaller to larger sub-problems 3


Greedy Algorithm
⚫ A greedy algorithm works in phases. At each phase:
⚫ makes the best choice available right now, without regard
for future consequences
⚫ hopes to end up at a global optimum by choosing a local
optimum at each step. For some problem, it works

⚫ Greedy algorithms sometimes works well for


optimization problems
⚫ Greedy algorithms tend to be easier to code
⚫ Greedy algorithms frequently used in everyday
problem solving
⚫ Choosing a job
⚫ Route finding
⚫ Playing cards 4

⚫ Invest on stocks
Greedy Algorithm
⚫ How to know if a greedy algorithm will solve a
particular optimization problem?
⚫ Two key ingredients
⚫ Greedy choice property
⚫ Optimal sub-structure

⚫ If a problem has these properties, then we


can develop a greedy algorithm for it.

5
Greedy Algorithm
⚫ Greedy choice property: A globally optimal solution can
be arrived at by making a locally optimal (greedy) choice
⚫ Make whatever choice seems best at the moment and then solve
the sub-problem arising after the choice is made
⚫ The choice made by a greedy algorithm may depend on choices
so far, but it cannot depend on any future choices or on the
solutions to sub-problems

⚫ Optimal sub-structure: A problem exhibits optimal


substructure if an optimal solution to the problem
contains within it optimal solutions to sub-problems

You might also like