Un algoritmo codicioso es cualquier algoritmo que sigue la heurística de resolución de problemas de realizar la elecció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 óptimas localmente que se aproximan a una solución óptima global en un período de tiempo razonable.
Por ejemplo, una estrategia codiciosa para el problema del viajante (que es de alta complejidad computacional) es la siguiente heurística: "En cada paso del viaje, visita la ciudad más cercana no visitada". Esta heurística no pretende encontrar la mejor solución, pero termina en un número razonable de pasos; Encontrar una solución óptima a un problema tan complejo normalmente requiere una cantidad excesiva de pasos. En optimización matemática, los algoritmos codiciosos resuelven de manera óptima problemas combinatorios que tienen las propiedades de matroides y brindan aproximaciones de factor constante a problemas de optimización con la estructura submodular.
Detalles específicos
Los algoritmos codiciosos 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
Podemos tomar la decisión que nos parezca mejor en ese momento y luego resolver los subproblemas que surjan más adelante. La elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta el momento, pero no de las elecciones futuras o de todas las soluciones al subproblema. De forma iterativa, toma una decisión codiciosa tras otra, reduciendo cada problema a uno más pequeño. En otras palabras, un algoritmo codicioso nunca reconsidera sus elecciones. 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 la ruta algorítmica 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 codiciosos 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 posibles ejemplos, ver efecto horizonte .
Tipos
Los algoritmos codiciosos pueden caracterizarse como "miopes" y también como "no recuperables". 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 los codiciosos. Sin embargo, es importante tener en cuenta que el algoritmo codicioso se puede utilizar como algoritmo de selección para priorizar opciones dentro de una búsqueda o como algoritmo de ramificación y vinculación. Hay algunas variaciones del algoritmo codicioso:
Algoritmos puros y codiciosos
Algoritmos codiciosos ortogonales
Algoritmos codiciosos relajados
Teoría
Los algoritmos codiciosos tienen una larga historia de estudio en optimización combinatoria e informática teórica . Se sabe que las heurísticas codiciosas producen resultados subóptimos en muchos problemas, [4] por lo que las preguntas naturales son:
¿Para qué problemas funcionan de manera óptima los algoritmos codiciosos?
¿Para qué problemas los algoritmos codiciosos garantizan una solución aproximadamente óptima?
¿Para qué problemas se garantiza que el algoritmo codicioso 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 set cover .
matroides
Una matroide es una estructura matemática que generaliza la noción de independencia lineal de espacios vectoriales a conjuntos arbitrarios. Si un problema de optimización tiene la estructura de una matroide, entonces el algoritmo codicioso apropiado lo resolverá de manera óptima. [5]
Funciones submodulares
Una función definida sobre subconjuntos de un conjunto se llama submodular si para cada uno tenemos eso .
Supongamos que se quiere encontrar un conjunto que maximice . El algoritmo codicioso, que construye un conjunto agregando incrementalmente el elemento que aumenta más en cada paso, produce como resultado un conjunto que es al menos . [6] Es decir, codicioso se desempeña dentro de un factor constante tan bueno como la solución óptima.
Se pueden demostrar garantías similares cuando se imponen restricciones adicionales, como restricciones de cardinalidad, [7] a la salida, aunque a menudo se requieren ligeras variaciones en el algoritmo codicioso. Consulte [8] para obtener una descripción general.
Otros problemas con las garantías
Otros problemas para los cuales el algoritmo codicioso ofrece una fuerte garantía, 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 codiciosos normalmente (pero no siempre) no logran encontrar la solución global óptima porque generalmente no operan de manera exhaustiva con todos los datos. Pueden comprometerse a tomar ciertas decisiones demasiado pronto, lo que les impide encontrar la mejor solución general más adelante. Por ejemplo, todos los algoritmos de coloración codiciosa conocidos para el problema de coloración de gráficos y todos los demás problemas NP-completos no encuentran consistentemente soluciones óptimas. Sin embargo, son útiles porque son rápidos de idear y a menudo dan buenas aproximaciones al óptimo.
También aparecen algoritmos codiciosos en el enrutamiento de la red. Utilizando el enrutamiento codicioso, 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 tanto de "cercanía") puede estar determinada por su ubicación física, como en el enrutamiento geográfico utilizado por las redes ad hoc . La ubicación también puede ser una construcción completamente artificial, como en el enrutamiento de mundos pequeños 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 máximo número de actividades que no choquen entre sí.
En el juego de computadora para Macintosh Crystal Quest, el objetivo es recolectar cristales, de manera similar al problema del viajante . El juego tiene un modo de demostración, donde el juego utiliza un algoritmo codicioso para ir a cada cristal. 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 de coincidencias 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 codiciosos, sin embargo, no se garantiza que encuentren la solución óptima.
Un algoritmo popular es el algoritmo ID3 para la construcción de árboles de decisión.
^ Gutin, Gregorio; Sí, Anders; Zverovich, Alexey (2002). "El viajante de comercio no debe ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemática Aplicada Discreta . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
^ Feige 1998
^ Papadimitriou y Steiglitz 1998
^ Nemhauser, Wolsey y Fisher 1978
^ Buchbinder y otros. 2014
^ Krause y Golovin 2014
^ "Conferencia 5: Introducción a los algoritmos de aproximación" (PDF) . Algoritmos avanzados (2IL45): notas del curso . Universidad Técnica de Eindhoven. Archivado (PDF) desde el original el 9 de octubre de 2022.
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, Gregorio; Sí, Anders; Zverovich, Alexey (2002). "El viajante de comercio no debe ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemática Aplicada Discreta . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
Bang-Jensen, Jørgen; Gutin, Gregorio; Sí, Anders (2004). "Cuando falla el algoritmo codicioso". Optimización discreta . 1 (2): 121–127. doi : 10.1016/j.disopt.2004.03.007 .
Bendall, Gareth; Margot, François (2006). "Resistencia de tipo codicioso de 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 del conjunto" (PDF) . Revista de la ACM . 45 (4): 634–652. doi :10.1145/285055.285059. S2CID 52827488. Archivado (PDF) desde el original el 9 de octubre de 2022.
Nemhauser, G.; Wolsey, Luisiana; Pescador, ML (1978). "Un 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, Morán; Naor, José (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ática Industrial y Aplicada. doi :10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Archivado (PDF) desde el original el 9 de octubre de 2022.
Krause, A.; Golovin, D. (2014). "Maximización de funciones submodulares". En Burdeos, L.; Hamadi, Y.; Kohli, P. (eds.). Tratabilidad: enfoques prácticos para problemas difíciles . Prensa de la Universidad de Cambridge. págs. 71-104. doi :10.1017/CBO9781139177801.004. ISBN 9781139177801.