[go: up one dir, main page]
Scribd
Upload
7 views77 pages

Greedy Approach

Uploaded by

M.Micheal Berdinanth
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
7 views77 pages

Greedy Approach

Uploaded by

M.Micheal Berdinanth
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/ 77

Greedy Algorithms

V. Balasubramanian
SSN College of Engineering
Introduction
• Charles Dickens’ - Ebenezer Scrooge
greedy person ever, fictional or real.
• Each day his only drive was to
greedily grab as much gold as he
could.
• Christmas Carol
Contd…
• They often lead to very efficient and
simple solutions.
• Like dynamic programming, greedy
algorithms are often used to solve
optimization problems.
• The greedy approach is more
straightforward.
• DP, a recursive property is used to
divide an instance into smaller
instances.
Contd…
• In the greedy approach, there is no
division into smaller instances. A
greedy algorithm arrives at a
solution by making a sequence of
choices, each of which simply looks
the best at the moment. That is,
each choice is locally optimal. The
hope is that a globally optimal
solution will be obtained, but this is
not always the case.
Greedy Stratergy
Example
• penny, nickel, dime, quarter, half
dollar
• D1 = 25 (quarter), d2= 10 (dime),
• d3= 5 (nickel), and d4= 1 (penny).
• Change for 36,48
Example
• dime, nickel, and penny and 12 paise
coin
• Change for 16
• Example:
Example
• Coins 1,3,4
• Change for 6.
Approach
• A selection procedure chooses the next item to
add to the set. The selection is performed
according to a greedy criterion that satisfies
some locally optimal consideration at the time.
• • A feasibility check determines if the new set
is feasible by checking whether it is possible to
complete this set in such a way as to give a
solution to the instance.
• • A solution check determines whether the new
set constitutes a solution to the instance.
Greedy Technique
• Constructs a solution to an optimization problem
piece by piece through a sequence of choices that
are:

• feasible
• locally optimal
• irrevocable
• For some problems, yields an optimal solution for
every instance.
• For most, does not but can be useful for fast
approximations.
Applications
• Optimal solutions:
– change making for “normal” coin
denominations
– minimum spanning tree (MST)
– single-source shortest paths
– simple scheduling problems
– Huffman codes
Coin Change Problem
Given unlimited amounts of coins of denominations d1 > … >
dm ,
give change for amount n with the least number of coins

Example: d1 = 25c, d2 =10c, d3 = 5c, d4 = 1c and n = 48c

Greedy solution:

Greedy solution is
• optimal for any amount and “normal’’ set of denominations
• may not be optimal for arbitrary coin denominations
Minimum Spanning Tree (MST)
• Spanning tree of a connected graph
G: a connected acyclic subgraph of G
that includes all of G’s vertices

• Minimum spanning tree of a


weighted, connected graph G: a
spanning tree of G of minimum total
weight
Example
Prims Algorithm
• Suppose an urban planner wants to
connect certain cities with roads so
that it is possible for someone to
drive from any city to any other city.
• Budgetary Constraint
• Robert Clay Prim (born September 25,
1921in Sweetwater, Texas) is an American
mathematician and computer scientist.
• Robert Prim along with coworker Joseph
Kruskal
• Prim's algorithm, was originally
discovered in 1930 by
Czechmathematician Vojtěch Jarník and
later independently by Prim in 1957.
Problem
Assumption
No cycles
Greedy Algorithm
Prims Algorithm
Algorithm
Prims Algorithm
Algorithm
• Start with tree T1 consisting of one (any) vertex
and “grow” tree one vertex at a time to produce
MST through a series of expanding subtrees T1,
T2, …, Tn

• On each iteration, construct Ti+1 from Ti by


adding vertex not in Ti that is closest to those
already in Ti (this is a “greedy” step!)

• Stop when all vertices are included


Example
Proof of Correctness
• Mathematical Induction
Correctness
• Roughly how many cuts does a graph
with n vertices have?
• 2n-2
Contd…
• PQRS
• 0000 A : { P,Q,R,S } B : {} // ignore, B is empty
• 0001 A : { P,Q,R } B : { S }
• 0010 A : { P,Q,S } B : { R }
• 0011 A : { P,Q } B : { R,S }
• 0100 A : { P,R,S } B : { Q }
• 0101 A : { P,R } B : { Q,S }
• 0110 A : { P,S } B : { Q,R }
• 0111 A : { P } B : { Q,R,S }
• 1000 A : { Q,R,S } B : { P }
• 1001 A : { Q,R }, B : { P,S }
• 1010 A : { Q,S } B : { P,R }
• 1011 A : { Q } B : { P,R,S }
• 1100 A : { R,S } B : { P,Q }
• 1101 A : { R } B : { P,Q,S }
• 1110 A : { S } B : { P,Q,R }
• 1111 A : {} B : { P,Q,R,S } // ignore, A empty
Empty Cut Lemma
Lemma 2
Proof contd…
Analysis
Contd…
• Proof by induction that this construction actually
yields MST
• Needs priority queue for locating closest fringe
vertex
Efficiency
• O(n2) for weight matrix representation of graph
and array implementation of priority queue
• O(m log n) for adjacency list representation of
graph with n vertices and m edges and min-heap
implementation of priority queue
Exercise
2,10,1
When v is added to X
Kruskal’s Algorithm
• Sort the edges in nondecreasing order of
lengths

• “Grow” tree one edge at a time to produce


MST through a series of expanding forests
F1, F2, …, Fn-1

• On each iteration, add the next edge on


the sorted list unless this would create a
cycle. (If it would, skip the edge.)
Slide 9- 51
Union, find
Complexity analysis
• Sorting the edges mlogm – merge
sort
• Disjoint set:
• O(n) – to initialise disjoint data set
• O(mlog m) – find,equal, merge
Example
Exercise
• Does Kruskal’s algorithm work
correctly on graphs that have
negative edge weights?
Dijkstras Assumption
• Edsger W. Dijkstra (1930–2002), a noted Dutch
pioneer of the science and industry of computing,
discovered this algorithm in the mid-1950s.
Dijkstra said about his algorithm: “This was the
first graph problem I ever posed myself and
solved. The amazing thing was that I didn’t
publish it. It was not amazing at the time. At the
time, algorithms were hardly considered a
scientific topic.”
• Turing award -1972
Assumption
• This algorithm is applicable to
undirected and directed graphs with
nonnegative weights only.
• Single Source Shortest Paths Problem: Given a weighted
• connected graph G, find shortest paths from source vertex s
• to each of the other vertices

• Dijkstra’s algorithm: Similar to Prim’s MST algorithm, with


• a different way of computing numerical labels: Among vertices
• not already in the tree, it finds vertex u with the smallest sum
• dv + w(v,u)
• where is a vertex for which shortest path has been already found
on preceding iterations (such vertices form a tree)
• dv is the length of the shortest path form source to v
w(v,u) is the length (weight) of edge from v to u
Example
solution
Example
• Let T be a tree constructed by
Dijkstra’s algorithm in the process of
solving the single-source shortest-
paths problem for a weighted
connected graph G.
• a. True or false: T is a spanning
tree of G?
• b. True or false: T is a minimum
spanning tree of G?
Huffman code
Exercise
solution
Exercise
• What is the maximal length of a
codeword possible in a Huffman
encoding of an alphabet of n
symbols?

You might also like