Greedy algorithm
= Greedy algorithm
{wiki}
= Greedy
{synonym}
A <greedy algorithm> builds a <feasible solution> by repeatedly committing to a locally preferred next choice. Each commitment is final: the <algorithm> does not revisit it when later choices become available. In <mathematical optimization>, the important question is whether those commitments can still attain the best <objective function> value.
For example, a shared telescope can accept several observation requests with fixed time slots. In <interval scheduling>, every completed request counts equally, and overlapping requests cannot both be accepted. Choosing the request that finishes earliest leaves the resource available sooner. The example below turns that intuition into a precise rule, then shows why choosing the earliest start or shortest duration can lose jobs.
<Greedy algorithms> are attractive because a single pass can replace a search through many candidate <subsets>. However, "locally best" is only a design proposal. A problem-specific <greedy-choice property>, often established by an <exchange argument>, must connect the local decision to the actual <objective function>. The largest-individual-value rule in the <0-1 knapsack problem> fails; <Dijkstra's algorithm> needs its nonnegative-edge assumptions. A rule's success in one <optimization> task does not justify it in another.