La técnica de divide y vencerás utilizada en algoritmos se basa en la descomposición de un problema en subproblemas del mismo tipo más pequeños, lo que permite disminuir su dificultad y encontrar la solución más fácilmente.
Para emplear este algoritmo lo que tenemos que hacer es descomponer el problema que tengamos entre manos en subproblemas más pequeños, ir haciendo una resolución recursiva de los subproblemas y combinar o utilizar las soluciones de esos subproblemas para encontrar la solución al problema planteado.
Este modo de resolver problemas utiliza el principio de inducción sobre los diversos ejemplares del problema, de esta manera supone solucionados los subproblemas y utiliza las soluciones de los mismos para componer la solución final del problema.
Un ejemplo de esta técnica es el algoritmo de Euclides del año 300 a.C. aprox. que calcula el Máximo Cómun Divisor de dos enteros.
Ejemplos que nos permiten entender mejor cómo funciona esta técnica de solucionar problemas es la ordenacion por fusión o mergesort que es un problema que consiste en que dado un vector de enteros tenemos que ir dividiéndolo y ordenando las mitades por separado, para una vez ordenados fusionarlos y obtener la solución final.
El puzzle tromino, la ordenación rápida o quicksort y el cálculo del mayor elemento de un vector son problemas en los que se puede ver cómo funciona esté esquema algorítmico de divide y vencerás para encontrar la solución.
Si queréis mas información sobre esta estrategia de divide y vencerás y así cómo la solución a los ejemplos citados no dudéis en ponerlo en los comentarios.
 |
| Divide y Vencerás |
No hay comentarios:
Publicar un comentario