PDF de programación - Capitulo 2 - La técnica Divide y Vencerás

Capitulo 2
La técnica Divide y Vencerás



Introducción
Divide y Vencerás es una técnica para diseñar algoritmos que consiste en descomponer el
caso del problema que queremos resolver en un número de subproblemas menores del
mismo problema, resolviendo sucesiva e independientemente cada uno de ellos mediante
un algoritmo que suponemos existe, al que en lo sucesivo referiremos como “básico”, y des-
pués combinando las soluciones así obtenidas de modo que se obtenga la solución del pro-
blema inicial. Si el problema de partida lo notamos P, {PBiB , i∈I} representa la colección de
subproblemas en la que dividimos P, {SiB , i∈I} la de sus correspondientes soluciones y S la
combinación de esas soluciones de los subproblemas, el siguiente diagrama refleja como se
desarrollaría un algoritmo Divide y Vencerás



A pesar de la sencillez del método que describe este esquema, el desarrollo del mismo no
esta exento de dificultades, ya que hay diferentes escollos que deberemos tener previsto
superar. Así, por ejemplo, es natural esperar que todos los subproblemas sean de la misma
naturaleza entre si, y q ue además esta coincida con la de P. Pero nada hay seguro acerca
del numero de subproblemas en el que deberemos dividir P. Solo hay datos basados en la
experiencia que indican que la técnica Divide y Vencerás funciona mejor con un numero
pequeño de subproblemas que con uno grande. Tampoco sabemos nada sobre el tamaño
que deberán tener los subproblemas. La practica del Divide y Vencerás recomienda que
cuanto mas parecidos sean los tamaños de los subproblemas, mejor funciona el algoritmo.
Pero no hay ningún resultado teórico que demuestre que este hecho siempre conduce a
buenos resultados. En este punto es necesario destacar que cuando hablamos de dividir el
problema en subproblemas, no estamos diciendo que esa división tenga que ser exacta y
exhaustiva (lo que llamaríamos una partición) sino, mas bien, que consideramos subproble-
mas de P, sin que ello suponga que la unión de todos ellos deba reproducir exactamente P.
Podría pasar que la unión de todos los subproblemas reprodujera P, pero lo mas normal
será que de esa unión obtengamos algo mas que P.
Entonces, supuesto que sabemos cuantos subproblemas tendremos y que tamaño tendrán
estos, deberemos saber resolverlos, es decir, hallar las soluciones Si, i∈I, y lo que no es
menos fácil, que podamos combinarlas entre si para obtener una solución S que tenga sen-
tido. Junto con todo eso, hay que confiar en que S se corresponda con la solución verdadera
de P, y finalmente que todo este diagrama secuencial de pasos proporcione un algoritmo
mas eficiente que el básico que suponemos tenemos para resolver los subproblemas, y por
tanto valido para resolver P si hemos dicho que aquellos deben ser de la misma naturaleza
que este.
Bien, pues a pesar de todas estas dificultades y ambigüedades, cuando esta técnica puede
aplicarse, proporciona algoritmos altamente eficaces. Comprobaremos esto con la siguiente
ilustración. Supongamos que queremos resolver determinado problema P, y que para ello
disponemos de un cierto algoritmo B (básico) de orden cuadrático, es decir, que una cierta
implementación de B nos proporciona un tiempo

tB

(n) = bn2

para resolver un caso de tamaño n.
Supongamos ahora que descubrimos que sería posible resolver tal caso descomponiéndolo
en tres subcasos de tamaños n/2, resolviéndolos y combinando los resultados. Supongamos
que la descomposición y la combinación de las soluciones parciales podemos llevarla a ca-
bo mediante un algoritmo C que es lineal, es decir, de tiempo,

tc(n) = kn

para una cierta implementación y determinada constante k. Usando a la vez el algoritmo
básico inicial B y esta nueva idea, obtenemos un nuevo algoritmo N cuya implementación
consume un tiempo.

tN (n) = 3tB(n/2) + tc(n) = 3b(n/2)2 + kn = (3/4)bn2 + kn

El término (3/4)bn2 domina cuando n es suficientemente grande, lo que significa que el algo-
ritmo N es esencialmente un 25% más rápido que el algoritmo básico B. Pero, aunque esta
es una mejora considerable, no hemos conseguido cambiar el orden del tiempo requerido,
ya que el nuevo algoritmo N sigue siendo cuadrático.
Pero aun nos queda otra posibilidad para resolver mas eficazmente P, y radica precisamen-
te en la naturaleza de los subcasos, y por tanto de los subproblemas de P. En efecto, si los
subcasos son pequeños, sería posible que el algoritmo B fuera el que mejor sirviera a nues-
tros intereses. Pero, cuando los subcasos son lo suficientemente grandes, ¿no sería mejor
usar nuestro nuevo algoritmo N recursivamente? Si hacemos esto obtenemos un nuevo al-
goritmo DV cuya implementación corre un tiempo,

tA (n) si n ≤ n0
tDV(n) =
3tDV(n/2) + tc(n) en otro caso

donde n0 es un valor umbral para el tamaño del caso con el que el algoritmo es llamado
recursivamente.
Esta ecuación, que es similar a la de un ejemplo anterior, nos da un tiempo en el orden de
nlg3, que es muy aproximadamente n1.59. Por tanto la mejora comparada con el orden de n2
es sustancial, y lo grande que sea n es lo peor que este algoritmo puede tener. Veremos en
la siguiente sección como elegir n0 en la práctica. Aunque esta elección no afecta al orden
del tiempo de ejecución del algoritmo, también nos interesa hacer la constante oculta que
multiplica nlg3 tan pequeña como sea posible.
Como la técnica Divide y Vencerás se aplica siempre de una forma sistemática, es suscepti-
ble de algoritmizarse. Así el método general divide y vencerás consistiría en lo siguiente
Funcion DV(P)
Si P es suficientemente pequeño o simple entonces devolver BAASSIICCOO (P).

Descomponer P en subcasos P(1), P(2), ..., P(k) mas pequeños
para i = 1 hasta k hacer S(i) = DV(P(i))


donde BASICO, el subalgoritmo básico, se usa para resolver pequeños casos del problema
en cuestión.
Como antes hemos comentado, el número de subcasos k, es usualmente bajo e indepen-
diente del caso particular a resolver. Cuando k=1, es difícil justificar el nombre de divide-y-
vencerás, y en este caso a esta técnica se le llama de simplificación. Mencionemos también
que algunos algoritmos de tipo divide y vencerás, no siguen exactamente el esquema pre-

recombinar las S(i) en S (solucion de P)

Devolver (S)



cedente, sino que en su lugar, exigen que el primer subcaso se resuelvan antes de siquiera,
se haya formulado el segundo subcaso.
En cualquier caso, aprovechando el carácter genérico de la anterior función algorítmica
DV(P), podemos establecer que la eficiencia de un algoritmo Divide y Vencerás se calculará
siempre a partir de una ecuación recurrente de la siguiente forma,
t(n)

si n < c



T(n) =
aT(n/b) +D(n) +C(n)



en otro caso

donde a es el numero de subproblemas, n/b el tamaño de estos, D(n) el tiempo de dividir el
problema en los sub-problemas y C(n) el tiempo de combinacion de las soluciones de los
subproblemas. Si solo estuviéramos interesados en conocer el orden del algoritmo, nos bas-
taría con resolver esta ecuación sin necesidad de determinar las constantes que nos apare-
cerán en la solución. Sin embargo, si quisiéramos la solución exacta, que indudablemente
estaría asociada a una implementación concreta, el calculo de las constantes seria obligado.
La determinación del umbral
Un algoritmo divide y vencerás debe evitar proceder recursivamente cuando el tamaño de
los subcasos no lo justifique. En este caso es preferible usar el algoritmo básico. Para ilus-
trar esto, consideremos de nuevo el algoritmo DV de la anterior sección, cuyo tiempo de
ejecución esta dado por,

tDV(n) =

3tDV (n/2) + tC(n) en otro caso

tB(n) si n[ n0

donde tB(n) es el tiempo requerido por el subalgoritmo básico y tC(n) es el tiempo consumido
en hacer una descomposición y una recombinación.
Para determinar el valor del umbral n0 que minimiza tDV(n), no es suficiente conocer que
tB(n) sea cuadrático y que tC(n) sea lineal, ya que ese valor es evidente que ira asociado a
la resolución de cada caso concreto, y a cada implementación particular.
En efecto, consideremos una implementación para la que los valores de tB(n) y de tC(n)
estén dados, respectivamente, por n2 y 16n milisegundos. Supongamos que tenemos para
resolver un caso de tamaño 1024. Si el algoritmo procede recursivamente hasta obtener
subcasos de tamaño 1, es decir, si n0 =1, consume más de media hora en resolver este ca-
so. Esto es ridículo, ya que el subcaso puede resolverse en poco más de un cuarto de hora
usando el subalgoritmo básico directamente, es decir tomando n0 = 1. ¿Podríamos concluir
que la técnica divide y vencerás nos permite pasar de un algoritmo cuadrático a un algoritmo
cuyo tiempo de ejecución está en O(nlg3), pero sólo a costa de un aumento en la constante
oculta tan enorme que el nuevo algoritmo nunca es económico en casos que puedan resol-
verse en un tiempo razonable?. Pues la respuesta es no: en nuestro ejemplo, el caso de
tamaño 1024 puede resolverse en menos de 8 minutos si elegimos apropiadamente el um-
bral n0.
Este ejemplo muestra que la elección del umbral puede tener una influencia considerable en
la eficiencia de un algoritmo de divide y vencerás. De todos modos, la elección del umbral es
complicada porque el mejor valor generalmente no depende sólo del algoritmo considerado,
sino también de l a implementación particular. ¿Cómo elegiremos entonces n0?. Lo q