Cheat Sheet: Greedy Algorithm
- Definition: A greedy algorithm makes the locally optimal choice at each step, hoping it will lead to a globally optimal solution.
- Advantage: Simple and efficient, as it doesn’t require backtracking.
- Disadvantage: Doesn’t always result in the optimal solution since it only focuses on short-term gains.
- Examples:
- Coin change problem: Always picks the largest possible coin to minimize the remaining amount.
- Activity selection problem: Chooses the activity that finishes the earliest to maximize the number of activities.
Cheat Sheet: Elitist Algorithm
- Definition: An algorithm, particularly in genetic algorithms, that preserves the best solutions from one generation to the next without change.
- Advantage: Ensures that the best solutions are not lost, maintaining progress.
- Disadvantage: Can lead to premature convergence, where the algorithm settles on suboptimal solutions too quickly.
- Examples:
- Genetic algorithms: The top-performing individuals are directly passed to the next generation, while the rest undergo mutation and crossover.
An algorithm can be both greedy and elitist, particularly in the context of genetic algorithms. Here’s how:
- Greedy component: The algorithm can make local, short-term decisions, like selecting individuals for crossover or mutation based on their current fitness scores.
- Elitist component: At the same time, it can preserve the top-performing solutions from the current generation (elitism), ensuring that the best solutions are always carried forward to the next generation.
For example, in a genetic algorithm with elitism, the greedy aspect would come into play when selecting parents based on fitness (a greedy choice for reproduction), while the elitist aspect ensures that the very best solutions are never lost.
So, the algorithm can use greedy decisions to explore solutions while still safeguarding the best outcomes through elitism.