Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

.

En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original.

En programación dinámica, los subproblemas en que se divide el problema original no son independientes, en el sentido siguiente: los subproblemas comparten subproblemas entre ellos. Por tanto, una solución de divide y vencerás resolvería repetidas veces esos subproblemas compartidos, haciendo más trabajo del necesario. En programación dinámica se utiliza la técnica de la memorialización (memoization) para almacenar y reutilizar las soluciones de los subproblemas comunes, evitando resolverlos más de una vez.

Comentarios