Buscar en el sitio
Contacto
Analisisdisenodealgoritmo
E-mail: miguel-762011@hotmail.com
TEMA 3
DIVIDE Y VENCERAS
INTRODUCCIÓN
El término Divide y Vencerás en su acepción más amplia es algo más que una Técnica de diseño de algoritmos. De hecho, suele ser considerada una filosofía General para resolver problemas y de aquí que su nombre no sólo forme parte del Vocabulario informático, sino que también se utiliza en muchos otros ámbitos.
Divide y Vencerás es una técnica de diseño de algoritmos
que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño. Si los subproblemas son todavía relativamente grandes se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente. Ello naturalmente sugiere el uso de la recursión en las implementaciones de estos algoritmos.
La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:
1. En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño nk y donde 0 ≤ nk < n. A esta tarea se le conoce como división.
2. En segundo lugar han de resolverse independientemente todos los
Subproblemas, bien directamente si son elementales o bien de forma recursiva. 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, también denominados casos base.
3. Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.
El funcionamiento de los algoritmos que siguen la técnica de Divide y Vencerás
PROCEDURE DyV(x:TipoProblema):TipoSolucion;
VAR i,k,:CARDINAL;
s:TipoSolucion;
subproblemas: ARRAY OF TipoProblema;
subsoluciones:ARRAY OF TipoSolucion;
BEGIN
IF EsCasobase(x) THEN
s:=ResuelveCasoBase(x)
ELSE
k:=Divide(x,subproblemas);
FOR i:=1 TO k DO
subsoluciones[i]:=DyV(subproblemas[i])
END;
s:=Combina(subsoluciones)
END;
RETURN s
END DyV;
Hemos de hacer unas apreciaciones en este esquema sobre el procedimiento
Divide, sobre el número k que representa el número de subproblemas, y sobre el tamaño de los subproblemas, ya que de todo ello va a depender la eficiencia del algoritmo resultante.
En primer lugar, el número k debe ser pequeño e independiente de una entrada determinada. En el caso particular de los algoritmos Divide y Vencerás que
contienen sólo una llamada recursiva, es decir k = 1, hablaremos de algoritmos de simplificación. Tal es el caso del algoritmo recursivo que resuelve el cálculo del factorial de un número, que sencillamente reduce el problema a otro subproblema del mismo tipo de tamaño más pequeño. También son algoritmos de simplificación
el de búsqueda binaria en un vector o el que resuelve el problema del k-ésimo elemento.
La ventaja de los algoritmos de simplificación es que consiguen reducir el
tamaño del problema en cada paso, por lo que sus tiempos de ejecución suelen ser muy buenos (normalmente de orden logarítmico o lineal). Además pueden admitir
una mejora adicional, puesto que en ellos suele poder eliminarse fácilmente la recursión mediante el uso de un bucle iterativo, lo que conlleva menores tiempos de ejecución y menor complejidad espacial al no utilizar la pila de recursión, aunque por contra, también en detrimento de la legibilidad del código resultante.
Por el hecho de usar un diseño recursivo, los algoritmos diseñados mediante la técnica de Divide y Vencerás van a heredar las ventajas e inconvenientes que la recursión plantea:
a) Por un lado el diseño que se obtiene suele ser simple, claro, robusto y elegante, lo que da lugar a una mayor legibilidad y facilidad de depuración y mantenimiento del código obtenido.
b) Sin embargo, los diseños recursivos conllevan normalmente un mayor tiempo de ejecución que los iterativos, además de la complejidad espacial que puede representar el uso de la pila de recursión.