Divide y vencerás (A3C34A2D03)

La técnica conocida como Divide y Vencerás consiste en descomponer un problema complejo en subproblemas más simples, independientes entre sí, para construir la solución del problema inicial mediante la combinación de las soluciones de los subproblemas. Este método se puede esquematizar de la siguiente manera:

• Si el problema es sencillo, solucionarlo;
• Si el problema es complejo:
  1 |  Dividir el problema en subproblemas más pequeños
  2 |  Resolver cada subproblema, aplicando la misma estrategia
  3 |  Combinar dichas soluciones para obtener la solución del problema original

Un problema se considera “sencillo” cuando se puede resolver fácilmente, lo que normalmente se da cuando el tamaño del problema es pequeño. Además, los subproblemas deben ser menos costosos de resolver que el problema original. También deben ser disjuntos, es decir, que la solución de cada uno de ellos debe obtenerse independientemente de los otros. Por último, el número de subproblemas debe ser mayor o igual que 2; si fuera 1, la técnica se denomina reducción o simplificación. Así, la forma general de este tipo de algoritmos es la que se ilustra en el listado siguiente.

Algoritmo Divide y Vencerás
Datos
    TamañoProblema: Número
    S, SP1, ..., SPk: Solución
Instrucciones
    Si TamañoProblema es Pequeño
        Entonces S <- ResolverProblema
    Sino
        SP1 <- Divide y Vencerás (SubProblema1)
        ...
        SPk <- Divide y Vencerás (SubProblemaK)
        S <- Combinar (SP1, ..., SPk)
    Fin_Si
    Devolver S
Fin_Divide y Vencerás

Respecto a la eficiencia de este tipo de algoritmos, hay que insistir en que los subproblemas sean independientes entre sí, es decir, que no existan “solapes” entre ellos, porque dispararía la complejidad a órdenes exponenciales. En los casos en los que haya solapamiento entre subproblemas, existen otras técnicas más eficientes para resolverlos, como es el caso de la programación dinámica. Además, es importante que los subproblemas tengan tamaños similares para que no se produzcan desequilibrios que afecten a su rendimiento. Cuando se cumplen todas estas restricciones, la complejidad de este tipo de algoritmos suele ser polinomial, lo que los hace muy eficientes.

Un ejemplo sencillo que ilustra esta técnica es la búsqueda del menor valor de una colección de números. Si la colección solo tiene un número, el problema es trivial: el menor valor es el de dicho número. Si la colección tiene más de un número, se puede dividir la colección en dos mitades de tamaño similar. Así, una vez obtenido el menor elemento de cada una de las dos mitades, bastará con quedarnos con el menor de ellos para tener el menor elemento de la colección completa. El algoritmo MenorColeccion del listado siguiente describe la idea. La Figura 1 ilustra dos ejemplos del funcionamiento del algoritmo. El de la izquierda, es la aplicación a dos casos: cuando el problema es sencillo (P=1) y cuando no lo es (P>1). El de la derecha, describe cómo se obtiene la obtención del menor de una de las mitades (para la otra mitad sería similar) aplicando la misma técnica. Para el caso de que la colección tiene más de un elemento, se descompone siempre en dos mitades, y el proceso se repite hasta que el tamaño de la colección queda reducido a 1, que es el que constituye el caso en el que el problema tiene una solución inmediata. Obsérvese que, para cada mitad, la obtención del menor valor se obtiene aplicando la misma técnica. Por último, la complejidad de este algoritmo es lineal, O(n), ya que se comparan todos los elementos de la colección.

Algoritmo MenorColección
Datos
    P, N1, N2, ..., NP: Número:
    Menor, MenorI, MenorD: Numero
Instrucciones
    P <- TamañoColección
    Si P = 1
        Entonces Menor <- NP
    Sino
        K <- P/2
        MenorI <- MenorColeccion (N1, ..., Nk)
        MenorD <- MenorColeccion (Nk+1, ..., NP)
        Si MenorI <- MenorD
            Entonces Menor <- MenorI
            Sino Menor <- MenorD
        Fin_Si
    Fin_Si S
    Devolver Menor
Fin_MenorColeccion

Figura 1. Ejemplo de aplicación del algoritmo para dos colecciones de números (izda) y desarrollo de uno de los casos (dcha).

La técnica de Divide y Vencerás ha sido utilizada con éxito para reducir la complejidad de los algoritmos tradicionales de ordenación de elementos, que en sus versiones más sencillas (inserción, selección, burbuja) son O(n²). Así, los algoritmos de ordenación rápida (quicksort) o de ordenación por mezcla (mergesort), que aplican “divide y vencerás” son ambos O(nlogn). Veamos uno de ellos, el quicksort, cuya idea es la siguiente:

• Si la colección solo tiene un elemento, el problema es trivial: ya está ordenada.
• Si la colección tiene más de un elemento:
  1 |  Elegir un elemento X (llamado pivote) de la colección
  2 |  Mover los menores que X a su izquierda y los mayores que X a su derecha. El elemento X ha quedado colocado en su sitio (imagen derecha)
  3 |  Ordenar aplicando la misma idea la izquierda de X
  4 |  Ordenar aplicando la misma idea la derecha de X

El listado siguiente describe el algoritmo:

Algoritmo QuickSort
Datos
    X:Elemento, N, PosX:Número;
Instrucciones
    N <- TamañoColección
    Si N > 1
        Entonces X <- Elegir Pivote
                 PosX <- Posición de X al mover menores y mayores
                 QuickSort <- (hasta PosX)
                 QuickSort <- (desde PosX)
   Fin_Si
Fin_QuickSort

La Figura 2 ilustra un ejemplo de funcionamiento. En este caso, se ha elegido como pivote el elemento que ocupa la primera posición, aunque podría haber sido cualquier otro (el último o el de la posición central).

Figura 2. Ejemplo de funcionamiento del algoritmo QuickSort.

La elección del pivote puede afectar a la complejidad del algoritmo, pero no se profundizará en este problema aquí. Por otro lado, el algoritmo que mueve los menores y mayores que el pivote, a su izquierda y derecha, respectivamente, y proporciona la posición en la que ha quedado, no se incluye para no confundir al lector o a la lectora. La Figura 3 ilustra la idea, que consiste en recorrer la secuencia desde la izquierda hacia la derecha (izq) hasta que se encuentre un elemento mayor que el pivote, y desde la derecha hasta la izquierda (der) hasta encontrar un elemento menor que el pivote. En ese momento, se intercambia uno por otro. El proceso se repite hasta que se crucen izq y der. La posición de der será la posición ordenada del pivote, por lo que se realiza el intercambio entre ambas.

Figura 3. Ejemplo de colocación del pivote.