Greedy Algorithm
Greedy Algorithm
Definition
A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment.
It doesn't worry whether the current best result will bring the overall optimal result.
The algorithm never reverses the earlier decision, even if the choice is wrong.
It works in a top-down approach.
This algorithm may not produce the best result for all problems because it always opts for the local best choice to yield a global best result.
However, we can determine if the greedy algorithm can be used with any problem if the problem has the following properties:
Properties Required for Greedy Algorithm
Greedy Choice Property
If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps, then the problem can be solved using a greedy approach.
This property is called the greedy choice property.
Optimal Substructure
If the optimal overall solution to the problem corresponds to the optimal solution of its subproblems, then the problem can be solved using a greedy approach.
This property is termed optimal substructure.
Advantages of Greedy Approach
The algorithm is easier to describe.
The algorithm can perform better than other algorithms (but not in all cases).
Drawbacks of Greedy Approach
As stated earlier, the greedy algorithm doesn't always yield the optimal solution.
This is the major drawback of the algorithm.
Example: Finding the Longest Path in a Graph
Suppose we want to find the longest path in a graph from root to leaf using the greedy algorithm.
Start with the root node (20).
The weight of the right child is 3, and the weight of the left child is 2.
To find the largest path, the optimal choice at this moment is 3 (greedy selection).
The weight of the only child of 3 is 1.
The final greedy path gives us a result of: 20 + 3 + 1 = 24. However, this is not the optimal solution as there exists another path yielding a higher weight: 20 + 2 + 10 = 32.
Approach Description
Initially, the solution set (containing answers) is empty.
At each step, an item is added to the solution set until reaching a solution.
If the solution set is feasible, the current item is kept; otherwise, the item is rejected and never considered again.
Example: Coin Change Problem
Problem: Make change for an amount using the smallest possible number of coins.
Amount: 18
Available Coins:
$5 coin
$2 coin
$1 coin
There is no limit to the number of each coin you can use.
Steps to Solve:
Create an empty solution set: solution ext{-}set = ext{{}}.
Available coins: ext{{5, 2, 1}}.
Set current sum = 0.
Always select the coin with the largest value (i.e., 5) until the sum exceeds 18:
1st iteration: solution ext{-}set = ext{{5}}, sum = 5.
2nd iteration: solution ext{-}set = ext{{5, 5}}, sum = 10.
3rd iteration: solution ext{-}set = ext{{5, 5, 5}}, sum = 15.
4th iteration: solution ext{-}set = ext{{5, 5, 5, 2}}, sum = 17.
5th iteration: select 1: sum = 18; solution ext{-}set = ext{{5, 5, 5, 2, 1}}.
Activity Selection Problem
The greedy algorithm starts with the given constraints and moves accordingly.
Problem Description:
Given n activities with provided start and finish times, select the maximum number of activities that can be performed by a single individual, assuming only one activity can be worked on at a time.
Example 1:
Activities sorted by finish time:
start: {10, 12, 20}
finish: {20, 25, 30}
Maximum activities executed: {0, 2} (indexes in start[] and finish[]).
Example 2:
Consider 6 activities:
start: {1, 3, 0, 5, 8, 10}
finish: {2, 7, 6, 8, 9, 15}
Maximum activities executed: {0, 4, 5} (indexes in start[] and finish[]).
Job Sequencing Problem
Example 1:
Input:
Jobs with deadlines and profits:
JobID, Deadline, Profit
a: 4, 20
b: 1, 10
c: 1, 40
d: 1, 30
Output: Maximum profit sequence of jobs: c, a.
Example 2:
Input:
Jobs with deadlines and profits:
JobID, Deadline, Profit
a: 2, 100
b: 1, 19
c: 1, 27
d: 1, 25
e: 3, 15
Output: Maximum profit sequence of jobs: c, a, e.
Fractional Knapsack Problem
Greedy Approach: Calculate the ratio of profit/weight and select items accordingly.
Consider the capacity of the knapsack: W = 60.
Provided items:
Item A: Profit = 280, Weight = 40
Item B: Profit = 100, Weight = 10
Item C: Profit = 120, Weight = 20
Item D: Profit = 120, Weight = 24
Calculated Ratios:
Item
Profit
Weight
Ratio (p/w)
A
280
40
7
B
100
10
10
C
120
20
6
D
120
24
5
Selection Process
Choose Item B first (weight < knapsack capacity).
Choose Item A next (weight < remaining capacity).
Choose Item C after that, but only a fraction since the remaining capacity < weight of C.
Fraction chosen: rac{(60 - 50)}{20}.
Total weight of selected items: 10 + 40 + 20 imes rac{10}{20} = 60.
Total profit becomes: 100 + 280 + 120 imes rac{10}{20} = 380 + 60 = 440.
This is the optimal solution; no other combination yields higher profit.
Graph Coloring Problem
Definition
Graph coloring, also known as vertex coloring, colors a graph’s vertices such that no two adjacent vertices share the same color.
K-Colorable Graph
A graph that can be assigned a proper k-coloring is termed k-colorable.
K-Chromatic Graph
The smallest number of colors required to color a graph G is its chromatic number. A graph that is k-chromatic has a chromatic number exactly equal to k.
Greedy Coloring Algorithm
Greedy coloring proceeds by considering the vertices of the graph in sequence and assigning each vertex its first available color (the smallest unused color by adjacent vertices).
For a graph with maximum degree x, greedy coloring will use at most x + 1 colors.
Drawbacks of Greedy Coloring
Greedy coloring does not always minimize the total number of colors required and can be suboptimal.
Example: A crown graph (a complete bipartite graph) can be 2-colored, but greedy coloring may yield x + 1 colors.
Procedure for Greedy Coloring
Coloring the First Vertex: Color a vertex with color 1.
Coloring Subsequent Vertices: Pick an uncolored vertex v. Color it with the lowest-numbered color not used on adjacent colored vertices. If all previously used colors are adjacent, introduce a new color and number it.
Continue Coloring: Repeat until all vertices are colored.
Example of Graph Coloring
Initially color vertex a as orange (color 1).
Adjacent vertices of vertex a (b and d) are colored with different colors (grey as color 2, and blue as color 3). Vertex c is colored orange again as no adjacent vertex of c is colored with color 1.
The graph can be colored with 3 colors, resulting in a chromatic number of 3.