Difference between revisions of "Greedy algorithm"
(Importing text file) |
m (link) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
''steepest ascent algorithm, steepest descent algorithm, myopic 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 [[ | + | 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 [[#References|[a1]]] for more details and for the justification of such methods. | The Kruskal algorithm uses similar ideas. See [[#References|[a1]]] for more details and for the justification of such methods. | ||
− | For maximizing a [[ | + | 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 | + | Take $Q^0 = \emptyset$, $t=1$, as a start. |
− | At stage | + | 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. | The famous Dijkstra algorithm for shortest paths in networks is also of greedy type. | ||
Line 15: | Line 15: | ||
See [[#References|[a3]]] for an analysis of the greedy algorithm as applied to knapsack-type problems. | See [[#References|[a3]]] for an analysis of the greedy algorithm as applied to knapsack-type problems. | ||
− | The greedy algorithm can be used to characterize matroids (see [[ | + | 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). | + | 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==== | ====References==== | ||
− | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> B. Korte, L. Lovász, R. Schruder, "Greedoids" , Springer (1991)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> S. Walukiewicz, "Integer programming" , Kluwer Acad. Publ. (1991)</TD></TR></table> | + | <table> |
+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> B. Korte, L. Lovász, R. Schruder, "Greedoids" , Springer (1991)</TD></TR> | ||
+ | <TR><TD valign="top">[a2]</TD> <TD valign="top"> C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)</TD></TR> | ||
+ | <TR><TD valign="top">[a3]</TD> <TD valign="top"> S. Walukiewicz, "Integer programming" , Kluwer Acad. Publ. (1991)</TD></TR> | ||
+ | </table> | ||
+ | |||
+ | {{TEX|done}} | ||
+ | |||
+ | [[Category:Algorithms]] |
Latest revision as of 15:16, 20 November 2014
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) |
Greedy algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Greedy_algorithm&oldid=11679