Namespaces
Variants
Actions

Difference between revisions of "Greedy algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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 [[Network|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.
+
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 [[Set function|set function]], the greedy algorithm works as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102101.png" /> be a real-valued function defined on all subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102102.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102103.png" /> and consider the problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102104.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102106.png" />, as a start.
+
Take $Q^0 = \emptyset$, $t=1$, as a start.
  
At stage <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102107.png" />, consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102108.png" /> and choose any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g1102109.png" /> that realizes this maximum; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g11021010.png" /> stop; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g11021011.png" /> is the greedy solution; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g11021012.png" />, set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110210/g11021013.png" />.
+
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 [[Matroid|Matroid]]).
+
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)
How to Cite This Entry:
Greedy algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Greedy_algorithm&oldid=11679
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article