5.1. Método general.
Los algoritmos divide y vencerás están dentro de los métodos descendentes.
- Empezar con el problema original y descomponer en pasos sucesivos en problemas de menor tamaño.
- Partiendo del problema grande, descendemos hacia problemas más sencillos.
La programación dinámica, por el contrario, es un método ascendente:
- Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.
Ejemplo. Algoritmo de Floyd, para el cálculo de los caminos mínimos entre cualquier par de nodos en un grafo.
- Calcular los caminos mínimos, pudiendo pasar por 1 nodo intermedio (el nodo 1), luego pudiendo pasar por los 2 primeros, ...
- Repetir hasta tener los caminos mínimos pudiendo pasar por cualquier nodo. Los resultados para los problemas pequeños se pueden guardar en la misma matriz de costes.