Algoritmos voraces

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Algoritmos voraces (greedy algorithms) 
Los algoritmos voraces son algoritmos que toman la 
mejor decisión local en cada paso, con la esperanza de 
llegar a la mejor solución global. 
Ideas principales para estudiantes de universidad 
Para los estudiantes de universidad, es importante 
comprender las siguientes ideas principales sobre los 
algoritmos voraces: 
• Los algoritmos voraces toman decisiones locales 
óptimas. 
• Los algoritmos voraces pueden no encontrar la 
solución óptima global. 
• Los algoritmos voraces son sencillos de 
implementar. 
Recomendaciones para estudiantes de universidad 
Para los estudiantes de universidad que están 
aprendiendo sobre los algoritmos voraces, se 
recomiendan las siguientes actividades: 
• Practicar mucho. La mejor manera de aprender 
sobre los algoritmos voraces es practicar con 
frecuencia. 
• Buscar ayuda cuando sea necesario. Si tienes 
problemas para entender un concepto o resolver 
un problema, no dudes en pedir ayuda a un 
profesor o a un tutor. 
• Participar en proyectos. Trabajar en proyectos te 
ayudará a aplicar tus conocimientos sobre los 
algoritmos voraces en el mundo real. 
Explicación 
Los algoritmos voraces toman decisiones locales 
óptimas en cada paso. Esto significa que, en cada 
paso, el algoritmo elige la opción que parece ser la 
mejor en ese momento. 
Los algoritmos voraces pueden no encontrar la solución 
óptima global. Esto se debe a que los algoritmos 
voraces solo consideran las opciones locales. 
Los algoritmos voraces 
son sencillos de 
implementar. Esto se 
debe a que los 
algoritmos voraces solo 
requieren tomar la mejor 
decisión local en cada 
paso. 
Ejemplos de algoritmos 
voraces 
Algunos ejemplos de 
algoritmos voraces 
incluyen: 
• El problema del 
cambio: Este 
problema 
consiste en 
encontrar la 
combinación de 
monedas más 
pequeña que 
suma una 
cantidad 
determinada de 
dinero. Un 
algoritmo voraz 
para este 
problema 
seleccionaría 
siempre la 
moneda de 
mayor valor que 
pueda ser 
utilizada para 
alcanzar la 
cantidad objetivo. 
• El problema de la 
mochila: Este 
problema 
consiste en 
encontrar la 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
combinación de objetos que tiene el mayor valor 
y que cabe en una mochila de un tamaño 
limitado. Un algoritmo voraz para este problema 
seleccionaría siempre el objeto de mayor valor 
que pueda ser incluido en la mochila sin exceder 
el límite de tamaño. 
• El problema del camino más corto: Este 
problema consiste en encontrar el camino más 
corto entre dos puntos en un gráfico. Un 
algoritmo voraz para este problema seleccionaría 
siempre el arco de menor peso que conecta el 
punto actual con un punto no visitado. 
Ventajas y desventajas de los algoritmos voraces 
Ventajas: 
• Los algoritmos voraces son sencillos de 
implementar. 
• Los algoritmos voraces pueden ser eficientes 
para problemas pequeños. 
Desventajas: 
• Los algoritmos voraces pueden no encontrar la 
solución óptima global. 
• Los algoritmos voraces pueden ser ineficientes 
para problemas grandes. 
Conclusión 
Los algoritmos voraces son una herramienta útil para 
resolver problemas simples. Sin embargo, los 
algoritmos voraces pueden no encontrar la solución 
óptima global para problemas grandes.