“Greedy problems” here refer to the problem statement which can be solved well using “Greedy Algorithms”. Greedy algorithms are basically the algorithms which give solution by reaching a local optimal solution. To know more about greedy algorithms go here.
Some
of the famous problem statements which can be solved by greedy algorithm are –
1. Fractional Knapsack
Problem
2. Huffman Encoding
3. Minimal Spanning
Tree/Kruskal’s algorithm
4. Djikstra’s algorithm
Let’s
have a look at them:
1.
Fractional Knapsack Problem
In this
article, we describe the greedy algorithm for solving the Fractional Knapsack
Problem.
Fractional
knapsack problem is just a modified version of the famous knapsack problem.
Problem
Statement:
We are given a
knapsack (backpack) with a maximum weight capacity W. We are given N items with
each having weight wi and value vi. We have to fill the
knapsack such that we can have maximum value in our knapsack.
In fractional
knapsack problem, we are allowed to take certain fractions of each item so that
the value in the knapsack is maximized.
Approach:
a. Find Value/Weight ratio of
each item.
b. Arrange the items on the
basis of their Value/Weight in descending order.
c. Start taking the item with
highest Value/Weight until that item is exhausted or Maximum weight capacity is
reached.
d. If the condition in “c” is
not fulfilled, move to the next highest Value/Weight and repeat “c”.
2.
Huffman Encoding
The aim of
Huffman Coding is to make a shorter encoding than the first fixed width
encoding. Indeed it's a touch quite that, it's to urge the shortest possible
unambigious encoding. The genius of the algorithm is that it's simple and can
always find the optimum (shortest possible) encoding and this encoding will
always be but or adequate to the length of the equivalent 8-bit encoding.
Problem
Statement: Design an algorithm that can represent a given piece of text using
less number of bits.
Approach:
a. Count the amount of
occurrences of every byte within the sequence and put them during a list
b. Sort that list in
ascending order of frequency
c. Pick the 2 lowest
frequency bytes off the highest of the table and add them to the tree as two
branches on the trunk
d. Add the frequencies of
these two nodes together and add that a part of the tree back to the list and
type the list again in ascending order of frequencies
e. If there's quite one item
left within the list then attend step 3, otherwise you're done, the last item
within the list is that the completed tree
Fig- Huffman Data
Compression (ref- github)
|
3.
Minimal Spanning Tree/Kruskal’s
algorithm
Most of the
cable network companies use the Disjoint Set Union arrangement in Kruskal’s
algorithm to seek out the shortest path to get cables across a city or group of
cities.
Problem
Statement:
Given a graph G
with vertex V and edges E, spanning tree is a tree that spans
(traces every vertex of G) G and is a subgraph of G (every
edge in tree is an edge in G). Now consider every edge has a weight
assigned to it. Minimal Spanning Tree is a spanning tree where the sum of each
weight is minimum.
Approach:
a. Sort the edges in
ascending order.
b. Start adding the edges
from minimum weight to maximum weight.
c. If a cycle is formed by
adding an edge, don’t consider that edge and move to the next edge. (A cycle is
formed in a graph when both vertexes on both sides of the edge are already
visited.)
Fig:- Minimum
Spanning Tree (ref- wikipedia)
|
4.
Djikstra’s algorithm
Problem Statement:
Given a graph G
with vertexes Vi and edges Ei with an
assigned weight to each edge, find the path which has the shortest weight sum
from a start node Vs to an end node Ve.
Approach:
a. Dijkstra’s algorithm
initially marks the space (from the starting node) to each other node on the
graph with infinity and 0 for our initial node.
b. Set the initial node as
current. Mark all other nodes unvisited. Create a group of all the unvisited
nodes called the unvisited set.
c. For the present node,
consider all of its neighbors and calculate their tentative distances. Compare
the newly calculated tentative distance to the present assigned value and
assign the smaller one.
d. Once we are done
considering all of the neighbors of the present node, mark the present node as
visited and take away it from the unvisited set. A node once visited, will
never be checked again.
e. If the destination node
has been marked visited (when planning a route between two specific nodes) or
if the littlest tentative distance among the nodes within the unvisited set is
infinity (when planning an entire traversal; occurs when there's no connection
between the beginning node and remaining unvisited nodes), then stop. The
algorithm has been completed.
f. Otherwise, select the
unvisited node that's marked with the littlest tentative distance, set it because
the new current node, and return to step 3.
 |
Great content
ReplyDeleteGreat Information
ReplyDeleteGreat Work.
ReplyDeleteGreat work
ReplyDeleteExcellent work
ReplyDeleteYou set a high bar with this one..!!
ReplyDeleteGreat Work!!
ReplyDeleteExcellent
ReplyDeleteExcellent work !!!
ReplyDelete