Greedy: conceptos, subestructura óptima y criterios de selección

Apuntes

TEORÍA DE ALGORITMOS 1 Metodología greedy Por: ING. VÍCTOR DANIEL PODBEREZSKI vpodberezski@fi.uba.ar 1 Introducción Cuando nos enfrentamos a un problema complejo una práctica que suele buscarse es descomponer el mismo en partes más pequeñas. De esa forma enfrentaremos subproblemas menores que podemos resolver en forma más sencilla. Una consecuencia de esa separación es la necesidad de generar un mecanismo para interconectar y jerarquizar las partes. La solución de un subproblema puede ser requerido para atacar a otro. El tratamiento del conjunto de los subproblemas nos dará la solución global del problema original. La mayoría de los paradigmas de resolución de problemas enfrentan esta separación e interconexión de diferentes maneras. Los conocidos como algoritmos codiciosos (Greedy) son tal vez los más fáciles de producir entre ellos. Esta familia de algoritmos se utilizan para resolver problemas de optimización. Intentan por lo tanto maximizar o minimizar alguna cantidad durante su ejecución. El algoritmo realiza una división jerárquica en subproblemas cuya resolución habilita un nuevo subproblema a resolver. El proceso es en general iterativo. En cada subproblema se aplica un cri...