Python - Clases de algoritmos
Los algoritmos son pasos inequívocos que deberían darnos una salida bien definida procesando cero o más entradas. Esto conduce a muchos enfoques para diseñar y escribir los algoritmos. Se ha observado que la mayoría de los algoritmos se pueden clasificar en las siguientes categorías.
Algoritmos codiciosos
Los algoritmos codiciosos intentan encontrar una solución óptima localizada, que eventualmente puede conducir a soluciones optimizadas globalmente. Sin embargo, los algoritmos generalmente codiciosos no proporcionan soluciones optimizadas globalmente.
Por lo tanto, los algoritmos codiciosos buscan una solución fácil en ese momento sin considerar cómo afecta los pasos futuros. Es similar a cómo los humanos resuelven problemas sin pasar por los detalles completos de las entradas proporcionadas.
La mayoría de los algoritmos de redes utilizan el enfoque codicioso. Aquí hay una lista de algunos de ellos:
- Problema del vendedor ambulante
- Algoritmo de árbol de expansión mínimo de Prim
- Algoritmo de árbol de expansión mínimo de Kruskal
- Algoritmo de árbol de expansión mínimo de Dijkstra
Divide y conquistaras
Esta clase de algoritmos implica dividir el problema dado en subproblemas más pequeños y luego resolver cada uno de los subproblemas de forma independiente. Cuando el problema no puede subdividirse más, comenzamos a fusionar la solución de cada uno de los subproblemas para llegar a la solución del problema mayor.
Los ejemplos importantes de algoritmos de divide y vencerás son:
- Combinar ordenar
- Ordenación rápida
- Algoritmo de árbol de expansión mínimo de Kruskal
- Búsqueda binaria
Programación dinámica
La programación dinámica implica dividir el problema más grande en otros más pequeños, pero a diferencia de dividir y conquistar, no implica resolver cada subproblema de forma independiente. Más bien, los resultados de subproblemas más pequeños se recuerdan y se utilizan para subproblemas similares o superpuestos. En su mayoría, estos algoritmos se utilizan para la optimización. Antes de resolver el subproblema en cuestión, el algoritmo dinámico intentará examinar los resultados de los subproblemas previamente resueltos.
Los algoritmos dinámicos están motivados para una optimización general del problema y no para la optimización local.
Los ejemplos importantes de algoritmos de programación dinámica son:
- Serie de números de Fibonacci
- Problema de la mochila
- Torre de Hanoi