Algoritmo codicioso - Greedy algorithm
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. En muchos problemas, una estrategia codiciosa no produce una solución óptima, pero una heurística codiciosa puede producir soluciones locales óptimas que se aproximan a una solución globalmente óptima en un período de tiempo razonable.
Por ejemplo, una estrategia codiciosa para el problema del vendedor ambulante (que es de alta complejidad computacional) es la siguiente heurística: "En cada paso del viaje, visite 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 a un problema tan complejo requiere típicamente muchos pasos irrazonablemente. En la optimización matemática, los algoritmos codiciosos resuelven de manera óptima problemas combinatorios que tienen las propiedades de las matroides y dan aproximaciones de factor constante a los problemas de optimización con la estructura submodular.
Detalles específicos
En general, los algoritmos codiciosos tienen cinco componentes:
- Un conjunto de candidatos, a partir del cual se crea una solución.
- Una función de selección, que elige al mejor candidato para agregar a la solución.
- Una función de viabilidad, que se utiliza para determinar si un candidato puede utilizarse para contribuir a una solución.
- Una función objetivo, que asigna un valor a una solución, o una solución parcial, y
- Una función de solución, que indicará cuándo hemos descubierto una solución completa.
Los algoritmos codiciosos producen buenas soluciones en algunos problemas matemáticos , pero no en otros. La mayoría de los problemas para los que trabajan tendrán dos propiedades:
- Propiedad de elección codiciosa
- Podemos tomar la decisión que nos parezca mejor en este momento y luego resolver los subproblemas que surjan más tarde. La elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta ahora, pero no de las elecciones futuras o de todas las soluciones al subproblema. De manera iterativa, hace una elección codiciosa tras otra, reduciendo cada problema dado a uno más pequeño. En otras palabras, un algoritmo codicioso nunca reconsidera sus opciones. Ésta es la principal diferencia con la programación dinámica , que es exhaustiva y está garantizada para 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 presenta una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas".
Casos de fracaso
Los algoritmos codiciosos no logran producir la solución óptima para muchos otros problemas e incluso pueden producir la única peor solución posible . Un ejemplo es el problema del viajante de comercio 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 único. Para ver otros posibles ejemplos, consulte el efecto horizonte .
Tipos
Los algoritmos codiciosos se pueden caracterizar como "miopes" y también como "no recuperables". Son ideales solo para problemas que tienen una 'subestructura óptima'. A pesar de esto, para muchos problemas simples, los algoritmos más adecuados son codiciosos. Sin embargo, es importante tener en cuenta que el algoritmo codicioso se puede utilizar como un algoritmo de selección para priorizar opciones dentro de una búsqueda o un algoritmo de bifurcación y vinculación. Hay algunas variaciones del algoritmo codicioso:
- Algoritmos codiciosos puros
- 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, por lo que las preguntas naturales son:
- ¿Para qué problemas funcionan de manera óptima los algoritmos codiciosos?
- ¿Para qué problemas garantizan los algoritmos codiciosos 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 matroids , así como para problemas específicos, como la cobertura de conjuntos .
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 un matroide, entonces el algoritmo codicioso apropiado lo resolverá de manera óptima.
Funciones submodulares
Una función definida en subconjuntos de un conjunto se llama submodular si para cada tenemos eso .
Supongamos que uno quiere encontrar un conjunto que maximice . El algoritmo codicioso, que construye un conjunto agregando incrementalmente el elemento que más aumenta en cada paso, produce como salida un conjunto que es al menos . 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, en la salida, aunque a menudo se requieren ligeras variaciones en el algoritmo codicioso. Consulte para obtener una descripción general.
Otros problemas con las garantías
Otros problemas para los que el algoritmo codicioso 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 codiciosos generalmente (pero no siempre) no logran encontrar la solución óptima globalmente porque generalmente no operan de manera exhaustiva en todos los datos. Pueden comprometerse con ciertas opciones demasiado pronto, lo que les impide encontrar la mejor solución general más adelante. Por ejemplo, todos los algoritmos de coloración codiciosos 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 pensar 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 de elección porque es más rápido que otros métodos de optimización como la programación dinámica . Ejemplos de este tipo de algoritmos codiciosos son el algoritmo de Kruskal y el algoritmo de Prim para encontrar árboles de expansión mínima y el algoritmo para encontrar óptimos árboles de Huffman .
Los algoritmos codiciosos también aparecen en el enrutamiento de la red . Mediante el enrutamiento codicioso, se reenvía un mensaje al nodo vecino que está "más cerca" del destino. La noción de la ubicación de un nodo (y por lo 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 mundo pequeño y la tabla hash distribuida .
Ejemplos de
- 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 chocan entre sí.
- En el juego de computadora para Macintosh Crystal Quest, el objetivo es recolectar cristales, de una manera similar al problema del vendedor ambulante . El juego tiene un modo de demostración, donde el juego usa 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 a menudo termina 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 maximizan 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 , los algoritmos codiciosos se utilizan comúnmente, sin embargo, no se garantiza que encuentren la solución óptima.
- Uno de estos algoritmos populares es el algoritmo ID3 para la construcción del árbol de decisiones.
-
El algoritmo de Dijkstra y el algoritmo de búsqueda A * relacionado son algoritmos codiciosos óptimos y comprobables 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 sobrestime los costos de la ruta.
- El algoritmo de Kruskal y el algoritmo de Prim son algoritmos codiciosos para la construcción de árboles de expansión mínima de un determinado grafo conexo . Siempre encuentran una solución óptima, que puede no ser única en general.
Ver también
Referencias
Fuentes
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "16 algoritmos codiciosos" . Introducción a los algoritmos . MIT Press. págs. 370–. ISBN 978-0-262-03293-3.
- Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "El vendedor ambulante no debe 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 codicioso falla" . Optimización discreta . 1 (2): 121-127. doi : 10.1016 / j.disopt.2004.03.007 .
- Bendall, Gareth; Margot, François (2006). "Resistencia avariciosa 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 .
- Nemhauser, G .; Wolsey, LA; Fisher, ML (1978). "Un análisis de aproximaciones para maximizar las funciones del conjunto submodular — 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.
- 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.
enlaces externos
- "Algoritmo codicioso" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Regalo, Noah. "Ejemplo de moneda codiciosa de Python" .