Greedyapproach

Greedy approach
The greedy approach is an algorithmic technique used to solve optimization problems by

making a sequence of choices. In each step, it chooses the option that seems the best at that
moment, often with the goal of finding a global optimum through locally optimal decisions. The
greedy algorithm doesn't always guarantee the optimal solution for all problems, but for some,
like the Minimum Spanning Tree or Knapsack Problem (fractional version), it does work
efficiently.
Characteristics of the Greedy Approach:
1. Local Optimal Choice: The algorithm always picks the best immediate choice without
considering future consequences.
2. No Reversals: Once a choice is made, it’s not changed or reversed.
3. Feasibility: It ensures that each step or choice adheres to the rules of the problem.
4. Optimal Substructure: Greedy algorithms work well for problems where an optimal
solution to a problem contains an optimal solution to subproblems.
Examples of Greedy Algorithms:
1. Dijkstra's Shortest Path Algorithm: Finds the shortest path in a weighted graph.
2. Prim’s Algorithm: Builds a minimum spanning tree for a weighted undirected graph.
3. Kruskal’s Algorithm: Constructs a minimum spanning tree by picking the smallest
edges.
4. Fractional Knapsack Problem: Maximizes value by taking fractions of items.
5. Activity Selection Problem: Maximizes the number of non-overlapping activities.
Steps in the Greedy Approach:
1. Define the problem in terms of a sequence of decisions.

2. Make the best choice at each step that appears best according to the problem's criteria.
3. Check if the solution is feasible (if it obeys all constraints).
4. Repeat until the solution is complete.
Pros and Cons:
 Pros: Fast and simple to implement, and it often yields good results for specific types of
problems.
 Cons: Doesn’t always guarantee an optimal solution for every problem; often requires the
problem to have certain properties like optimal substructure and the greedy-choice
property.
The greedy approach is useful and effective for problems with specific properties but can fail if
these properties aren’t met.
Let's go through each example with a numerical example that demonstrates how the greedy
approach works.
1. Dijkstra's Shortest Path Algorithm
Problem: Find the shortest path from a starting node AAA to all other nodes in a weighted
graph.
Graph Example
Let's consider the following graph with nodes and edge weights:
scss
Copy code
(A)---4---(B)
| |
1 2
| |
(C)---3---(D)
Steps:
 Start at node AAA with a distance of 0, and initialize other nodes as having infinite
distance.
 Select the node with the minimum distance that hasn't been visited.
1. From AAA: Distance to BBB = 4, Distance to CCC = 1.

o Updated distances: B=4B = 4B=4, C=1C = 1C=1.
2. Move to CCC (smallest distance):
o Distance to DDD via C=1+3=4C = 1 + 3 = 4C=1+3=4.
o Updated distances: D=4D = 4D=4, B=4B = 4B=4.
3. Move to BBB (next smallest distance):
o Distance to DDD via B=4+2=6B = 4 + 2 = 6B=4+2=6, but DDD's current
distance is already 4.
4. Move to DDD.
Final shortest distances from AAA: A=0A = 0A=0, B=4B = 4B=4, C=1C = 1C=1, D=4D =
4D=4.
2. Prim’s Algorithm
Problem: Find a Minimum Spanning Tree (MST) for a weighted, undirected graph.
Graph Example
Use the same graph as above:
scss
Copy code
(A)---4---(B)
| |
1 2
| |
(C)---3---(D)
Steps:
1. Start at node AAA and add the edge with the smallest weight connecting to an unvisited
node.
o Choose edge AAA-CCC with weight 1.
2. From CCC, choose the edge with the smallest weight.
o Choose edge CCC-DDD with weight 3.
3. From DDD, choose the edge with the smallest weight that connects to an unvisited node.
o Choose edge DDD-BBB with weight 2.
Result: The edges in the MST are AAA-CCC, CCC-DDD, and DDD-BBB with a total weight of
1+3+2=61 + 3 + 2 = 61+3+2=6.
3. Kruskal’s Algorithm
Problem: Find a Minimum Spanning Tree by adding edges of minimum weight and avoiding
cycles.
Graph Example
Use the same graph as above:
scss
Copy code
(A)---4---(B)
| |
1 2
| |
(C)---3---(D)
Steps:
1. Sort all edges by weight: AAA-CCC (1), DDD-BBB (2), CCC-DDD (3), AAA-BBB (4).
2. Start adding edges from the smallest weight, avoiding cycles.
o Add AAA-CCC with weight 1.
o Add DDD-BBB with weight 2.
o Add CCC-DDD with weight 3.
3. Stop, as adding AAA-BBB would create a cycle.
Result: The edges in the MST are AAA-CCC, DDD-BBB, and CCC-DDD with a total weight of
1+2+3=61 + 2 + 3 = 61+2+3=6.
4. Fractional Knapsack Problem
Problem: Maximize the total value of items in a knapsack with a weight limit, allowing fractions
of items.
Example:
 Knapsack weight limit = 50.

 Items:
o Item 1: Weight = 10, Value = 60 (Value per weight = 6)
Steps:
1. Sort items by value per weight: Item 1 (6), Item 2 (5), Item 3 (4).
2. Add items to the knapsack:
o Add all of Item 1 (Weight = 10, Value = 60).
o Add all of Item 2 (Weight = 20, Value = 100).
o For Item 3, add as much as possible with remaining capacity (20 weight from
Item 3).
 Fractional value of Item 3 = 2030×120=80\frac{20}{30} \times 120 =
803020×120=80.
Result: Total value in knapsack = 60+100+80=24060 + 100 + 80 = 24060+100+80=240.
5. Activity Selection Problem
Problem: Select the maximum number of activities that don’t overlap, given their start and end
times.
Example:
Activities with start and end times:
 Activity 1: (1, 4)
Steps:
1. Sort activities by end time: Activity 1 (4), Activity 2 (5), Activity 4 (7), Activity 5 (9),
Activity 6 (9), Activity 3 (6).
2. Start selecting activities from the earliest ending one that doesn’t overlap with the
previously selected activity:
o Select Activity 1 (ends at 4).
Result: Maximum set of non-overlapping activities: Activity 1, Activity 4, and Activity 5.

Greedyapproach

Uploaded by

Copyright:

Available Formats

Greedyapproach

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Greedyapproach

Uploaded by

Copyright:

Available Formats

Greedy approach

The greedy approach is an algorithmic technique used to solve optimization problems by

Characteristics of the Greedy Approach:

Examples of Greedy Algorithms:

Steps in the Greedy Approach:

1. Define the problem in terms of a sequence of decisions.

Pros and Cons:

1. Dijkstra's Shortest Path Algorithm

1. From AAA: Distance to BBB = 4, Distance to CCC = 1.

Use the same graph as above:

Use the same graph as above:

4. Fractional Knapsack Problem

 Knapsack weight limit = 50.

Result: Total value in knapsack = 60+100+80=24060 + 100 + 80 = 24060+100+80=240.

5. Activity Selection Problem

Result: Maximum set of non-overlapping activities: Activity 1, Activity 4, and Activity 5.

You might also like