Greedy Method
What Is Greedy Algorithm?
A Greedy
algorithm is an approach to solving a problem that selects the most appropriate
option based on the current situation. This algorithm ignores the fact that the
current best result may not bring about the overall optimal result.
Control abstraction
The Greedy method
suggest that one can devise an algorithm that work in
stages, considering one input at a time. At each stage, a decision is made regarding whether a
particular input is an optimal solution or not. This is done by considering the
inputs in an order determined by some selection procedure.
Knapsack
Problem Using Greedy Method: The selection of some things, each with profit and
weight values, to be packed into one or more knapsacks with capacity is the
fundamental idea behind all families of knapsack problems.
Example
Objects: 1
2 3 4 5 6
7
Profit
(P): 10 15 7
8 9 4
Weight(w):
1 3 5 4
1 3 2
W
(Weight of the knapsack): 15
n
(no of items): 7
In this case, we first calculate the
profit/weight ratio.
Object
1: 5/1 = 5
Object
2: 10/3 = 3. 33
Object 3: 15/5 = 3
Object
4: 7/4 = 1.7
Object 5: 8/1 = 8
Object
6: 9/3 = 3
Object 7: 4/2 = 2
P:w: 5 3.3
3 1.7 8 3 2
(8 + 5 + 10 + 15 + 9 +
4)= 51.
Job Sequencing with
Deadline
starting
time and ending time, they need to be scheduled in such a way that maximum
profit is received within the maximum deadline.
·
Once, the
deadline is decided, arrange the jobs in descending order of their profits.
·
Selects the jobs
with highest profits, their time periods not exceeding the maximum deadline.
·
The selected set
of jobs are the output.
A spanning tree is defined as a tree-like subgraph of a
connected, undirected graph that includes all the vertices of the graph.
it
is a subset of the edges of the graph that forms a tree (acyclic) where every node of the graph is a part of the
tree.
Example:
The
minimum spanning tree has all the properties of a spanning tree with an added
constraint of having the minimum possible weights among all possible spanning
trees. Like a spanning tree, there can also be many possible MSTs for a graph.
Steps in
Kruskal’s Algorithm to generate a minimum spanning tree:
·
Step 1:
Sort all edges in increasing order of their edge weights.
·
Step 2:
Pick the smallest edge.
·
Step 3:
Check if the new edge creates a cycle or loop in a spanning tree.
· Step 4: If it does not form the cycle, then include that edge in MST. Otherwise, discard it.
· Step 5: Repeat from step 2 until it all edges in MST.
Prims Algorithm
The
algorithm starts with an empty spanning tree. The idea is to maintain two sets
of vertices. The first set contains the vertices already included in the MST,
and the other set contains the vertices not yet included. At every step, it
considers all the edges that connect the two sets and picks the minimum weight
edge from these edges. After picking the edge, it moves the other endpoint of
the edge to the set containing MST.
Optimal Storage on Tapes is one of the applications of the
Greedy Method. The objective is to find the Optimal
retrieval time for accessing programs that are stored on tape. There are n programs that are to be stored on a computer
tape of length L.
Optimal merge
pattern
•
Optimal
merge pattern is a pattern that relates to the merging of two or more
sorted files in a single sorted file.
•
two sorted files containing n and m records
respectively then they could be merged together, to obtain one sorted file in
time O (n+m).
Huffman
Coding
•
Huffman
Coding is a technique of compressing data to reduce its size without losing any
of the details
•
Huffman
coding first creates a tree using the frequencies of the character
We
need to maintain the path distance of every vertex. We can store that in an
array of size v, where v is the number of vertices.
Milan Tomic
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 comments:
Post a Comment