Algoritmo codicioso

Secuencia de elecciones localmente óptimas.

Los algoritmos codiciosos determinan la cantidad mínima de monedas que se deben dar al realizar el cambio. Estos son los pasos que la mayoría de la gente seguiría para emular un algoritmo codicioso para representar 36 centavos usando solo monedas con valores {1, 5, 10, 20}. La moneda de mayor valor, menor que el cambio restante adeudado, es el óptimo local. (En general, el problema de hacer cambios requiere programación dinámica para encontrar una solución óptima; sin embargo, la mayoría de los sistemas monetarios son casos especiales donde 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 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 . ${\displaystyle f}$ ${\displaystyle \Omega }$ ${\displaystyle S,T\subseteq \Omega }$ ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$

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. ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle (1-1/e)\max _{X\subseteq \Omega }f(X)}$ ${\displaystyle (1-1/e)\approx 0.63}$

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

• Establecer cubierta
• El problema del árbol de Steiner
• Equilibrio de carga ^[9]
• conjunto independiente

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.

Si se puede demostrar que un algoritmo codicioso produce el óptimo global para una clase de problema determinada, normalmente se convierte en el método elegido porque es más rápido que otros métodos de optimización como la programación dinámica . Ejemplos de algoritmos tan codiciosos son el algoritmo de Kruskal y el algoritmo de Prim para encontrar árboles de expansión mínimos y el algoritmo para encontrar árboles de Huffman óptimos .

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.
• El algoritmo de Dijkstra y el algoritmo de búsqueda A* relacionado son algoritmos codiciosos verificablemente óptimos para la búsqueda de gráficos y la búsqueda de la ruta más corta .
  • Una búsqueda* es condicionalmente óptima y requiere una " heurística admisible " que no sobreestime los costos de la ruta.
• El algoritmo de Kruskal y el algoritmo de Prim son algoritmos codiciosos para construir árboles de expansión mínimos de un gráfico conectado dado . Siempre encuentran una solución óptima, que puede no ser única en general.
• Los algoritmos Sequitur y Lempel-Ziv-Welch son algoritmos codiciosos para la inducción gramatical .

Ver también

• Portal de matemáticas

• Búsqueda de mejor primero
• Estrategia codiciosa de Epsilon
• Algoritmo codicioso para fracciones egipcias
• fuente codiciosa
• Montañismo
• Efecto horizonte
• Matroide

Referencias

1. Negro, Paul E. (2 de febrero de 2005). "algoritmo codicioso". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST) . Consultado el 17 de agosto de 2012 .
2. Cormen et al. 2001, cap. dieciséis
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 .
4. Feige 1998
5. Papadimitriou y Steiglitz 1998
6. Nemhauser, Wolsey y Fisher 1978
7. Buchbinder y otros. 2014
8. Krause y Golovin 2014
9. "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.
• Papadimitriou, Christos H .; Steiglitz, Kenneth (1998). Optimización combinatoria: algoritmos y complejidad . Dover.

enlaces externos

• "Algoritmo codicioso", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Regalo, Noé. "Ejemplo de moneda codiciosa de Python".