Greedy Algorithms

Greedy Algorithms Overview

• Definition: A greedy algorithm makes the locally optimal choice at each stage with the hope of finding the global optimum.
• Application Areas: Used in optimization problems, such as the Knapsack problem, job scheduling, and graph algorithms (e.g., Prim's and Kruskal's).

Key Concepts in Greedy Algorithms

• Safe Move:

  • A move is considered safe if it can lead to an optimal solution.
  • Safety must be proved before making a greedy choice.

• Greedy Choice:

  • At each step, make a choice that seems best at the moment without considering future consequences.
  • Examples include:
  • Placing the maximum digit first
  • Using gas stations furthest along the route before refilling.

General Strategy

• Procedure:
  1. Identify a greedy choice.
  2. Prove that it is a safe move.
  3. Solve the problem as a set of subproblems.

Fractional Knapsack Problem

• Input: Item weights $w<em>1, w</em>2, …, w<em>n$ and values $v</em>1, v<em>2, …, v</em>n$; capacity $W$.
• Output: Maximum total value of fractions of items that fit into the knapsack.

Example of the Fractional Knapsack

• Items: 3 items with values and weights:
  • Item 1: value = 20, weight = 4 → $5 ext{/unit}$
  • Item 2: value = 18, weight = 3 → $6 ext{/unit}$
  • Item 3: value = 14, weight = 2 → $7 ext{/unit}$
• Optimal Strategy:
  • Fill the knapsack with items in descending order of value per weight.

Greedy Algorithm for Fractional Knapsack

1. Sort items based on value/weight ratio.
2. While the knapsack is not full:
   • Take the item with the highest value/weight ratio.
   • If the item fits entirely, take it; otherwise, take the fraction that fits.
3. Return the total value achieved.

Complexity

• The time complexity of the Knapsack problem when implemented using a greedy algorithm is $O(n ext{ log } n)$ due to sorting, and then a linear scan of the items, $O(n)$.

Grouping Children Problem

• Problem Statement: Organize children into groups such that the age of any two children in the same group differs by at most one year.
• Naive Algorithm:
  • Generate every possible grouping and check their validity. This leads to a complexity of $ext{Ω}(2^n)$.
• Efficient Algorithm:
  • Sort the ages and create groups from sorted sequence.
  • Each time you can cover as many elements as possible with segments of length 1.

Points Covering Problem

• Objective: Cover points with the minimum number of unit segments.
• Greedy Strategy:
  • Always cover the leftmost uncovered point with the first unit segment.
• Algorithm:
  • Keep track of the rightmost point covered, iterate through sorted points to cover subsequent points.

Car Fueling Problem

• Problem Statement: Given a distance a car can travel on a full tank, calculate the minimum number of refills required to travel between two points, A and B, with n gas stations in between.
• Greedy Approach:
  • Refill at the farthest reachable station each time until reaching the destination or unable to reach the next station.

Implementation of Greedy Algorithms

• Steps to Design:
  1. Identify the greedy choice.
  2. Check if it leads to a safe move.
  3. Repeat until the problem is solved or no choices are left.

Conclusion

• Greedy algorithms are often efficient and solve a broad range of optimization problems effectively. However, proving that greedy choices lead to optimal solutions can be critical and requires careful analysis.