Algoritmo codicioso

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.

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]

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 .

Esta sección necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo agregando citas de fuentes confiables en esta sección. El material sin fuentes puede ser cuestionado y eliminado. ( Junio ​​de 2018 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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

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 .

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]

Una función definida en subconjuntos de un conjunto se llama submodular si para cada tenemos que .${\estilo de visualización f}$${\estilo de visualización\Omega}$${\displaystyle S,T\subseteq \Omega}$${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$

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.${\estilo de visualización S}$${\estilo de visualización f}$${\estilo de visualización S}$${\estilo de visualización f}$${\displaystyle (1-1/e)\max _{X\subseteq \Omega }f(X)}$${\displaystyle (1-1/e)\aproximadamente 0,63}$

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 para los que el algoritmo voraz ofrece una garantía sólida, pero no una solución óptima, incluyen

• Cubierta del conjunto
• El problema del árbol de Steiner
• Equilibrio de carga ^[10]
• 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.

Esta sección necesita ser ampliada . Puedes ayudar agregándole algo. ( Junio ​​2018 )

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.

Si se puede demostrar que un algoritmo voraz produce el óptimo global para una clase de problema dada, 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 . Algunos ejemplos de estos algoritmos voraces 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 .

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 .

• 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.
• El algoritmo de Dijkstra y el algoritmo de búsqueda A* relacionado son algoritmos voraces verificablemente óptimos para la búsqueda de gráficos y la búsqueda de rutas más cortas .
  • La búsqueda A* 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 voraces para construir árboles de expansión mínima de un grafo conexo dado . Siempre encuentran una solución óptima, que puede no ser única en general.
• Los algoritmos Sequitur y Lempel-Ziv-Welch son algoritmos voraces para la inducción gramatical .

Wikimedia Commons tiene medios relacionados con Algoritmos voraces .

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