Los algoritmos codiciosos determinan la cantidad mínima de monedas que se deben dar al dar el cambio. Estos son los pasos que la mayoría de las personas seguirían para emular un algoritmo codicioso que represente 36 centavos utilizando solo monedas con valores {1, 5, 10, 20}. La moneda de mayor valor, menor que el cambio restante que se debe, es el óptimo local. (En general, el problema de dar el cambio requiere programación dinámica para encontrar una solución óptima; sin embargo, la mayoría de los sistemas monetarios son casos especiales en los que la estrategia codiciosa sí encuentra una solución óptima).
Un algoritmo codicioso es cualquier algoritmo que sigue la heurística de resolución de problemas de tomar la decisión localmente óptima en cada etapa. [1] En muchos problemas, una estrategia codiciosa no produce una solución óptima, pero una heurística codiciosa puede producir soluciones localmente óptimas que se aproximan a una solución globalmente óptima en un tiempo razonable.
Por ejemplo, una estrategia voraz para el problema del viajante de comercio (que es de alta complejidad computacional ) es la siguiente heurística: "En cada paso del viaje, visita la ciudad no visitada más cercana". Esta heurística no pretende encontrar la mejor solución, pero termina en un número razonable de pasos; encontrar una solución óptima para un problema tan complejo normalmente requiere una cantidad irrazonablemente grande de pasos. En optimización matemática, los algoritmos voraces resuelven de manera óptima problemas combinatorios que tienen las propiedades de los matroides y dan aproximaciones de factor constante a problemas de optimización con la estructura submodular.
Detalles específicos
Los algoritmos voraces producen buenas soluciones para algunos problemas matemáticos , pero no para otros. La mayoría de los problemas para los que funcionan tendrán dos propiedades:
Propiedad de elección codiciosa
Se puede elegir la opción que parezca mejor en un momento dado y luego (de forma recursiva) resolver los subproblemas restantes. La elección que hace un algoritmo voraz puede depender de las opciones que se hayan elegido hasta el momento, pero no de las opciones futuras ni de todas las soluciones del subproblema. Iterativamente, toma una opción voraz tras otra, reduciendo cada problema dado a uno más pequeño. En otras palabras, un algoritmo voraz nunca reconsidera sus opciones. Esta es la principal diferencia con la programación dinámica , que es exhaustiva y garantiza encontrar la solución. Después de cada etapa, la programación dinámica toma decisiones basadas en todas las decisiones tomadas en la etapa anterior y puede reconsiderar el camino algorítmico de la etapa anterior hacia la solución.
Subestructura óptima
"Un problema exhibe una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas". [2]
Casos de fracaso
Ejemplos de cómo un algoritmo codicioso puede no lograr la solución óptima.
Los algoritmos voraces no logran producir la solución óptima para muchos otros problemas e incluso pueden producir la peor solución posible. Un ejemplo es el problema del viajante mencionado anteriormente: para cada número de ciudades, hay una asignación de distancias entre las ciudades para las cuales la heurística del vecino más cercano produce el peor recorrido posible. [3]
Para otros ejemplos posibles, véase el efecto horizonte .
Tipos
Los algoritmos voraces pueden caracterizarse como "poco previsores" y también como "irrecuperables". Son ideales sólo para problemas que tienen una "subestructura óptima". A pesar de esto, para muchos problemas simples, los algoritmos más adecuados son voraces. Sin embargo, es importante señalar que el algoritmo voraz puede usarse como un algoritmo de selección para priorizar opciones dentro de un algoritmo de búsqueda o de ramificación y acotación. Existen algunas variaciones del algoritmo voraz: [4]
Algoritmos puramente codiciosos
Algoritmos voraces ortogonales
Algoritmos relajados y codiciosos
Teoría
Los algoritmos voraces tienen una larga historia de estudio en la optimización combinatoria y la informática teórica . Se sabe que las heurísticas voraces producen resultados subóptimos en muchos problemas, [5] por lo que las preguntas naturales son:
¿Para qué problemas funcionan óptimamente los algoritmos voraces?
¿Para qué problemas los algoritmos voraces garantizan una solución aproximadamente óptima?
¿Para qué problemas se garantiza que el algoritmo voraz no producirá una solución óptima?
Existe una gran cantidad de literatura que responde a estas preguntas para clases generales de problemas, como matroides , así como para problemas específicos, como cobertura de conjuntos .
Matroides
Un matroide es una estructura matemática que generaliza la noción de independencia lineal de los espacios vectoriales a conjuntos arbitrarios. Si un problema de optimización tiene la estructura de un matroide, entonces el algoritmo voraz apropiado lo resolverá de manera óptima. [6]
Funciones submodulares
Una función definida en subconjuntos de un conjunto se llama submodular si para cada tenemos que .
Supongamos que se desea encontrar un conjunto que maximice . El algoritmo voraz, que construye un conjunto añadiendo de forma incremental el elemento que aumenta más en cada paso, produce como resultado un conjunto que es al menos . [7] Es decir, el algoritmo voraz funciona dentro de un factor constante de tan bueno como la solución óptima.
Se pueden demostrar garantías similares cuando se imponen restricciones adicionales, como restricciones de cardinalidad, [8] en la salida, aunque a menudo se requieren ligeras variaciones en el algoritmo voraz. Véase [9] para una descripción general.
Otros problemas con las garantías
Otros problemas para los que el algoritmo voraz ofrece una garantía sólida, pero no una solución óptima, incluyen
Muchos de estos problemas tienen límites inferiores coincidentes, es decir, el algoritmo codicioso no funciona mejor que la garantía en el peor de los casos.
Aplicaciones
Los algoritmos voraces normalmente (pero no siempre) no logran encontrar la solución globalmente óptima porque no suelen operar exhaustivamente sobre todos los datos. Pueden comprometerse con ciertas opciones demasiado pronto, lo que les impide encontrar la mejor solución global más adelante. Por ejemplo, todos los algoritmos voraces de coloración conocidos para el problema de coloración de grafos y todos los demás problemas NP-completos no encuentran soluciones óptimas de manera consistente. Sin embargo, son útiles porque se les ocurre rápidamente y a menudo brindan buenas aproximaciones al óptimo.
Los algoritmos voraces también aparecen en el enrutamiento de redes . Mediante el enrutamiento voraz, se reenvía un mensaje al nodo vecino que está "más cerca" del destino. La noción de ubicación de un nodo (y, por lo tanto, de "cercanía") puede determinarse por su ubicación física, como en el enrutamiento geográfico utilizado por redes ad hoc . La ubicación también puede ser una construcción completamente artificial, como en el enrutamiento de mundo pequeño y la tabla hash distribuida .
Ejemplos
El problema de selección de actividades es característico de esta clase de problemas, donde el objetivo es elegir el número máximo de actividades que no entren en conflicto entre sí.
En el juego de ordenador para Macintosh Crystal Quest, el objetivo es recolectar cristales, de forma similar al problema del viajante . El juego tiene un modo de demostración, en el que se utiliza un algoritmo codicioso para llegar a todos los cristales. La inteligencia artificial no tiene en cuenta los obstáculos, por lo que el modo de demostración suele terminar rápidamente.
La búsqueda coincidente es un ejemplo de un algoritmo codicioso aplicado a la aproximación de señales.
Un algoritmo codicioso encuentra la solución óptima al problema de Malfatti de encontrar tres círculos disjuntos dentro de un triángulo dado que maximicen el área total de los círculos; se conjetura que el mismo algoritmo codicioso es óptimo para cualquier número de círculos.
Se utiliza un algoritmo codicioso para construir un árbol de Huffman durante la codificación de Huffman donde encuentra una solución óptima.
En el aprendizaje de árboles de decisión , se utilizan comúnmente algoritmos voraces, sin embargo, no se garantiza que encuentren la solución óptima.
Un algoritmo popular de este tipo es el algoritmo ID3 para la construcción de árboles de decisión.
^ Black, Paul E. (2 de febrero de 2005). "algoritmo voraz". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología (NIST) de EE. UU . . Consultado el 17 de agosto de 2012 .
^ Cormen et al. 2001, cap. 16
^ Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "El viajante de comercio no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemáticas Aplicadas Discretas . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
^ DeVore, RA; Temlyakov, VN (1996-12-01). "Algunas observaciones sobre algoritmos voraces". Avances en Matemática Computacional . 5 (1): 173–187. doi :10.1007/BF02124742. ISSN 1572-9044.
^ Feige 1998
^ Papadimitriou y Steiglitz 1998
^ Nemhauser, Wolsey y Fisher 1978
^ Buchbinder y otros, 2014
^ Krause y Golovin 2014
^ "Lección 5: Introducción a los algoritmos de aproximación" (PDF) . Algoritmos avanzados (2IL45) — Apuntes del curso . TU Eindhoven. Archivado (PDF) desde el original el 2022-10-09.
Fuentes
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "16 algoritmos codiciosos". Introducción a los algoritmos . Prensa del MIT. págs. 370–. ISBN 978-0-262-03293-3.
Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "El viajante de comercio no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemáticas Aplicadas Discretas . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "Cuando el algoritmo voraz falla". Optimización discreta . 1 (2): 121–127. doi : 10.1016/j.disopt.2004.03.007 .
Bendall, Gareth; Margot, François (2006). "Resistencia de tipo voraz en problemas combinatorios". Optimización discreta . 3 (4): 288–298. doi : 10.1016/j.disopt.2006.03.001 .
Feige, U. (1998). "Un umbral de ln n para aproximar la cobertura de conjuntos" (PDF) . Revista de la ACM . 45 (4): 634–652. doi :10.1145/285055.285059. S2CID 52827488. Archivado (PDF) desde el original el 2022-10-09.
Nemhauser, G.; Wolsey, LA; Fisher, ML (1978). "Análisis de aproximaciones para maximizar funciones de conjuntos submodulares—I". Programación matemática . 14 (1): 265–294. doi :10.1007/BF01588971. S2CID 206800425.
Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). "Maximización submodular con restricciones de cardinalidad" (PDF) . Actas del vigésimo quinto simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. doi :10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Archivado (PDF) del original el 9 de octubre de 2022.
Krause, A.; Golovin, D. (2014). "Maximización de funciones submodulares". En Bordeaux, L.; Hamadi, Y.; Kohli, P. (eds.). Tractability: Practical Approaches to Hard Problems (Tratabilidad: enfoques prácticos para problemas difíciles ). Cambridge University Press. págs. 71–104. doi :10.1017/CBO9781139177801.004. ISBN.9781139177801.
