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 w1, w2, …, wn and values v1, v2, …, vn; 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.