Greedy algorithm

A greedy algorithm builds a solution by repeatedly choosing the locally best available option, without revisiting earlier choices. It produces a global optimum only for problems whose structure supports that strategy.

Greedy choice property: A property of an optimization problem stating that some globally optimal solution begins with a locally optimal choice. It identifies when an algorithm’s first local choice can safely belong to an optimal solution.
Kruskal's algorithm: A minimum-spanning-tree algorithm that adds edges in increasing weight order while avoiding cycles. Its edge-by-edge choices are justified by the cut property of minimum spanning trees.
Dynamic programming: An algorithmic method that solves overlapping subproblems and combines their results, often storing intermediate answers. Unlike a greedy method, it can compare alternatives whose consequences unfold across multiple choices.
Combinatorial optimization: The study of finding optimal choices among a finite or countable set of feasible combinations. Greedy algorithms are one approach to optimizing discrete choices.
Optimal substructure: A property of an optimization problem whose optimal solutions contain optimal solutions to smaller subproblems. After a greedy choice, optimal substructure lets the remaining problem be solved on its own.
Prim's algorithm: A minimum-spanning-tree algorithm that repeatedly adds the cheapest edge connecting the current tree to a new vertex. It grows a tree through locally cheapest safe edges, illustrating a different greedy construction.
Backtracking: A search method that explores candidate solutions and retracts choices when they cannot lead to a valid result. Backtracking revisits decisions that a greedy algorithm permanently commits to.
Optimization problem: A problem that asks for the best feasible solution according to an objective function. The meaning of “locally best” depends on the objective and feasible solutions being optimized.
Exchange argument: A proof technique that transforms an optimal solution to include a chosen element without worsening its value. It can prove that a locally optimal choice is compatible with a global optimum.
Dijkstra's algorithm: A single-source shortest-path algorithm for graphs with nonnegative edge weights. It finalizes the nearest unsettled vertex, a greedy choice valid under its weight constraint.

Linked from 19 pages