Divide y venceras

Capítulo 3 DIVIDE Y VENCERÁS

3.1 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. En nuestro contexto, Divide y Venceráses 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 lasimplementaciones 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 conuna 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 descrita anteriormente se refleja en el esquema general que presentamos a continuación:

106

TÉCNICAS DE DISEÑO DE ALGORITMOS

PROCEDUREDyV(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 elnú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 desimplificació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 reducirel 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 derecursió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...