Algoritmos golosos

Los algoritmos golosos son aquellos que resuelven el problema basándose en las heurísticas. Una heurística es una función que evalúa las distintas alternativas de soluciones parciales, pero de manera exclusivamente local. Es decir, prioriza lo que en ese momento parece ser la mejor decisión, sin preocuparse si eso es, en términos globales, efectivamente lo mejor.

La lógica esta en aproximarse a la solución mas optima, tomando decisiones que aparentemente son las mas optimas. Esto, en la practica, no siempre sucede. A diferencia del backtracking, los algoritmos golosos no "vuelven para atrás", no corrigen sus decisiones si no fueron las mejores.

Una forma de verificar si un enfoque goloso funcionaria en un problema, es verificar la subestructura optima. Se dice que un problema tiene subestructura optima si una solución optima de dicho problema contiene soluciones optimas a los subproblemas que se pueden formar a partir del problema original. Es decir, si la solución final incluye soluciones parciales que, localmente, eran efectivamente las mejores.