miniaturadeimagen|Visualización del cálculo de la sublista contigua más grande con la suma más grande de una lista de 4 elementos por divide y vencerás. En la cultura popular, divide y vencerás (del inglés: divide and conquer) hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las soluciones encontradas.

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros), multiplicar números grandes (Karatsuba), análisis sintácticos (análisis sintáctico top-down) y la transformada discreta de Fourier.

Por otra parte, analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización.

El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces). Estos algoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles. Bajo esta amplia definición, sin embargo, cada algoritmo que usa recursión o bucles puede ser tomado como un algoritmo de “divide y vencerás”. El nombre decrementa y vencerás ha sido propuesta para la subclase simple de problemas.

La corrección de un algoritmo de “divide y vencerás”, está habitualmente probada una inducción matemática, y su coste computacional se determina resolviendo relaciones de recurrencia.

Principio de Rubik

El principio de Rubik indica que “un problema complejo se resuelve más fácil fragmentando en problemas cada vez más pequeños y por consiguiente más simples.” De manera que cada incidencia o tarea conlleva a una sola responsabilidad y a la vez sencilla de explicar. Y esto se resuelve separando los problemas en pequeños fragmentos del problema general.

Precedentes históricos

La búsqueda binaria, un algoritmo de divide y vencerás en el que el problema original es partido sucesivamente en subproblemas simples de más o menos la mitad del tamaño, tiene una larga historia. La idea de usar una lista ordenada de objetos para facilitar su búsqueda data de la antigua Babilonia en el 200 a. C., mientras que una descripción del algoritmo en ordenadores apareció en 1946 en un artículo de John Mauchly. Otro algoritmo de “divide y vencerás” con un único subproblema es el algoritmo de Euclides para computar el máximo común divisor de dos números (mediante reducción de números a problemas equivalentes cada vez más pequeños), que data de muchos siglos antes de Cristo.

Un ejemplo antiguo de algoritmo de “divide y vencerás” con múltiples subproblemas es la descripción realizada por Gauss en 1805 de lo que se le llama ahora algoritmo de la rápida transformación de FourierCooley-Tukey (FFT), aunque él no analizó su conjunto de operaciones cuantitativamente y los FFT no se difundieron hasta que se redescubrieron casi un siglo después.

Otro problema antiguo de 2 subdivisiones de “divide y vencerás” que fue específicamente desarrollado para ordenadores y analizado adecuadamente es el algoritmo de merge-sort, inventado por John von Neumann en 1945.

Otro ejemplo notable es el algoritmo inventado por A. Karatsuba en 1960 que puede multiplicar dos números de n dígitos en . El algoritmo refutó la conjetura de Andréi Kolmogórov en 1956 que esa tarea requería Ω(n2) operaciones. Otro ejemplo de algoritmo de divide y vencerás que originalmente no se usaba en ordenador, Knuth dio el método que habitualmente una oficina de correos usa para dirigir las cartas: las cartas se ordenan en diferentes bolsas en función de su área geográfica, cada una de estas bolsas a su vez se ordena en diferentes lotes para subregiones más pequeñas, y así sucesivamente hasta que son repartidas. Esto está relacionado con el ordenamiento Radix, descrito para las máquinas de ordenación de tarjetas perforadas a los comienzos .

Diseño e implementación La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:

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 n/k y donde 0 ≤ n/k < n. A esta tarea se le conoce como división. 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. Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.

Los algoritmos divide y vencerás (o divide and conquer, en inglés), se diseñan como procedimientos generalmente recursivos.

AlgoritmoDyV (p: TipoProblema): TipoSolucion

if esCasoBase(p) return resuelve(p)

else subproblemas: array of TipoProblema subproblemas = divideEnSubproblemas(p) soluciones_parciales: array of TipoSolucion

for each sp in subproblemas soluciones_parciales.push_back(AlgoritmoDYV(sp)) endFor

return mezcla(soluciones_parciales)

endIf

finAlgoritmoDyV

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:

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. En cambio, 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.

Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivo que almacene las soluciones parciales en una estructura de datos explícita, como puede ser una pila, cola, o cola de prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escoger qué subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usar técnicas como Ramificación y acotación o de optimización.

Recursión

Los algoritmos de “divide y vencerás” están naturalmente implementados, como procesos recursivos. En ese caso, los subproblemas parciales encabezados por aquel que ya ha sido resuelto se almacenan en la pila de llamadas de procedimientos.

Pila explícita

Los algoritmos de divide y vencerás también pueden ser implementados por un programa no recursivo que almacena los subproblemas parciales en alguna estructura de datos explícita, tales como una pila, una cola, o una cola de prioridad. Este enfoque permite más libertad a la hora de elegir los subproblemas a resolver después, una característica que es importante en algunas aplicaciones, por ejemplo en la búsqueda en anchura y en el método de ramificación y poda para optimización de subproblemas. Este enfoque es también la solución estándar en lenguajes de programación que no permiten procedimientos recursivos.

Tamaño de la pila

En implementaciones recursivas de algoritmos de DyV, debe asegurarse que hay suficiente memoria libre para la pila de recursión, sino la ejecución puede fallar por desbordamiento de la pila. Afortunadamente, los algoritmos DyV que son eficientes temporalmente tienen una profundidad recursiva relativamente pequeña. Por ejemplo, el algoritmo quicksort puede ser implementado de forma que nunca requiere más de llamadas recursivas para ordenar n elementos.

Los desbordamientos de pila podrían ser difíciles de evitar cuando usamos procedimientos recursivos, donde muchos compiladores asumen que la pila de recursión es una zona contigua de memoria, y algunos asignan una cantidad de espacio determinada para ello. Los compiladores pueden también asignar más información en la pila de recursión que la estrictamente necesaria, tales como la dirección de retorno, parámetros invariables, y las variables internas del procedimiento. Así, el riesgo de desbordamiento de pila puede ser reducido mediante la minimización de parámetros y variables internas de los procedimientos recursivos, o usando estructura de pila explícita.

Elegir los casos base

En cualquier algoritmo recursivo, hay una libertad considerable para elegir los casos bases, los subproblemas pequeños que son resueltos directamente para acabar con la recursión.

Elegir los casos base más pequeños y simples posibles es más elegante y normalmente nos da lugar a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo FFT podría parar la recursión cuando la entrada es una muestra simple, y el algoritmo quicksort de ordenación podría parar cuando la entrada es una lista vacía. En ambos casos, sólo hay que considerar un caso base, y no requiere procesamiento.

Por otra parte, la eficiencia normalmente mejora si la recursión se para en casos relativamente grandes, y estos son resueltos no recursivamente. Esta estrategia evita la sobrecarga de llamadas recursivas que hacen poco o ningún trabajo, y pueden también permitir el uso de algoritmos especializados no recursivos que, para esos casos base, son más eficientes que la recursión explícita. Ya que un algoritmo de DyV reduce cada instancia del problema o subproblema a un gran número de instancias base, éstas habitualmente dominan el coste general del algoritmo, especialmente cuando la sobrecarga de separación/unión es baja. Véase que estas consideraciones no dependen de si la recursión está implementada por compilador o por pila explícita.

Compartir subproblemas repetidos

Para algunos problemas, la recursión ramificada podría acabar evaluando el mismo subproblema muchas veces. En tales casos valdría la pena identificar y guardar las soluciones de estos subproblemas solapados, una técnica comúnmente conocida como memoización. Llevado al límite, nos lleva a algoritmos de “divide y vencerás” de bottom-up tales como la programación dinámica y análisis gráfico.EDF

Ventajas Resolución de problemas complejos Este modelo algorítmico es una herramienta potente para solucionar problemas complejos, tales como el clásico juego de las torres de Hanói. Todo lo que necesita este algoritmo es dividir el problema en subproblemas más sencillos, y éstos en otros más sencillos hasta llegar a unos subproblemas sencillos (también llamados casos base). Una vez ahí, se resuelven y se combinan los subproblemas en orden inverso a su inicio. Cómo dividir los problemas es, a menudo, la parte más compleja del algoritmo. Por eso, en muchos problemas, el modelo sólo ofrece la solución más sencilla, no la mejor.

Eficiencia del algoritmo