1
Método general La técnica divide y vencerás consiste en descomponer el problema en un conjunto de subproblemas más pequeños. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original.
Esquema general: divide_venceras (p: problema) dividir (p, p1, p2, …, pk) para i = 1, 2, …, k si = resolver (pi) solucion = combinar (s1, s2, …, sk)
Puede ser recursivo siendo “resolver” una nueva llamada a “divide_venceras” Si el problema es “pequeño”, entonces se puede resolver de forma directa.
Ejemplo: Torres de Hanoi
2
Método general
Para que pueda aplicarse la técnica divide y vencerás necesitamos: El problema original debe poder dividirse fácilmente en un conjunto de subproblemas, del mismo tipo que el problema original pero con una resolución más sencilla (menos costosa). La solución de un subproblema debe obtenerse independientemente de los otros. Normalmente los subproblemas deben ser de tamaños parecidos. Como mínimo necesitamos que haya dos subproblemas. Si sólo tenemos un subproblema hablamos de técnicas de reducción (o simplificación). Necesitamos un método (más o menos directo) de resolver los problemas de tamaño pequeño. Es necesario tener un método de combinar los resultados de los subproblemas.
3
Método general, esquema recursivo Normalmente para resolver los subproblemas se utilizan llamadas recursivas al mismo algoritmo (aunque no necesariamente).
Esquema recursivo (con división en 2 subproblemas): divide_venceras (p, q: indice) var m: indice si pequeño (p, q) solucion = solucion_directa (p, q) en otro caso m = dividir (p, q); solucion = combinar (divide_venceras (p, m), divide_venceras (m+1, q));
4
Análisis de tiempos de ejecución Para el esquema recursivo, con división en dos subproblemas: g(n) Si n?n0 es suficientemente pequeño t(n) = 2*t(n/2) + f(n) En otro caso t(n): tiempo de ejecución del algoritmo. g(n): tiempo de comprobar si es pequeño y calcular la solución para el caso base f(n): tiempo de comprobar si es pequeño y de dividir el problema y combinar los resultados.
5
Análisis de tiempos de ejecución
Desarrollando tenemos: Suponiendo que n es potencia de 2, n = 2k, y n0 = n/2m.
Si n0=1, entonces m=k:
6
Análisis de tiempos de ejecución
Ejemplo 1. La resolución directa se puede hacer en un tiempo constante y la combinación de resultados también. g(n) = c; f(n) = d
Ejemplo 2. La solución directa se calcula en O(n2) y la combinación en O(n). g(n) = c·n2; f(n) = d·n
7
Análisis de tiempos de ejecución Si el problema se divide en a llamadas recursivas de tamaño n/b, y la combinación requiere f(n) = d·n ? O(n), entonces: t(n) = a·t(n/b) + d·n Suponiendo n = bk ? k = logb n t(bk) = a·t(bk-1) + d·bk Podemos deducir que: O(nlogba) Si a > b t(n) ? O(n·log n) Si a = b O(n) Si a < b Ejemplo 3. Dividimos en 2 trozos de tamaño n/2 (ordenación por mezcla): a = b = 2 t(n) ? O(n·log n) Ejemplo 4. Realizamos 4 llamadas recursivas con trozos de tamaño n/2. a = 4; b = 2 t(n) ? O(nlog24) = O(n2)
8
Búsqueda del máximo y del mínimo Método directo: MaxMin (A: array [1..N] of tipo; var Max, Min: tipo) Max = A[1] Min = A[1] para i=2, 3, …, N si A[i]>Max Max = A[i] en otro caso si A[i]