Algoritmos voraces

Los algoritmos voraces construyen una solución de forma incremental al tomar repetidamente la elección que parece mejor en el paso actual, y son correctos precisamente cuando tales elecciones localmente óptimas conducen de manera demostrable a una solución globalmente óptima.

Definition

Un algoritmo voraz construye una solución a través de una secuencia de elecciones, cada una elegida para optimizar algún criterio local, sin revisar nunca las elecciones anteriores; es correcto solo cuando las elecciones localmente óptimas producen un resultado globalmente óptimo.

Scope

Este tema abarca el paradigma voraz: la propiedad de elección voraz y la subestructura óptima que lo justifican, las técnicas de prueba estándar (argumentos de intercambio y el marco de matroides), y algoritmos voraces canónicos que incluyen la codificación de Huffman, árboles de expansión mínima (Kruskal y Prim), los caminos más cortos de Dijkstra y la programación de intervalos. También aborda cuándo las estrategias voraces sirven solo como heurísticas de aproximación en lugar de métodos exactos.

Core questions

• ¿Qué es la propiedad de elección voraz y cómo se demuestra para un problema dado?
• ¿Cómo demuestra un argumento de intercambio que una elección voraz es segura?
• ¿Qué problemas tienen una estructura de matroide que garantiza la optimalidad voraz?
• ¿Cuándo es un método voraz solo una aproximación en lugar de un algoritmo exacto?
• ¿Cómo se compara el algoritmo voraz con la programación dinámica para el mismo problema?

Key concepts

• propiedad de elección voraz
• subestructura óptima
• argumento de intercambio
• matroides
• codificación de Huffman
• árbol de expansión mínima
• programación de intervalos
• problema de la mochila fraccional

Key theories

Propiedad de elección voraz y argumentos de intercambio

Un problema admite una solución voraz cuando una solución globalmente óptima siempre puede modificarse para que concuerde con la primera elección voraz sin pérdida de optimalidad; los argumentos de intercambio (o 'el voraz se mantiene a la cabeza') formalizan esto.

Matroides y optimalidad voraz

Cuando las soluciones factibles forman los conjuntos independientes de un matroide ponderado, el algoritmo voraz siempre encuentra un conjunto independiente de peso máximo; esto unifica resultados como la optimalidad del algoritmo de árbol de expansión mínima de Kruskal.

Clinical relevance

Los algoritmos voraces impulsan sistemas ampliamente utilizados: la codificación de Huffman en formatos de compresión de datos, los algoritmos de árbol de expansión mínima en el diseño de redes, el algoritmo de Dijkstra en el enrutamiento y la navegación, y la programación voraz y las heurísticas de cobertura de conjuntos en sistemas operativos y asignación de recursos.

History

El razonamiento voraz aparece en resultados clásicos como los algoritmos de árbol de expansión mínima de Kruskal (1956) y Prim (1957), los códigos de prefijo óptimos de Huffman (1952) y el algoritmo de caminos más cortos de Dijkstra (1959). La explicación basada en la teoría de matroides de cuándo los métodos voraces tienen éxito fue desarrollada por Edmonds y otros en las décadas de 1960 y 1970.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

¿Por qué el algoritmo voraz funciona para el problema de la mochila fraccional pero no para el problema de la mochila 0/1?

En el problema de la mochila fraccional, los elementos se pueden dividir, por lo que tomar primero el elemento de mayor valor por peso es siempre seguro y demostrablemente óptimo. En el problema de la mochila 0/1, los elementos son indivisibles, la elección voraz puede impedir una mejor combinación y se requiere programación dinámica para un óptimo exacto.

¿Cómo se demuestra que un algoritmo voraz es correcto?

Las dos técnicas estándar son el argumento de intercambio, que transforma cualquier solución óptima en la voraz sin empeorarla, y el argumento 'el voraz se mantiene a la cabeza', que muestra que la solución parcial voraz es al menos tan buena como cualquier otra en cada paso. La teoría de matroides proporciona una condición suficiente general.