Árbol de contenidos.
Mecanismos de resolución de algoritmos¶
Divide y vencerás¶
Definición¶
Divide y vencerás divide el problema principal en subproblemas independientes, resuelve cada subproblema por separado y luego combina los resultados para formar la solución del problema original.
Programación dinámica¶
Definición¶
La programación dinámica en contraste con Divide y vencerás utiliza una matriz que almacena resultados intermedios ya resueltos para evitar recalcular estos resultados, lo que reduce el tiempo de ejecución.
Algoritmos voraces¶
Definición¶
Los algoritmos voraces eligen una solución local óptima en cada paso con la esperanza de llegar a una solución general óptima.
- Descompone el problema en un conjunto de decisiones.
- Elige la más prometedora.
- No reconsideras las decisiones ya tomadas.
Back tracking¶
Definición¶
En back tracking se exploran todas las soluciones posible de manera sistemática para encontrar una solución o todas las soluciones válidas a un problema. Construye la solución paso a paso y abandona (retrocede) las soluciones parciales que no cumplen las condiciones del problema (las que no dan una solución válida).
Ramificación y poda¶
Definición¶
Se utiliza para resolver problemas de optimización. Este método consiste en dividir el problema original en subproblemas más pequeños (ramificación) y utilizar límites (cotas) para eliminar (podar) subproblemas que no pueden contener una solución mejor que la mejor solución encontrada hasta el momento.
Complejidad y notación asintótica¶
Cálculo de complejidades básicas¶
Ecuaciones de recurrencia¶
Tipos del Problema de la mochila¶
Conceptos clave¶
- Subestructura óptima o principio de optimalidad