Algoritmo divide y vencerás
De Wikipedia, la enciclopedia libre
En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las soluciones encontradas.
En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. Como introducción, se podría decir que el método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema, como por ejemplo el algoritmo de ordenación ( quicksort , mergesort) y la transformada discreta de Fourier.
Tabla de contenidos |
[editar] Diseño e implementación
Los algoritmos Divide y vencerás o Divide and conquer, como se les conoce en inglés se diseñan como procedimientos generalmente recursivos.
AlgoritmoDYV(p: TipoProblema): TipoSolucion
IF esCasoBase(p)
return resuelve(p)
ELSE
subproblemas : ARRAY OF TipoProblema
subproblemas = divideEnSubproblemas(p)
soluciones_parciales : ARRAY OF TipoSolucion
FOR EACH sp IN subproblemas
soluciones_parciales.push_back(AlgoritmoDYV(sp))
return mezcla(soluciones_parciales)
Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivo que almacene las soluciones parciales en una estructura de datos explícita, como puede ser una pila, cola, o cola con prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escoger qué subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usar técnicas como Ramificación y acotación o de optimización.
[editar] Ventajas
[editar] Resolución de problemas complejos
Este modelo algorítmico es una herramienta potente para solucionar problemas complejos, tales como el clásico juego de las torres de Hanoi. Todo lo que necesita este algoritmo es dividir el problema en subproblemas más sencillos, y éstos en otros más sencillos hasta llegar a unos subproblemas sencillos (también llamados casos base). Una vez ahí, se resuelven y se combinan los subproblemas en orden inverso a su inicio. Cómo dividir los problemas es, a menudo, la parte más compleja del algoritmo. Por eso, en muchos problemas, el modelo sólo ofrece la solución más sencilla, no la mejor.
[editar] Eficiencia del algoritmo
Normalmente, esta técnica proporciona una forma natural de diseñar algoritmos eficientes. Por ejemplo, si el trabajo de dividir el problema y de combinar las soluciones parciales es proporcional al tamaño del problema (n); además, hay un número limitado p de subproblemas de tamaño aproximadamente igual a n/p en cada etapa; y por último, los casos base requieren un tiempo constante (O(1)); entonces el algoritmo divide y vencerás tiene por cota superior asintótica a O(nlogn). Esta cota es la que tienen los algoritmos divide y vencerás que solucionan problemas tales como ordenar y la transformada discreta de fourier. Ambos procedimientos reducen su complejidad, anteriormente definida por O(n2). Para terminar, cabe destacar que existen otros enfoques y métodos que mejoran estas cotas.
[editar] Paralelismo
Este tipo de algoritmos se adapta de forma natural a la ejecución en entornos multiprocesador, especialmente en sistemas de memoria compartida donde la comunicación de datos entre los procesadores no necesita ser planeada por adelantado, por lo que subproblemas distintos se pueden ejecutar en procesadores distintos.
[editar] Acceso a memoria
Los algoritmos que siguen el paradigma Divide y vencerás, tienden naturalmente a hacer un uso eficiente de las memorias cachés. La razón es que una vez que un subproblema es lo suficientemente pequeño, él y todos sus subproblemas se pueden, en principio, solucionar dentro de esa caché, sin tener acceso a la memoria principal, que es del orden de decenas de veces más lenta. Un algoritmo diseñado para aprovechar la memoria caché de esta manera se llama modelo caché-olvidadiza, olvidadiza porque no contiene el tamaño de la memoria como parámetro explícito. Por otra parte, estos algoritmos se pueden diseñar para muchos problemas importantes, tales como ordenación, la multiplicación de matrices, de manera que se haga un uso óptimo de la caché. En contraste, el acercamiento tradicional para explotar la caché es hacer bloques, de esta forma, el problema se divide explícitamente en las partes de tamaños apropiados para que se pueda utilizar al caché de forma óptima, pero solamente cuando el algoritmo es mejorado para el tamaño específico de la caché de una máquina particular. La misma ventaja existe en lo que respecta a otros sistemas jerárquicos de memoria, por ejemplo NUMA o memoria virtual, así como para niveles múltiples de caché: una vez que un subproblema es suficientemente pequeño, puede ser solucionado dentro de un nivel dado de la jerarquía, sin tener que acceder al más alto (más lento). Sin embargo, la clase de optimalidad asintótica descrita aquí, análoga a notación O mayúscula, no hace caso de factores constantes, y el añadir mejoras adicionales específicas de la máquina y caché no es un requerimiento para alcanzar el óptimo en un sentido absoluto.
[editar] Desventajas
La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastos indirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener que almacenar la pila de llamadas (el estado en cada punto en la repetición), pueden empeorar cualquier mejora hasta entonces lograda. Esta tara, sin embargo, depende del estilo de la implementación: con casos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de las llamadas.
[editar] Ejercicios
- Multiplicación de Enteros Grandes: algoritmo eficiente para multiplicar números de tamaño considerable, que se salen de los límites de representación, y no abordable con los algoritmos clásicos debido al excesivo coste.
- Subvector de suma máxima: Algoritmo eficiente para encontrar subcadenas dentro de un vector evitando tener que recorrer todo el vector desde cada posición.
