Algoritmos Divide y Venceras

Muy buenas vie0s!

Pues nada, aqui estudiando Teoría de Algoritmos... y como estoy estudiando esto, pues voy a compartirlo con vosotros y asi sufris un poco conmigo jejeje (ademas, me sirve para estudiar pues tengo que hacer memoria para escribirlo aqui)

Los algoritmos Divide y Venceras, como su propio nombre indica, se basan en dividir un problema en distintos subproblemas, resolver estos, recoger las distintas soluciones y combinarlas en la solución final, que usualmente sera la solución al problema original. Decir que a veces, la suma de los subproblemas no tiene por que ser igual al problema original en si.




Y hasta aquí, parece muy bonito y muy "oh, como mola, que facil, el paro en China baja..." dejemos los desvarios, y una vez dejados aparte, he de decir que no es tan facil y que muchas veces el desarrollo de este esquema no esta exento de complicaciones y dificultades.

Para simplificar, y aunque no hay algun elemento teoríco que asi lo asegure, la experiencía dice que es mejor dividir en subproblemas de mismo tamaño más o menos. Luego, hay que tener en cuenta que hay veces que el mismo problema en si no es susceptible de ser dividido pues posiblemente con un algoritmo basico se podrá resolver mas eficientemente pero la cuestión esta en ver cuando es mejor dividir ó no... ergo tenemos que hallar o tener en cuenta un tamaño umbral para esa cuestión. Hay que comentar que cuando se supera dicho umbral, el algoritmo será llamado recursivamente.

Y llegados aqui, basicamente ya esta dicho más o menos lo que es el algoritmo en si, desde una perspectiva teoríca y sin hacer ninguna implementación. Pero como eso no puede ser, he de ser  consecuente con el articulo y por ello, voy a mostrar una implementación teoríca tambien y en pseudo-codigo para que quede claro de como funciona esto.

---

FUNCION DV(P)
     Si P es pequeñito o sencillo, devolver Algoritmo Basico (P)
    
     Descomponer P en distintos subproblemas P(1), P(2)..., P(k) mas pequeños
            Para i = 1 hasta k hacer S(i) = DV(P(i))
                    Recombinar las S(i) en S (solucion de P)
     Devolver (S)

---

Donde P es el problema, P(1), P(2)... son los distintos subproblemas y k será el numero total de subproblemas. S es el conjunto de la soluciones recombinadas de los subproblemas.

Nótese que la linea del Para... se llama a la función otra vez [S(i) = DV(P(i))] ó sea, ahí la hemos llamado recursivamente pues se llama a si misma.

Bueno, esto es una primera explicación de este tipo de algoritmos. A ver si mañana, puedo hacer alguna aproximación a la utilización de dicho algoritmo en busquedas o ordenación de vectores...

Espero que os haya gustado y que haya resultado una explicación facil de entender! Sin más, un saludo y sed felices vie0s!