Algoritmos: Divide y venceras
Definición:
Se puede definir como una técnica de diseño de algoritmos.
Pasos para la solución de problemas aplicado esta técnica:
Paso 1 (Dividir):
El problema debe plantearse de tal forma que permita subdividido en 𝒌 problemas del mismo tipo pero de menor tamaño.
Entonces si se tiene un problema de tamaño ｎ entonces se tiene que lograr dividir el problema en k subproblemas pero teniendo en cuenta que 1 ≤ 𝒌 ≤ ｎ es decir que 𝒌 como mínimo puede ser 1 y como máximo puede ser el tamaño del subproblema.
El tamaño del subproblema es ｎk pero 0 ≤ ｎk ≤ ｎ es decir que ｎk que como mínimo puede ser 0 y como máximo puede ser ｎ.
Teniendo en cuenta todo lo que se ha dicho por eso se le dice que este paso se le llama dividir.
Por que se entiende que cada vez el suproblema se va a estar en otro mas pequeño que el problema anterior.
Paso 2 :
En este paso hay que resolver los subproblemas ya si sea un caso elemental o si es necesario subdividirlo en otros subproblema aplicando recursion.
Se describe en el libro:
"El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos elementales" Técnicas de Diseño de Algoritmos : Rosa Guerequeta y Antonio Vallecillo
Los casos elementales o los también llamados casos base, son los casos mas simples o el problema mas simple o como se les llama en matemáticas las raíces del problema.
Paso 3:
En este punto se unen todas las soluciones de cada subproblema para asi obtener la solucion del problema original.
Bibliográfica
- Técnicas de Diseño de Algoritmos : Rosa Guerequeta y Antonio Vallecillo