## [Algoritmo Voraz](/es/node/60339) Definición 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 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 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 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 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 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 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 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 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.