Greedy algorithm

Definition

A greedy algorithm is a problem-solving approach that makes the locally optimal choice at each stage with the hope of finding a global optimum. It is often used when a problem can be broken down into simpler, smaller problems that can be solved independently and sequentially.

5 Must Know Facts For Your Next Test

1. Greedy algorithms work by making the best possible choice at each step without considering the overall problem.
2. In graph theory, greedy algorithms are commonly used for problems like finding minimum spanning trees or shortest paths.
3. Greedy algorithms do not always produce the optimal solution for every problem but are useful for approximation.
4. The Traveling Salesperson Problem (TSP) can be approached using greedy methods, like choosing the nearest unvisited city next.
5. A common example of a greedy algorithm in TSP is the nearest neighbor heuristic.

Review Questions

• What is a key characteristic of greedy algorithms in terms of decision-making?
• How does a greedy algorithm approach solving the Traveling Salesperson Problem?
• Can greedy algorithms guarantee an optimal solution for all types of problems? Why or why not?

Related terms

Heuristic: A strategy or technique that guides problem-solving but does not guarantee an optimal solution.

Minimum Spanning Tree: A subset of edges in a weighted graph that connects all vertices without cycles and with minimum possible total edge weight.

Shortest Path: The path between two vertices in a graph such that the sum of weights of its constituent edges is minimized.