Algoritmos vidos (glotones, voraces)Los algoritmos vidos son algoritmos en los que tomamos decisiones locales para llegar a una cantidad ptima global. En este sentido, son parecidos a los deprogramacin dinmica. La diferencia es que para resolver un problema con programacin dinmica, tomamos en cuenta todas las soluciones para los subproblemas anteriores y con esto encontramos la solucin ptima; mientras que para resolver un problema mediante un algoritmo vido, slo tomamos la solucin ptima del subproblema anterior y con esto calculamos la ptima actual (por lo que no necesitamos guardar datos).

Esto es, empezamos por el caso ms sencillo y en cada paso tomamos la decisin que resulte ms eficiente en ese momento, con lo que esperamos llegar a una solucin ptima global, sin reconsiderar opciones.

Los algoritmos vidos encuentran las soluciones mucho ms rpido que por programacin dinmica, y muchas veces que por cualquier otro mtodo. El problema es que, aunque el enfoque es generalmente fcil de implementar, en la mayora de las ocasiones falla por no tomar en cuenta todas las combinaciones. Es por esto que no es conveniente utilizarlo a menos de que estemos convencidos de que funciona (preferentemente con una demostracin).

Entre los algoritmos ms conocidos que utilizan un enfoque vido, se encuentran los de Dijkstra, Prim y Kruskal (secciones10.4y10.6) que funcionan en grficas.

A veces son utilizados para disear algoritmos heursticos para problemas NP-completo, con lo que podemos obtener una buena aproximacin de la solucin en poco tiempo. De acuerdo a la complejidad del problema, un enfoque vido nos puede dar una aproximacin suficientemente buena o, si queremos una respuesta ptima, podemos utilizarla para realizar podas en una bsqueda exhaustiva.Problema ejemplo

ConferenciaProblemaEs comn que las conferencias cientficas estn divididas en varias secciones simultneas. Por ejemplo, puede haber una seccin para computacin en paralelo, otra para visualizacin, otra para compresin de datos, y as sucesivamente.Es obvio que se necesita realizar el trabajo de varias secciones de forma simultnea para reducir el tiempo de la conferencia y tener suficiente tiempo para las comidas, tomar caf, y las discusiones informales. Sin embargo, es posible que se estn dando ponencias interesantes de forma simultnea en distintas secciones.Un participante ha escrito una tabla con los horarios de todas las ponencias que le interesan. Te ha pedido que encuentres la cantidad mxima de ponencias a los que puede asistir.EntradaLa primera lnea contiene el nmero 1 n 100000, que es la cantidad de ponencias interesantes. Cada una de las siguientesnlneas contiene a dos enterostsyteseparados por un espacio (1 ts