Un método constructivo que construye una solución paso a paso tomando en cada etapa la opción localmente óptima, empleado en optimización combinatoria, algoritmos de aproximación y pruebas de existencia cuando las decisiones locales conducen a una solución global aceptable.

Principio

En cada iteración elija la opción que parezca mejor según un criterio local (por ejemplo, mayor ganancia inmediata o menor coste inmediato) y confíe en una prueba —a menudo mediante argumentos de intercambio o estructura de matroides— que demuestra que estas elecciones locales se agregan en una solución global óptima o de calidad garantizada.

Demostración

El algoritmo de Kruskal para árboles recubridores mínimos añade repetidamente la arista de menor peso que no crea un ciclo; las elecciones locales de aristas mínimas producen un árbol recubridor globalmente mínimo debido a un argumento de corte-y-pega vinculado a propiedades de corte o a la estructura de matroides del grafo.

Aplicación incorrecta

Aplicar una regla voraz sin una prueba de corrección subyacente puede producir soluciones arbitrariamente malas; por ejemplo, seleccionar vorazmente por beneficio inmediato en la mochila sin considerar la capacidad futura conduce a totales subóptimos, salvo en el caso fraccionario o con estructuras especiales.

Consecuencia

Cuando están justificadas, las soluciones voraces son sencillas, rápidas y con frecuencia ofrecen soluciones óptimas o aproximaciones de factor constante con pruebas de corrección transparentes; también proporcionan pruebas constructivas de existencia en combinatoria.

Inversión

La perspectiva inversa busca primero la optimalidad global y deriva una regla de selección local que reproduciría la solución óptima, usando esto para diseñar estrategias voraces mediante la caracterización de condiciones locales necesarias de los óptimos.

Límite

Efectivo cuando el problema posee una propiedad matroideal, propiedad de elección voraz o cuando aplica un argumento de intercambio; fracasa en muchos problemas NP-duros que carecen de tal estructura o cuando las interacciones futuras hacen cortas las elecciones locales.

Tensión semántica

En tensión con programación dinámica y optimización global: voraz es local y rápido pero puede perder óptimos globales que programación dinámica o branch-and-bound encontrarían; cuando ambos aplican, voraz suele ofrecer mayor simplicidad y menor coste.

Síntesis

Los algoritmos voraces realizan elecciones localmente óptimas de forma repetida y están justificados cuando la estructura del problema (matroide, propiedad de intercambio o cota de aproximación demostrable) asegura que esas elecciones se combinan en una solución global casi óptima u óptima; sin tal estructura corren el riesgo de un rendimiento pobre.