Divide y Vencerás

Publicado por Mario en

La idea de esta técnica es resolver un problema difícil dividiéndolo en partes más simples tantas veces como sea necesario.

En programación, el término divide y vencerás(DyV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico, dada la cantidad de aplicaciones que ha tenido para resolver numerosos problemas.

El método esta basado en la resolución recursiva de un problema dividiéndolo en varios subproblemas similares más simples. El proceso de división continúa hasta que estos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al llegar a este punto, las soluciones a cada uno de estos subproblemas se combinan para obtener la solución final.

ALGORITMOS DIVIDE Y VENCERÁS

La estructura de estos algoritmos se basa en recursión, es decir, se tiene un caso base donde el problema es trivial y se tiene otra parte dónde se realizan las operaciones recursivas con el objetivo de llegar al punto anterior.

EJEMPLOS DIVIDE Y VENCERÁS EN JAVA

Los ejemplos expuestos a continuación están codificados en java, pero podrían ser codificados en cualquier otro lenguaje que soporte la programación recursiva.

La estructura de los siguientes ejemplos está formada por:

  1. Límite inferior(li): indica el comienzo de aplicación del algoritmo
  2. Límite superior(ls): indica el fin de aplicación del algoritmo
  3. Mitad: parámetro pivote del algoritmo para ir dividiéndo el vector en sucesivas mitades, es decir, dividir el problema inicial en subproblemas más sencillos
  • Mayor elemento de un vector: este algoritmo “DyV” va reduciendo en mitades el vector para conseguir el mayor elemento de cada mitad y así sucesivamente hasta llegar al vector completo.Finalmente, se compara que máximo de cada parte es mayor de los dos y éste sería el mayor elemento del vector.
    public int mayor(int[] v,int li, int ls){
            if(li==ls)
                return v[li];
            else{
                int mitad = (li+ls)/2;
                int maxIzq = mayor(v,li,mitad);
                int maxDcha = mayor(v,mitad+1,ls);
                if(maxIzq>maxDcha)
                    return maxIzq;
                else
                    return maxDcha;
            } 
        }
  • Menor elemento de un vector: algoritmo idéntico al anterior, sin embargo, en esta ocasión nos quedamos con el menor de cada mitad.
    public int menor(int[] v,int li, int ls){
            if(li==ls)
                return v[li];
            else{
                int mitad = (li+ls)/2;
                int minIzq = menor(v,li,mitad);
                int minDcha = menor(v,mitad+1,ls);
                if(minIzq<minDcha)
                    return minIzq;
                else
                    return minDcha;
            } 
        }
  • Búsqueda de un elemento en un vector ordenado: a continuación se pueden apreciar la versión iterativa(sin aplicar DyV) y la recursiva aplicando la técnica.
    public boolean buscarIterativo(int[] v,int e){
            int li = 0, ls = v.length-1,mitad;
            boolean encontrado = false;
     
            while((li<ls) && !encontrado){
                //Mientras que el limite inferior se menor que el superior
                mitad = (li+ls)/2;
                if(e==v[mitad])//Si esta en la mitad
                    encontrado = true;
                else{
                    //Sino se busca en que mitad está
                    if(e <v[mitad])
                        /*Si esta en la primera mitad el limite superior pasa a ser el
                        último elemento de la primera mitad*/
                        ls = mitad - 1;
                    else
                        /*Si esta en la segunda mitad el limite inferior pasa a ser el 
                        primer elemento de la segunda mitad
                        */
                        li = mitad + 1;
                }
            }
     
            return encontrado;
        }
    public boolean buscarRecursivo(int[] v, int li,int ls,int e){
            boolean encontrado = false;
            int mitad;
     
            if(li==ls){
                /*La longitud del vector es 1, por lo tanto 
                 el elemento solo puede estar en la primera posición*/
                encontrado = v[li]==e;
            }else{
                mitad = (li+ls)/2;//Posición mitad del vector
                if(v[mitad]==e)//Está en la mitad
                    encontrado = true;
                else if(v[mitad]<e)//Es mayor que la mitad
                    //Llamada recursiva con la segunda mitad del vector
                    encontrado = buscarRecursivo(v,mitad+1,ls,e);
                else//Es menor que la mitad
                    //Llamada recursiva con la primera mitad del vector
                    encontrado = buscarRecursivo(v,li,mitad-1,e);
            }
            return encontrado;
        }
  • Valor medio de un vector de enteros: algoritmo que aplica la técnica de forma muy parecida a los métodos anteriores, asimismo sería dividir y aplicar la operación por mitades.
    public static double media(int[] v,int li, int ls){
            if(li==ls)
                return v[li];
            else{
                int mitad = (li+ls)/2;
                double mediaIzq = media(v,li,mitad);
                double mediaDcha = media(v,mitad+1,ls);
                return (mediaIzq+mediaDcha)/2;
            } 
        }

En conclusión, la técnica “Divide y Vencerás” tiene numerosas aplicaciones en el mundo algorítmico, debido a su efectividad de ir simplificando el problema para conseguir soluciones parciales que harán posible la solución final. Esta, además, tiene como consecuencia una reducción considerable de la complejidad de los algoritmos.


Deja un comentario