Greedy algorithm

steepest ascent algorithm, steepest descent algorithm, myopic algorithm

An algorithm that at every step selects the best choice available at that time without regard to possible future consequences. This is an idea that is used as a heuristic, but there are cases where the greedy algorithm gives an optimal solution, e.g., in the Kruskal algorithm and in the Prim algorithm for finding a minimum spanning tree in a network. The Prim algorithm works as follows. Start with any node and connect it to the node nearest to it. Given a connected set of nodes, take the unconnected node that is nearest to one in the connected set, and use that edge. Continue until all nodes are connected. Ties are broken arbitrarily.

The Kruskal algorithm uses similar ideas. See [a1] for more details and for the justification of such methods.

For maximizing a set function, the greedy algorithm works as follows. Let $\nu(Q)$ be a real-valued function defined on all subsets $Q$ of $\{1,2,\ldots,n\}$ and consider the problem $\max \nu(Q)$.

Take $Q^0 = \emptyset$, $t=1$, as a start.

At stage $t$, consider $\max \nu(Q^{t-1} \cup \{j\})$ and choose any $j_t \in \{1,2,\ldots,n\}$ that realizes this maximum; if $\nu(Q^{t-1} \cup \{j_t\}) \le \nu(Q^{t-1})$ stop; $Q^{t-1}$ is the greedy solution; if $\nu(Q^{t-1} \cup \{j_t\}) > \nu(Q^{t-1})$, set $Q^t = Q^{t-1} \cup \{j_t\}$.

The famous Dijkstra algorithm for shortest paths in networks is also of greedy type.

See [a3] for an analysis of the greedy algorithm as applied to knapsack-type problems.

The greedy algorithm can be used to characterize matroids (see Matroid).

A combinatorial structure that generalizes matroids (as well as anti-matroids) and also closely linked to the greedy algorithm is that of a greedoid (whence the somewhat less than euphonious name), which deals with ordered rather than unstructured sets (which is the case of matroids).

References

[a1]	B. Korte, L. Lovász, R. Schruder, "Greedoids" , Springer (1991)
[a2]	C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)
[a3]	S. Walukiewicz, "Integer programming" , Kluwer Acad. Publ. (1991)