Algoritmo voraz

Un algoritmo voraz es aquel que , en cada paso, toma la decisión que es localmente óptima y, posteriormente, no reconsidera las decisiones anteriores. Los algoritmos voraces se utilizan a menudo para resolver problemas de optimización combinatoria . Si un problema de optimización depende únicamente de la solución parcial de un subproblema, podemos resolverlo de forma "voraz" considerando solo el subproblema localmente óptimo. En este sentido, un algoritmo voraz es un caso especial de un algoritmo de programación dinámica . Uriel Feige ^{[ 1 ]} señala que:

Los algoritmos voraces pueden considerarse la forma definitiva de programación dinámica, en la que solo se mantiene una solución parcial. Para que este enfoque funcione, el problema debe tener una estructura mucho más definida.

En muchos casos, un algoritmo voraz no produce una solución exacta, pero puede generar soluciones que se aproximan a una solución exacta en un tiempo razonable. ^{[ 2 ]}

Un ejemplo de un problema que admite una solución voraz exacta es el problema de selección de actividades . Dada una colección de tareas que se pueden realizar entre intervalos de tiempo asignados, el problema consiste en determinar el número máximo de tareas que se pueden realizar. Un algoritmo voraz en${\displaystyle O(n\log(n))}$que resuelve este problema ordena las tareas por hora de finalización y luego elige repetidamente la primera tarea que comienza después de que terminó la última tarea.

Muchos algoritmos clásicos en ciencias de la computación, como el algoritmo de codificación de Huffman , el algoritmo de Prim , el algoritmo de Kruskal y el algoritmo de Dijkstra , utilizan propiedades voraces en su diseño. Los matemáticos también utilizan con frecuencia estrategias voraces en demostraciones. Un ejemplo clásico es lo que Raphael Yuster denomina la demostración voraz ^{[ 3 ]} de que todo torneo en un grafo contiene un camino hamiltoniano .

Dado que no existe una definición formal de lo que es un algoritmo voraz, ^{[ 4 ]} no se conoce una caracterización completa de cuándo un problema admite un algoritmo voraz como solución. Sin embargo, se han identificado casos especiales. Jack Edmonds demostró que un algoritmo voraz puede utilizarse para resolver una clase de problemas de optimización combinatoria lineal con una estructura de matroide. ^{[ 5 ]}

Posteriormente, Bernhard Korte y László Lovász caracterizaron una clase más amplia de problemas de optimización al introducir la noción de greedoide . Esto permitió, por ejemplo, demostrar la optimalidad del algoritmo de Prim .

Los algoritmos que deshacen pasos anteriores no son voraces. Por ejemplo, el algoritmo de Gale-Shapley no es un algoritmo voraz, ya que, si bien construye una solución eligiendo el mejor emparejamiento actual, en el proceso las soluciones existentes pueden modificarse.

Una técnica utilizada para demostrar la optimalidad de los algoritmos voraces es el argumento de intercambio. ^{[ 6 ]} El argumento de intercambio demuestra que cualquier solución diferente de la solución voraz es, como máximo, tan buena como la solución voraz. Este patrón de prueba generalmente sigue estos pasos:

1. Supongamos que existe una solución óptima diferente de la solución voraz.
2. Consideremos el primer punto donde difieren las soluciones óptima y voraz.
3. Demuestra que intercambiar la opción óptima por la opción codiciosa en este punto no puede empeorar la solución codiciosa.
4. Concluya por inducción que la solución voraz es la óptima.

Ejemplos de cómo un algoritmo voraz puede no lograr la solución óptima.

Partiendo de A, un algoritmo voraz que intenta encontrar el máximo siguiendo la mayor pendiente encontrará el máximo local en "m", sin tener en cuenta el máximo global en "M".

Para alcanzar la suma más grande, en cada paso, el algoritmo voraz elegirá lo que parezca ser la opción inmediata óptima, por lo que elegirá 12 en lugar de 3 en el segundo paso, y no alcanzará la mejor solución, que contiene 99.

• En el problema de la mochila fraccionaria , se dispone de una lista de artículos con pesos y valores. El objetivo es elegir cantidades fraccionarias de cada artículo de manera que se maximice el valor total y el peso sea inferior a una restricción fija. A diferencia del problema de la mochila , que se sabe que es NP-difícil , el problema de la mochila fraccionaria admite un algoritmo voraz de tiempo polinomial.
• Existen instancias del problema de la moneda de Frobenius que admiten soluciones voraces. Sin embargo, en algunos casos, el algoritmo voraz no produce una solución óptima. ^{[ 7 ]}
• La búsqueda de coincidencia es un ejemplo de un algoritmo voraz aplicado a la aproximación de señales.
• Un algoritmo voraz 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 voraz es óptimo para cualquier número de círculos.
• En el aprendizaje mediante árboles de decisión , se suelen utilizar algoritmos voraces; sin embargo, no garantizan encontrar la solución óptima.
  • Un algoritmo popular de este tipo es el algoritmo ID3 para la construcción de árboles de decisión.
• Un algoritmo voraz construye la representación de Zeckendorf (o codificación de Fibonacci) de un número natural. Restando repetidamente el mayor número de Fibonacci menor o igual al número natural, se obtiene su representación de Zeckendorf. El algoritmo voraz se deriva de la prueba de existencia de la representación de Zeckendorf. La unicidad de la representación de Zeckendorf garantiza que ninguna otra suma de Fibonacci no consecutiva puede dar un resultado diferente.
• Fibonacci describió un algoritmo voraz para calcular fracciones egipcias .
• Los algoritmos voraces aparecen en el enrutamiento de redes . Mediante el enrutamiento voraz, un mensaje se reenvía al nodo vecino que está más cerca del destino. La noción de ubicación de un nodo (y, por lo tanto, su cercanía) puede determinarse 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 las tablas hash distribuidas .

La teoría de grafos es una fuente inagotable de algoritmos voraces. Los informáticos utilizan con frecuencia algoritmos voraces para calcular invariantes de grafos.

• El algoritmo de Dijkstra y el algoritmo de búsqueda A* relacionado son algoritmos voraces óptimos y verificables para la búsqueda en grafos y la búsqueda de la ruta más corta .
  • La búsqueda A* es condicionalmente óptima, lo que requiere una " heurística admisible " que no sobreestime los costos de la ruta.
• Los algoritmos de Kruskal y Prim son algoritmos voraces para construir árboles de expansión mínima de un grafo conexo dado . Siempre encuentran una solución óptima, que en general puede no ser única.
• Un algoritmo voraz construye un árbol de Huffman en codificación de Huffman .
• Los algoritmos de Sequitur y Lempel-Ziv-Welch son algoritmos voraces para la inducción de gramáticas .
• Un algoritmo voraz encuentra el conjunto independiente máximo en un árbol.

Los algoritmos voraces también se utilizan para encontrar cotas superiores para los números cromáticos ^{[ 8 ]} . Un ejemplo sencillo es la cota${\displaystyle \chi (G)\leq \Delta (G)+1}$obtenido por un algoritmo voraz. ^{[ 9 ]} Comenzamos tomando un vértice que no ha sido coloreado. Dado que tiene como máximo${\displaystyle \Delta (G)}$vecinos, como mucho${\displaystyle \Delta (G)}$Los colores se utilizan en vértices adyacentes, dejando un color libre para el vértice en cuestión.

Una solución al problema del viajante de comercio NP-completo se puede aproximar comenzando desde un conjunto de aristas vacío y luego agregando la siguiente arista más barata que es un subgrafo de un recorrido completo. Se ha demostrado que este algoritmo voraz produce como máximo${\displaystyle \Theta (\log n)}$veces más largo que el recorrido óptimo. ^{[ 10 ]}

Otro ejemplo es que una solución para el problema de la mochila 0-1 puede aproximarse utilizando el algoritmo voraz para el problema de la mochila fraccionaria . Se ha demostrado que este algoritmo voraz produce una solución con un valor al menos la mitad del de la solución óptima. ^{[ 11 ]}

Las soluciones para la maximización submodular se aproximan utilizando un algoritmo voraz que produce una solución al menos la mitad del valor de la solución óptima. ^{[ 12 ]}

Los problemas para los que se utilizan algoritmos voraces para proporcionar algoritmos de aproximación incluyen el problema de cobertura de conjuntos , el equilibrio de carga , el árbol de Steiner y el problema de conjuntos independientes ^{[ 13 ]} .

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