Resolver problemas aplicando la estrategia Divide y Vencerás


La estrategia Divide y Vencerás (Divide and Conquer en inglés), es una técnica utilizada en disímiles algoritmos de programación, con el objetivo de optimizar la cantidad de operaciones que se van a realizar.

En esencia esta técnica se basa en dividir un problema en problemas más pequeños (sub-problemas), hasta que la solución de los sub-problemas sea trivial (es decir que se pueda resolver directamente), luego, con la unión de las soluciones de cada sub-problema llegar a la solución del problema principal.

Podemos crear un pseudocódigo de este proceso de la siguiente manera:

FuncionDivideYVenceras(problema)
Inicio
    Si problema es trivial
        Resolver problema
    Si no
        Inicio
            Dividir el problema en sub-problemas
            Para i=0 hasta Cantidad_de_sub-problemas
            FuncionDivideYVenceras(sub-problema[i])
            Combinar las soluciones de los sub-problemas
    Fin
Fin

Como puedes ver, el modelo general de un problema del tipo Divide y Vencerás se puede plantear como una función recursiva, que se detiene una vez que encuentra los casos bases. Pues esto es lo que se persigue con esta estrategia, mejorar el rendimiento de los algoritmos.

Dentro de los algoritmos clásicos que podemos encontrar que utilizan este tipo de estrategia, tenemos:

  • Algoritmos de ordenamiento tales como: Quick Sort, Merge Sort, entre otros.
  • Método para multiplicar matrices.
  • Encontrar el par de puntos más cercanos en un conjunto de puntos en el plano.
  • Determinar el k-ésimo elemento en un listado.
  • Hallas la potencia de un número.

Este último método (potencia de un número), será el que veremos a lo largo del artículo y les explicaré de qué forma podemos elevar un número a la potencia de una forma más óptima por medio de la estrategia hablada.

Lo primero que debes conocer es ¿Cómo elevar un número a la potencia? La respuesta a esto está dada por la forma en que lo haríamos manualmente, la mayoría seguro cuando vamos a elevar un número N a la K, lo que hacemos es multiplicar K veces el número N, o lo que es lo mismo:

N*N*N…*N

Si llevamos esto a la programación, la cantidad de iteraciones que debemos hacer, para determinar la potencia, va a estar dada por el número K. A continuación les muestro este método de elevar a la potencia, en lenguaje de programación C++:

int Potencia(int base, int exponente){
    int solucion = 1;

    for(int i=0; i<exponente; i++) //Aquí, multiplico la base
        solucion *= base;
    
    return solucion;
}

Como puedes notar, la cantidad de iteraciones necesarias para realizar esta operación es el valor del exponente, pero si este exponente es un valor muy grande, ¿Crees que se podría realizar esta operación?. Digamos que el exponente va a ser igual a 10^16, serían necesarias 10^16 iteraciones para resolver esta potencia.

¿Cómo podríamos mejorar este algoritmo? Aquí entra la técnica de Divide y Vencerás, hay que buscar la manera de dividir este problema en sub-problemas y resolverlo bajando esta complejidad.

Para ello debemos tener algunos conceptos claros sobre las propiedades de las potencias, que nos servirán de base para dar solución al problema. Alguna de las reglas que usaremos son:

  • Podemos decir que N^K * N^P es lo mismo que decir N^(K+P).
  • Por tanto a partir de lo anterior, podemos decir que N^K es lo mismo que decir N^(K/2) * N^(K/2).

Partiendo de este punto, entonces nos encontramos con la vía que usaremos para dividir el problema en sub-problemas.

Las condiciones esenciales que debemos seguir son:

  • Si el exponente es 1, entonces la solución es la base.

Divide y venceras

  • Si el exponente es 0, entonces la solución es 1.

Divide y venceras

  • Si el exponente es par, dividir en dos y resolvemos una sola parte del problema.

Divide y venceras

  • Si el exponente es impar, dividir en dos, resolvemos una sola parte del problema y el valor que nos queda por agregar lo multiplicamos a la solución.

Divide y venceras

Y como podemos notar, en cada operación que realicemos, desechamos la mitad de los cálculos, dado que si ya determinamos a que es igual N^(K/2) no es necesario volver a calcularlo. Entonces, ¿Cómo podemos programar esta forma de subdividir este problema?

Pues como les mencioné anteriormente, la vía utilizada para resolver este tipo de problemas,es por medio de una función recursiva. A continuación les muestro el código en C++ de este método.

int Potencia2(int base, int exponente){
    if(exponente == 0) 
        return 1;  //Si el exponente es 0, la solución es 1.
    if(exponente == 1)
        return base;  //Si el exponente es 1, la solución es la base.
    
    //Dividimos el problema en dos y calculamos
    int solucion = Potencia2(base, exponente/2);  
    solucion *= solucion;  //La solución del sub-problema, la multiplicamos por ella misma, ya que es igual al otro sub-problema.
    
    if(exponente%2 == 1)  //Si el exponente es impar, multiplicamos la solución por la base.
        solucion *= base;
    return solucion;
}

Está claro que es un poco más complejo de entender este método, pero dada la forma de solución que utiliza, la cantidad máxima de iteraciones que va a realizar es igual a log2(N), ya que se divide consecutivamente en 2 el exponente. A continuación les muestro una tabla comparativa donde podrán ver las diferencias entre la cantidad de iteraciones que hacen cada uno de los dos métodos vistos.

Exponente N Log(N)
10 10 5
100 100 7
1000 1000 10
1000000 1000000 20

Conclusiones

Está claro que podemos optimizar en gran medida la forma de elevar un número a la potencia. Es por ello la importancia de la estrategia de Divide y Vencerás, ya que nos provee de una estrategia de solución a los problemas, porque como les mostré anteriormente, nos divide el problema para mejorar la forma de llegar a la respuesta final.

Esto es todo por ahora y nos vemos en próximos artículos con algo más sobre programación e informática. Cualquier duda o sugerencia, puedes dejarla en los comentarios. Hasta la próxima.

 

 

  • JO

    ¿Puede ser que haya un error en “Digamos que el exponente va a ser igual a 10^16, serían necesarias 10^16 iteraciones para resolver esta potencia”, no serían 16 contra 5 en forma recursiva?