INTRODUCCIÓN

Esta estrategia constituye un poderoso paradigma para definir algoritmos eficientes. Este método primero divide un problema en dos subproblemas más pequeños de modo que cada subproblema sea idéntico al problema original, excepto porque su tamaño de entrada es menor. Luego, ambos subproblemas se resuelven y las subsoluciones se fusionan en la solución final.

Una cuestión muy importante sobre esta estrategia es que divide el problema original en dos subproblemas idénticos al problema original. Por lo tanto, también estos dos subproblemas pueden resolverse aplicando la estrategia divide-y-vencerás. O, para decirlo con otras palabras, se resuelven de manera recurrente o recursiva.

Consideremos el sencillo problema de encontrar el máximo (número mayor) de un conjunto S de n números. La estrategia divide-y-vencerás resolvería este problema al dividir la entrada en dos conjuntos, cada uno con n/2 números. Sean S1 y S2 estos dos conjuntos.

Luego se encuentra el máximo de S1 y S2, respectivamente. Sea Xi, donde i = 1,2, el máximo de S¡. Así, el máximo de S puede encontrarse al comparar X1 y X2. El que sea mayor de éstos será el máximo de S.En el análisis anterior casualmente se mencionó que es necesario encontrar el máximo X¡. Pero, ¿cómo se encuentra Xi? Nuevamente puede aplicarse la estrategia divide-y-vencerás. Es decir, Si se divide en dos subconjuntos, se encuentran los máximos de estos subconjuntos y después de fusionan los resultados.

En general, un algoritmo divide-y-vencerás consta de tres pasos.

Paso 1. Si el tamaño del problema es pequeño, éste se resuelve aplicando algún método directo; en caso contrario, el problema original se separa en dos subproblemas, de preferencia del mismo tamaño.

Paso 2. Los dos subproblemas se resuelven de manera recurrente aplicando el algoritmo divide-y-vencerás a los subproblemas.

Paso 3. Las soluciones de los subproblemas se fusionan en una solución del problema original.

La recurrencia del paso 2 crea subproblemas cada vez más pequeños. Al final estos subproblemas son tan pequeños que cada uno puede resolverse directa y fácilmente.