Los algoritmos codiciosos producen buenas soluciones en algunos problemas matemáticos pero no en otros. La mayoría de los problemas para los cuales trabajan bien tienen dos características:

; Característica bien escogida codiciosa : Podemos tomar cualquier decisión parece la mejor en el momento y después soluciona los subproblemas que se presentan más adelante. La decisión tomada por un algoritmo codicioso puede depender de las decisiones tomadas hasta ahora pero no en las opciones futuras o todas las soluciones al subproblema. Toma iterativo una decisión codiciosa después de otra, reduciendo cada problema dado en más pequeño. Es decir un algoritmo codicioso nunca reconsidera sus opciones. Ésta es la diferencia principal de la programación dinámica, que es exhaustiva y se garantiza para encontrar la solución. Después de cada etapa, la programación dinámica toma las decisiones basadas en todas las decisiones tomadas en la etapa anterior, y puede reconsiderar la trayectoria algorítmica de la etapa anterior a la solución.

; Subestructura óptima : Un problema exhibe la subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas.

; cuando el codicioso-tipo algoritmos falla : Para muchos otros problemas, los algoritmos codiciosos pueden producir las soluciones posibles peores únicas del . Un ejemplo es el algoritmo vecino más cercano mencionado anteriormente: para cada número de ciudades hay una asignación de distancias entre las ciudades para las cuales el heurístico vecino más cercano produce el viaje posible peor único (G. Para más información, ver las referencias.

Usos

Para la mayoría de los problemas, los algoritmos codiciosos sobre todo (pero no siempre) no pueden encontrar la solución global óptima, porque no funcionan generalmente exhaustivo en todos los datos. Pueden llegar a comisiones a ciertas opciones demasiado temprano que eviten que encuentren la mejor solución total más adelante. Por ejemplo, todos los algoritmos codiciosos sabidos para el representan el problema de colorante gráficamente y el resto de los problemas NP-completos no encuentran constantemente soluciones óptimas. Sin embargo, son útiles porque son rápidos pensar para arriba y dar a menudo buenas aproximaciones al grado óptimo.

Si un algoritmo codicioso se puede demostrar para rendir el grado óptimo global para una clase dada del problema, se convierte en típicamente el método de opción porque es más rápido que otros métodos de la optimización como la programación dinámica. Los ejemplos de tales algoritmos codiciosos son el algoritmo de Kruskal y el algoritmo remilgado para encontrar atravesar del mínimo - el algoritmo de Dijkstra de los árboles para encontrar las trayectorias más cortas de la Solo-Fuente, y el algoritmo para encontrar los árboles óptimos de Huffman

La teoría de los Matroids y la teoría más general Greedoids proporcionan las clases enteras de tales algoritmos.

Los algoritmos codiciosos aparecen en la encaminamiento de la red también. Usar la encaminamiento codiciosa, un mensaje se remite al nodo vecino que es " closest" a la destinación. La noción de la localización de un nodo (y por lo tanto del " closeness") puede ser determinado por su localización física, como en la encaminamiento geográfica usada por la localización ad hoc de las redes puede también estar una construcción enteramente artificial como en la pequeña encaminamiento del mundo y las tablas de elección arbitraria distribuidas

Ejemplos