PDF de programación - Capitulo 5 - El esquema Divide y vencerás

El esquema “Divide y vencerás” 1

Capítulo 5

Divide et impera
Julio César (100 a.C.-44 a.C)

Resumen: En este tema se presenta el esquema algorítmico Divide y vencerás, que
es un caso particular del diseño recursivo, y se ilustra con ejemplos significativos en
los que la estrategia reporta beneficios claros. Se espera del alumno que incorpore este
método a sus estrategias de resolución de problemas.

1.

?

?

?

?

Introducción

En este capítulo iniciamos la presentación de un conjunto de esquemas algorítmicos
que pueden emplearse como estrategias de resolución de problemas. Un esquema
puede verse como un algoritmo genérico que puede resolver distintos problemas. Si
se concretan los tipos de datos y las operaciones del esquema genérico con los tipos
y operaciones específicos de un problema concreto, tendremos un algoritmo para
resolver dicho problema.

Además de divide y vencerás, este curso veremos el esquema de vuelta atrás. En cursos
posteriores aparecerán otros esquemas con nombres propios tales como el método
voraz, el de programación dinámica y el de ramificación y poda. Cada uno de ellos
resuelve una familia de problemas de características parecidas.

Los esquemas o métodos algorítmicos deben verse como un conjunto de algoritmos
prefabricados que el diseñador puede ensayar ante un problema nuevo. No hay ga-
rantía de éxito pero, si se alcanza la solución, el esfuerzo invertido habrá sido menor
que si el diseño se hubiese abordado desde cero.

El esquema divide y vencerás (DV) consiste en descomponer el problema dado en
uno o varios subproblemas del mismo tipo, el tamaño de cuyos datos es una fracción
del tamaño original. Una vez resueltos los subproblemas por medio de la aplicación
recursiva del algoritmo, se combinan sus resultados para construir la solución del
problema original. Existirán uno o más casos base en los que el problema no se

1Ricardo Peña es el autor principal de este tema. Modificado por Clara Segura en el curso 2013-14.

97

98

?

?

?

?

?

Recordemos que la solución de la misma era:

Estructura de Datos y Algoritmos

Capítulo 5. Divide y Vencerás

subdivide más y se resuelve, o bien directamente si es sencillo, o bien utilizando un
algoritmo distinto.

Aparentemente estas son las características generales de todo diseño recursivo y de
hecho el esquema DV es un caso particular del mismo. Para distinguirlo de otros
diseños recursivos que no responden a DV se han de cumplir las siguientes condiciones:

Los subproblemas han de tener un tamaño que sea una fracción del tamaño
original (un medio, un tercio, etc . . . ). No basta simplemente con que sean más
pequeños.
Los subproblemas se generan exclusivamente a partir del problema original. En
algunos diseños recursivos, los parámetros de una llamada pueden depender de
los resultados de otra previa. En el esquema DV, no.
La solución del problema original se obtiene combinando los resultados de los
subproblemas entre sí, y posiblemente con parte de los datos originales. Otras
posibles combinaciones no encajan en el esquema.
El (los) caso(s) base no son necesariamente los casos triviales. Como veremos
más adelante podría utilizarse como caso base (incluso debería utilizarse en
ocasiones) un algoritmo distinto al algoritmo recursivo DV.

Puesto en forma de código, el esquema DV tiene el siguiente aspecto:
template <class Problema, class Solución>
Solución divide-y-vencerás (Problema x) {
Problema x_1,...,x_k;
Solución y_1,...,y_k;

if (base(x))

return método-directo(x);

(x_1,..., x_k) = descomponer(x);
for (i=1; i<=k; i++)

y_i = divide-y-vencerás(x_i);
return combinar(x, y_1,..., y_k);

else {

}

}

Los tipos Problema, Solución, y los métodos base, método-directo, descomponer
y combinar, son específicos de cada problema resuelto por el esquema.

Para saber si la aplicación del esquema DV a un problema dado resultará en una
solución eficiente o no, se deberá utilizar la recurrencia vista en el Capítulo 4 en la
que el tamaño del problema disminuía mediante división:

T (n) =⇢ c1
T (n) =8<:

a ⇤ T (n/b) + c ⇤ nk

si 0  n < n0
si n n0

O(nk)
O(nk ⇤ log n)
O(nlogb a)

si a < bk
si a = bk
si a > bk

2. Ejemplos de aplicación del esquema con éxito

99

?

Para obtener una solución eficiente, hay que conseguir a la vez:

que el tamaño de cada subproblema sea lo más pequeño posible, es decir, ma-
ximizar b.
que el número de subproblemas generados sea lo más pequeño posible, es decir,
minimizar a.
que el coste de la parte no recursiva sea lo más pequeño posible, es decir mini-
mizar k.

?

La recurrencia puede utilizarse para anticipar el coste que resultará de la solución
DV, sin tener por qué completar todos los detalles. Si el coste sale igual o peor que
el de un algoritmo ya existente, entonces no merecerá la pena aplicar DV.

2. Ejemplos de aplicación del esquema con éxito

?

?

?

?

?

Algunos de los algoritmos recursivos vistos hasta ahora encajan perfectamente en el
esquema DV.
La búsqueda binaria en un vector ordenado vista en el Cap. 4 es un primer ejemplo.
En este caso, la operación descomponer selecciona una de las dos mitades del vector
y la operación combinar es vacía. Obteníamos los siguientes parámetros de coste:
b = 2 Tamaño mitad del subvector a investigar en cada llamada recursiva.
a = 1 Un subproblema a lo sumo.
k = 0 Coste constante de la parte no recursiva.
dando un coste total O(log n).
La ordenación mediante mezcla o mergesort también responde al esquema: la
operación descomponer divide el vector en dos mitades y la operación combinar
mezcla las dos mitades ordenadas en un vector final. Los parámetros del coste son:
b = 2 Tamaño mitad de cada subvector.
a = 2 Siempre se generan dos subproblemas.
k = 1 Coste lineal de la parte no recursiva (la mezcla).
dando un coste total O(n log n).
La ordenación rápida o quicksort, considerando solo el caso mejor, también res-
ponde al esquema. La operación descomponer elige el pivote, particiona el vector
con respecto a él y lo divide en dos mitades. La operación combinar en este caso
es vacía. Los parámetros del coste son:
b = 2 Tamaño mitad de cada subvector.
a = 2 Siempre se generan dos subproblemas.
k = 1 Coste lineal de la parte no recursiva (la partición).
dando un coste total O(n log n).
La comprobación en un vector v estrictamente ordenado de si existe un índice i
tal que v[i] = i (ver la sección de problemas del Cap. 4) sigue un esquema similar
al de la búsqueda binaria:

Facultad de Informática - UCM

100

?

Capítulo 5. Divide y Vencerás

b = 2 Tamaño mitad del subvector a investigar en cada llamada recursiva.
a = 1 Un subproblema a lo sumo.
k = 0 Coste constante de la parte no recursiva.

dando un coste total O(log n).

Un problema históricamente famoso es el de la solución DV a la transformada discreta
de Fourier (DFT), dando lugar al algoritmo conocido como transformada rápida
de Fourier, o FFT (J.W. Cooley y J.W. Tukey, 1965). La transformada discreta
convierte un conjunto de muestras de amplitud de una señal, en el conjunto de
frecuencias que resultan del análisis de Fourier de la misma. Esta transformación
y su inversa (que se realiza utilizando el mismo algoritmo DFT) tienen gran interés
práctico pues permiten filtrar frecuencias indeseadas (p.e. ruido) y mejorar la calidad
de las señales de audio o de vídeo.
La transformada en esencia multiplica una matriz n ⇥ n de números complejos por
un vector de longitud n de coeficientes reales, y produce otro vector de la misma
longitud. El algoritmo clásico realiza esta tarea del modo obvio y tiene un coste
O(n2). La FFT descompone de un cierto modo el vector original en dos vectores de
tamaño n/2, realiza la FFT de cada uno, y luego combina los resultados de tamaño
n/2 para producir un vector de tamaño n. Las dos partes no recursivas tienen coste
lineal, dando lugar a un algoritmo FFT de coste O(n log n). El algoritmo se utilizó
por primera vez para analizar un temblor de tierra que tuvo lugar en Alaska en 1964.
El algoritmo clásico empleó 26 minutos en analizar la muestra, mientras que la FFT
de Cooley y Tukey lo hizo en 6 segundos.

3. Problema de selección

?

?

?

?

Dado un vector v de n elementos que se pueden ordenar y un entero 1  k  n, el
problema de selección consiste en encontrar el k-ésimo menor elemento.

El problema de encontrar la mediana de un vector es un caso particular de este
problema en el que se busca el elemento dn/2e-ésimo del vector en el caso de estar
ordenado (en los vectores de C++ corresponde a la posición (n 1) ÷ 2).
Una primera idea para resolver el problema consiste en ordenar el vector y tomar
el elemento v[k], lo cual tiene la complejidad del algoritmo de ordenación utilizado.
Nos preguntamos si podemos hacerlo más eficientemente.

Otra posibilidad es utilizar el algoritmo partición que vimos en el Capítulo 4 con
algún elemento del vector:

Si la posición p donde se coloca el pivote es igual a k, entonces v[p] es el elemento
que estamos buscando.
Si k < p entonces podemos pasar a buscar el k-ésimo elemento en las posiciones
anteriores a p, ya que en ellas se encuentran los elementos menores o iguales que
v[p] y v[p] es el p-ésimo elemento del vector.
Si k > p entonces podemos pasar a buscar el k-ésimo elemento en las posiciones
posteriores a p, ya que en ellas se encuentran los elementos mayores o iguales
que v[p] y v[p] es el p-ésimo elemento del vector.

Estructura de Datos y Algoritmos

3. Problema de selección

101

?

?

Al igual que hemos hecho en anteriores ocasiones generalizamos el problema aña-
diendo dos parámetros adicionales a y b tales que 0  a  b  long(v) 1, que nos
indican la parte del vector que nos interesa en cada momento. La llamada inicial que
deseamos es seleccion(v,0,long(v)-1,k).
En esta versión del algoritmo la posición k es una posición absoluta dentro del vector.
Se puede escribir una versión alternativa en la que k hace referencia a la posición
relativa dentro del subvector que se está tratando.

TElem seleccion1(TElem v[], int a, int b, int k)
// Pre : 0<