Unit 12 Greedy Technique
Structure:
12.1 Introduction
12.2
Objectives
Introduction to Greedy Technique
Types of greedy algorithm
Greedy choice property
Applications of greedy technique
12.3 Prim's Algorithm
Description
Correctness
Time complexity
12.4 Kruskal's Algorithm
Description
Correctness
Time complexity
12.5 Dijkstra's Algorithm
Description
Correctness
Time complexity
12.6 Huffman Trees
Huffman code
Constructing Huffman tree
Constructing Huffman code
12.7 Summary
12.8 Glossary
12.9 Terminal Questions
12.10 Answers
12.1 Introduction
In the previous unit we learnt about dynamic programming which is an
optimization technique. In this unit you will learn the concepts of Greedy
technique algorithms that are used for optimization problems such as
Kruskal's algorithm and Prim's algorithm for finding minimum spanning
trees. You will also learn about Dijkstra's algorithm for finding single-source
shortest paths, and the algorithm for finding optimum Huffman trees.
,objectives:
After studying this unit you should be able to:
describe the Greedy technique
construct Prim's,Kruskal's and Dijkstra's
algorithm
check for correctness of Prim's, Kruskal's and
Dijkstra's algorithm
construct the algorithm for finding optimum Huffman trees
12.2 Introduction to Greedy Technique
The Greedy technique constructs a solution to an
through a sequence of choices, each expanding a optimization problem
partially constructed
solution until a complete solution to the problem is reached.
The sequences of choices made should be:
Feasible, i.e. satisfying the constraints
.Locally optimal with respect to a neighborhood definition
Greedy in terms of some measures and irrevocable
The greedy algorithm, always takes the best immediate solution while
finding an answer.
Greedy algorithms find the globally optimal solution for
some optimization problems.
Now, let us see the different types of greedy techniques.
12.2.1 Types of greedy algorithm
Greedy algorithms can be classified as 'short sighted', and as
recoverable'. They are ideal for problems with 'non
optimal substructure. Greedy
algorithms are best suited for simple problems like giving
greedy algorithm can also be used as a selection algorithmchange.
The
to prioritize
options within a search, or branch and bound algorithm. The
few variations to the greedy following are a
algorithm:
Pure greedy algorithms
Orthogonal greedy algorithms
Relaxed greedy algorithms
Pure greedy algorithm
Pure greedy algorithm makes local choices in all iterations in order to find an
optimal solution. The Pure greedy algorithm chooses functions to use in
approximating.
Relaxed greedy algorithm
he Relaxed the approximation order,
greedy algorithm provides and gives
aConstructive proof of the estimate. There are several variants of the
elaxed greedy algorithm and their application for different dictionaries.
, Orthogonal greedy algorithm
In Orthogonal greedy algorithm the best approximation from the functions
generated at each iteration is taken.
12.2.2 Greedy-choice property
In greedy algorithms a globally optimal solution is arrived by making a
when considering which
locallyoptimal (greedy) choice That is to say
choice to make, the choice that looks best in the current problem, without
choices made
considering results from sub problems is selected. The by a
greedy algorithm can depend on choices of the past. but
it cannot depend
on any future choices or on the solutions to sub problems. This Is where
greedy algorithm differs from dynamic programming
In dynamic programming, choices are made at each step. but the choice
usually depends on the solutions to sub problems. Dynamic-programming
solves problems in bottom-up manner that is solving from smaller sub
problems to larger sub problems
Therefore a greedy strategy usually progresses in a top-down fashion
making one greedy choice after another, reducing each given problem
instance to a smaller one.
There are various applications of greedy technique. Let us see those next
12.2.3 Applications of greedy technique
if a greedy algorithm is proven to yield the global optimum solution for a
given problem class, it becomes the method of choice because it is faster
than other optimization methods hence such algorithms can be applied in
the following areas
Optimal solutions:
Change making for "normal" coin denominations
Minimum spanning tree (MST)
o
Single-source shortest paths
o
Simple scheduling problems
Huffman codes
Approximations/heuristics:
o Traveling salesman problem (TSP)
o Knapsack problem
Other combinatorial optimization problems
Structure:
12.1 Introduction
12.2
Objectives
Introduction to Greedy Technique
Types of greedy algorithm
Greedy choice property
Applications of greedy technique
12.3 Prim's Algorithm
Description
Correctness
Time complexity
12.4 Kruskal's Algorithm
Description
Correctness
Time complexity
12.5 Dijkstra's Algorithm
Description
Correctness
Time complexity
12.6 Huffman Trees
Huffman code
Constructing Huffman tree
Constructing Huffman code
12.7 Summary
12.8 Glossary
12.9 Terminal Questions
12.10 Answers
12.1 Introduction
In the previous unit we learnt about dynamic programming which is an
optimization technique. In this unit you will learn the concepts of Greedy
technique algorithms that are used for optimization problems such as
Kruskal's algorithm and Prim's algorithm for finding minimum spanning
trees. You will also learn about Dijkstra's algorithm for finding single-source
shortest paths, and the algorithm for finding optimum Huffman trees.
,objectives:
After studying this unit you should be able to:
describe the Greedy technique
construct Prim's,Kruskal's and Dijkstra's
algorithm
check for correctness of Prim's, Kruskal's and
Dijkstra's algorithm
construct the algorithm for finding optimum Huffman trees
12.2 Introduction to Greedy Technique
The Greedy technique constructs a solution to an
through a sequence of choices, each expanding a optimization problem
partially constructed
solution until a complete solution to the problem is reached.
The sequences of choices made should be:
Feasible, i.e. satisfying the constraints
.Locally optimal with respect to a neighborhood definition
Greedy in terms of some measures and irrevocable
The greedy algorithm, always takes the best immediate solution while
finding an answer.
Greedy algorithms find the globally optimal solution for
some optimization problems.
Now, let us see the different types of greedy techniques.
12.2.1 Types of greedy algorithm
Greedy algorithms can be classified as 'short sighted', and as
recoverable'. They are ideal for problems with 'non
optimal substructure. Greedy
algorithms are best suited for simple problems like giving
greedy algorithm can also be used as a selection algorithmchange.
The
to prioritize
options within a search, or branch and bound algorithm. The
few variations to the greedy following are a
algorithm:
Pure greedy algorithms
Orthogonal greedy algorithms
Relaxed greedy algorithms
Pure greedy algorithm
Pure greedy algorithm makes local choices in all iterations in order to find an
optimal solution. The Pure greedy algorithm chooses functions to use in
approximating.
Relaxed greedy algorithm
he Relaxed the approximation order,
greedy algorithm provides and gives
aConstructive proof of the estimate. There are several variants of the
elaxed greedy algorithm and their application for different dictionaries.
, Orthogonal greedy algorithm
In Orthogonal greedy algorithm the best approximation from the functions
generated at each iteration is taken.
12.2.2 Greedy-choice property
In greedy algorithms a globally optimal solution is arrived by making a
when considering which
locallyoptimal (greedy) choice That is to say
choice to make, the choice that looks best in the current problem, without
choices made
considering results from sub problems is selected. The by a
greedy algorithm can depend on choices of the past. but
it cannot depend
on any future choices or on the solutions to sub problems. This Is where
greedy algorithm differs from dynamic programming
In dynamic programming, choices are made at each step. but the choice
usually depends on the solutions to sub problems. Dynamic-programming
solves problems in bottom-up manner that is solving from smaller sub
problems to larger sub problems
Therefore a greedy strategy usually progresses in a top-down fashion
making one greedy choice after another, reducing each given problem
instance to a smaller one.
There are various applications of greedy technique. Let us see those next
12.2.3 Applications of greedy technique
if a greedy algorithm is proven to yield the global optimum solution for a
given problem class, it becomes the method of choice because it is faster
than other optimization methods hence such algorithms can be applied in
the following areas
Optimal solutions:
Change making for "normal" coin denominations
Minimum spanning tree (MST)
o
Single-source shortest paths
o
Simple scheduling problems
Huffman codes
Approximations/heuristics:
o Traveling salesman problem (TSP)
o Knapsack problem
Other combinatorial optimization problems
