dr. eduardo a. rodrÍguez tertello/algorithms/sesion12.pdf · divide y vencerás divide y vencerás...

Divide y vencerás

Dr. Eduardo A. RODRÍGUEZ TELLO

CINVESTAV-Tamaulipas

7 de marzo de 2018

Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Divide y vencerás 7 de marzo de 2018 1 / 50

1 Divide y vencerás


Divide y vencerás

Divide y vencerás

Divide y vencerás1 Es la estrategia para diseño de algoritmos más conocida

2 Divide la instancia del problema en dos o más instancias máspequeñas

3 Resuelve las instancias más pequeñas recursivamente

4 Obtiene la solución de la instancias original del problema alcombinar estas soluciones


Divide y vencerás

Divide y vencerás


Divide y vencerás Ejemplos de algoritmos divide y vencerás

1 Divide y vencerásEjemplos de algoritmos divide y vencerásRecurrencia general para divide y vencerásTeorema maestroMultiplicación de enteros grandesDivide y vencerás para cubiertas convexasQuickHull para cubiertas convexas


Divide y vencerás Ejemplos de algoritmos divide y vencerás

Ejemplos de algoritmos divide y vencerás

Algoritmos de ordenamiento: mergesort y quicksort

Recorridos en árboles binarios

Multiplicación de grandes enteros

Multiplicación de matrices: algoritmo de Strassen

Algoritmos para el par más cercano y cubierta convexa

Búsqueda binaria: decrementa en 1/2 (o divide y vencerás)


Divide y vencerás Recurrencia general para divide y vencerás



Divide y vencerás Recurrencia general para divide y vencerás

Recurrencia general para divide y vencerás

Divide y vencerás resuelve un problema de tamaño n recursivamente:dividiendo el problema original en a subproblemas de tamaño n/b ycombinando estas soluciones en tiempo O(nd), para a, b, d > 0

Su tiempo de ejecución puede entonces expresarse con la siguienteecuación:

T (n) = aT (dn/be) +O(nd)


Divide y vencerás Teorema maestro




Teorema MaestroDadas dos constantes a ≥ 0, b > 1 y f(n) una función, sea T (n)definida en los enteros no negativos por la recurrencia

T (n) = aT (n/b) + f(n),donde se interpreta n/b como bn/bc o dn/be. Entonces T (n)tiene los siguientes límites asintóticos:

1 Si f(n) = O(nlogb a−ε) para una constante ε > 0, entoncesT (n) = Θ(nlogb a)

2 Si f(n) = O(nlogb a), entonces T (n) = Θ(nlogb a lg n)

3 Si f(n) = O(nlogb a+ε) para una constante ε > 0, y sia f(n/b) ≤ c f(n) para alguna constante c < 1 y valores de nsuficientemente grandes, entonces T (n) = Θ(f(n))



Teorema maestro, observaciones

En cada uno de los tres casos, se comparan las funciones f(n) ynlogb a

Intuitivamente la función más grande determina la solución de larelación de recurrencia:

1 nlogb a es la más grande, entonces la solución es T (n) = Θ(nlogb a)

2 Las dos funciones son del mismo tamaño, entonces multiplicamospor un factor logarítmico y la solución esT (n) = Θ(nlogb a lg n) = Θ(f(n) lg n)

3 f(n) es la más grande, entonces la solución es T (n) = Θ(f(n))




Es importante aclarar los siguientes detalles técnicos:Caso 1: f(n) no sólo deber ser menor que nlogb a, esta debe serpolinomialmente menor

Significa que f(n) debe ser asintóticamente menor que nlogb a porun factor nε para alguna constante ε > 0

Caso 3: f(n) no sólo debe ser mayor que nlogb a, esta deber serpolinomialmente mayor y además satisfacer la condición deregularidad

a f(n/b) ≤ c f(n) para alguna constante c < 1 y todas los valoresde n suficientemente grandes.




En los siguientes casos no es posible utilizar el Teorema Maestro pararesolver una relación de recurrencia:

No todos los casos están cubiertos, hay un margen de espacio(gap) entre los casos 1 y 2 cuando f(n) es menor que nlogb a perono polinomialmente menor

Lo mismo ocurre entre los casos 2 y 3 cuando f(n) es mayor quenlogb a pero no polinomialmente mayor

Si en el caso 3 la condición de regularidad no se cumple



Teorema maestro, ejemplo 1

T (n) = 9T (n/3) + n

Identificamos que para esta recurrencia a = 9, b = 3, f(n) = n

Por lo tanto nlogb a = nlog3 9 = Θ(n2)

Como f(n) = O(nlog3 9−ε), donde ε = 1 podemos aplicar el caso 1del Teorema Maestro y concluir que la solución es:

T (n) = Θ(n2)




T (n) = T (2n/3) + 1

Identificamos que para esta recurrencia a = 1, b = 3/2, f(n) = 1

Por lo tanto nlogb a = nlog3/2 1 = n0 = 1

Como f(n) = Θ(nlogb a) = Θ(1), podemos aplicar el caso 2 delTeorema Maestro y concluir que la solución es:

T (n) = Θ(lg n)




T (n) = 3T (n/4) + n lg n

Identificamos que para esta recurrencia a = 3, b = 4, f(n) = n lg n

Por lo tanto nlogb a = nlog4 3 = O(n0.793)

Como f(n) = Ω(nlog4 3+ε), donde ε ≈ 0.2 podemos aplicar el caso3 del Teorema Maestro si la condición de regularidad se cumplepara f(n)

Para n suficientemente grande, se tiene queaf(n/b) = 3(n/4) lg(n/4) ≤ (3/4)n lg n = cf(n) para c = 3/4

En consecuencia usando el caso 3 la solución de la recurrenciaes:

T (n) = Θ(n lg n)




T (n) = 2T (n/2) + n lg n

Identificamos que para esta recurrencia a = 2, b = 2, f(n) = n lg n

Por lo tanto nlogb a = nlog2 2 = n

Podría pensarse equivocadamente que podemos aplicar el caso 3del Teorema Maestro porque f(n) = n lg n es asintóticamentemás grande que nlogb a = n.

El problema es que no es polinomialmente más grande. La razónf(n)/nlogb a = (n lg n)/n = lg n es asintóticamente menor que nε

para cualquier constante ε > 0

En consecuencia la recurrencia cae en el gap los casos 2 y 3.




T (n) = 2T (n/2) + Θ(n)

Identificamos que para esta recurrencia a = 2, b = 2, f(n) = Θ(n)

Por lo tanto nlogb a = nlog2 2 = n

Como f(n) = Θ(nlogb a) = Θ(n), podemos aplicar el caso 2 delTeorema Maestro y concluir que la solución es:

T (n) = Θ(n lg n)




T (n) = 8T (n/2) + Θ(n2)

Identificamos que para esta recurrencia a = 8, b = 2,f(n) = Θ(n2)

Por lo tanto nlogb a = nlog2 8 = n3

Como n3 es polinomialmente más grande que f(n) (i.e.,f(n) = O(n3−ε) para ε = 1) podemos aplicar el caso 1 delTeorema Maestro y concluir que la solución es:

T (n) = Θ(n3)


Divide y vencerás Multiplicación de enteros grandes




Multiplicación de enteros grandes

El algoritmo que aprendemos en aritmética básica para multiplicar dosnúmeros de n dígitos, requiere multiplicar los n dígitos del primernúmero por cada uno de los n dígitos del segundo. Su complejidadtemporal es O(n2)

Existe una forma más eficiente de hacerlo que está inspirada en elmétodo ideado por Gauss para multiplicar número complejosEn este método en vez de usar la expresión

(a+ bi)(c+ di) = ac− bd+ (bc+ ad)i

que incluye cuatro multiplicaciones reales, se usa la ecuación

(a+ bi)(c+ di) = ac− bd+ ((a+ b)(c+ d)− ac− db)i



Multiplicación de enteros grandes

La misma idea se puede usar si descomponemos la cadena de bits delos números a multiplicar en mitades: x = 2n/2xL + xR

Una multiplicación directa, quedaría así:

xy = 2nxLyL + 2n/2(xLyR + xRyL) + xRyR

cuyo tiempo de ejecución está dado por la recurrenciaT (n) = 4T (n/2) +O(n), que es O(n2)

Sin embargo, es posible usar otra expresión:

xy = 2nxLyL + 2n/2 ((xL + xR)(yL + yR)− xLyL − xRyR) + xRyR

cuyo tiempo de ejecución es T (n) = 3T (n/2) +O(n).Esta reducción en el número de multiplicaciones toma lugar en cadallamada recursiva, ¡con lo que se obtiene una cota de O(n1.59)!


Divide y vencerás Divide y vencerás para cubiertas convexas




Divide y vencerás para cubiertas convexas

El problema de construcción de la cubierta convexa para unconjunto P de puntos en el plano pueden ser resuelto utilizandodiferentes enfoques

A continuación estudiaremos otro algoritmo de orden O(n log n) elcual está basado en la técnica de diseño conocida como Divide yVencerás

Puede ser vista como una generalización del famoso algoritmo deordenamiento MergeSort




Divide y Vencerás1 Ordenar los puntos en P de acuerdo a su coordenada x

2 Particiona el conjunto de puntos P en dos conjuntos A y B, dondeA consiste de los dn/2e puntos con las coordenadas x máspequeñas (izq.) y B los bn/2c puntos restantes (der.)

3 Calcula recursivamente HA = conv(A) y HB = conv(B)

4 Combina las dos cubiertas en una cubierta convexa, H, medianteel cálculo de las tangentes superior e inferior de HA y HB ydescartando todos los puntos que caen entre esas dos tangentes




El ordenamiento del primer paso garantiza que los conjuntos A yB estén separados por una línea vertical, lo cual asegura que A yB no se traslapan

Esto simplifica el paso de combinación (paso 4)

Los pasos 2, 3 y 4 se repiten en cada nivel de recursión,deteniéndose cuando n ≤ 3

Si n = 3 la cubierta es un triángulo (asumiendo que no hay 3puntos colineales)




El tiempo de ejecución asintótico del algoritmo puede expresarsemediante una relación de recurrencia

Dada una entrada de tamaño n, consideraremos el tiemponecesario para realizar todos los pasos del algoritmo, ignorandolas llamadas recursivas

Esto incluye el tiempo para:1 Particionar el conjunto de puntos,2 Calcular las dos tangentes, y3 Regresar el resultado final

Claramente los pasos 2 y 3 pueden ser realizados en tiempoO(n), asumiendo que los vértices de la cubierta sonrepresentados con una lista ligada




A continuación veremos como las tangentes pueden sercalculadas en tiempo O(n)

Por lo tanto, ignorando los factores constantes, podemos describirel tiempo de ejecución mediante la siguiente recurrencia:

T (n) =

1 si n ≤ 3n+ 2T (n/2) sino

(1)




Esta es la misma relación de recurrencia que surge en elalgoritmo MergeSort

Es fácil mostrar que T (n) ∈ O(n log n)

Solamente falta mostrar cómo calcular las dos tangentes

Algo que simplifica el proceso de calcular las tangentes es quelos dos conjuntos A y B están separados por una línea vertical

Esto asumiendo que los puntos no tienen coordenadas xduplicadas




Vamos a concentrarnos en la tangente inferior (la superior essimétrica)

El algoritmo funciona mediante un procedimiento simple de“caminata”

Inicializamos a como el punto más a la derecha de HA y b el mása la izquierda de HB (esto puede ser encontrado en tiempo lineal)




La tangencia inferior es una condición que puede ser verificadalocalmente mediante una prueba de orientación involucrando losdos vértices y vértices vecinos en la cubierta

Se iteran los siguientes dos ciclos, los cuales avanzan a y b hastaque ellos alcanzan los puntos de tangencia inferior




tangenteInferior(HA, HB)1 Sea a el punto más a la derecha de HA

2 Sea b el punto más a la izquierda de HB

3 While (ab no es una tangente inferior de HA y HB) do1 While (ab no es una tangente inferior de HA) do a← a.pred (movera )

2 While (ab no es una tangente inferior de HB) do b← b.succ (moverb )

4 Regresar ab




Dado un punto en la cubierta, sea a.succ y a.pred su sucesor ypredecesor en orden con respecto a la cubierta

La condición “ab no es una tangente inferior de HA” puede serimplementada con la prueba de orientaciónOrient(b, a, a.pred) ≤ 0

Esta prueba es similar con HB




Probar la correctez de este procedimiento es algo no tancomplicado, el secreto está en probar que los dos while internosnunca van más allá de los puntos de la tangente inferior

La prueba detallada puede ser consultada en el libro de O’Rourke

El punto importante es que cada vértice en la cubierta puede servisitado máximo una vez por cada búsqueda, y por lo tanto sutiempo es O(m), donde m = |HA|+ |HB| = |A|+ |B|

Esto es exactamente lo que se requiere para tener un tiempo deejecución O(n log n)


Divide y vencerás QuickHull para cubiertas convexas




QuickHull para cubiertas convexas

Si el algoritmo Divide y Vencerás puede ser visto como unageneralización del MergeSort, podríamos preguntarnos si existenlas generalizaciones correspondientes a otros algoritmos deordenamiento para calcular cubiertas convexas

En particular, el siguiente algoritmo que vamos a considerarpuede ser visto como la generalización del QuickSort

El algoritmo resultante es conocido como QuickHull




Al igual que el QuickSort corre en tiempo O(n log n) para entradasfavorables pero puede tomar tiempo O(n2) con datosdesfavorables

Sin embargo, a diferencia del QuickSort, no hay una forma obviade convertirlo en un algoritmo aleatorizado con tiempo deejecución esperado O(n log n)

No obstante, QuickHull tiende a desempeñarse muy bien en lapráctica




La intuición indica que en muchas aplicaciones la mayoría de lospuntos caen en el interior de la cubierta

Por ejemplo, si los puntos están uniformemente distribuídos en uncuadrado unitario, entonces puede ser mostrado que el númeroesperado de puntos en la cubierta convexa es O(log n)




La idea detrás del algoritmo QuickHull es descartar los puntosque no están en la cubierta tan pronto como sea posible

QuickHull comienza por calcular dos puntos extremos

Utilizaremos el punto x más a la derecha y más abajo y el punto ymás a la izquierda y más arriba

Claramente estos puntos deben estar en la cubierta




La cubierta convexa completa estará formada por una cubiertasuperior sobre xy y una cubierta inferior bajo xy

QuickHull encuentra estas cubiertas mediante un procedimientoque inicia con los puntos extremos (a, b)

Continua encontrando un tercer punto extremo c estrictamente ala derecha de ab

Elimina todos los puntos dentro del triángulo abc

Itera recursivamente en (a, c) y (c, b)




Sea S el conjunto de puntos estrictamente a la derecha de ab (Spodría estar vacío )

La idea clave es que el punto c ∈ S que está más alejado de abdebe estar en la cubierta convexa

De hecho es un punto extremo en la dirección ortogonal a ab

Por lo tanto se pueden eliminar todos los puntos sobre o dentrodel triángulo abc (excepto por a, b y c)




El resto de los puntos es dividido en dos subconjuntos A y B:A, contiene aquellos puntos que caen fuera (a la derecha) de acB, incluye aquellos puntos que caen fuera (a la derecha) de cb

Podemos clasificar cada punto p, calculando las orientaciones delas tripletas acp y cbp

Se reemplaza la arista ab con ac y cb para continuarrecursivamente el procedimiento




QuickHull(a, b, S)

1 if S = ∅ then return ∅2 else if S = a, b then return (a, b) (una arista de la cubierta)

3 elsec← índice del punto con máxima distancia de abA← conjunto de puntos estrictamente a la derecha de (a, b)B ← conjunto de puntos estrictamente a la derecha de (c, b)return QuickHull(a, c, A) ∪ (c) ∪QuickHull(c, b, B)




Ahora analizaremos de la complejidad temporal del algoritmoQuickHull

Encontrar los puntos extremos x y y, y particionar S en A y Bpuede ser realizado en tiempo O(n)

En cuanto a la función recursiva, supongamos que |S| = n,entonces toma n pasos determinar el punto extremo c

Pero el costo de las llamadas recursivas depende del tamaño delos conjuntos A y B




Sea |A| = α y |B| = β con α+ β ≤ n− 1 = O(n)

La suma es como máximo n− 1 porque c no está incluido ni en Ani en B

Si la complejidad temporal de llamar QuickHull con |S| = n esT (n), podemos expresar T recursivamente en términos de ellamisma

T (n) = O(n) + T (α) + T (β) (2)

Para resolver esta ecuación es necesario expresar α y β entérminos de n




Considerando el mejor caso posible, i.e. cuando cada divisiónestá lo más balanceada posible: α = β = n/2

Por lo tanto se tiene que

T (n) = O(n) + 2T (n/2) (3)

Esta relación de recurrencia, nos es familiar, y su solución es:T (n) = O(n log n)

Por lo tanto el mejor tiempo de ejecución para el algoritmoQuickHull es O(n log n) (cuando los puntos están aleatoriamentedistribuidos)




Por otra parte, el peor caso para este algoritmo ocurre cuando ladivisión está demasiado desbalanceada: α = 0 y β = n− 1

Se llega a la siguiente relación de recurrencia

T (n) = O(n) + T (n− 1) = cn+ T (n− 1) (4)

La expansión repetida de esta relación de recurrencia muestraque T (n) = O(n2)

Por lo tanto a pesar de que el algoritmo QuickHull esgeneralmente muy rápido, es cuadrático en el peor caso adiferencia del algoritmo de Graham cuyo peor caso es O(n log n)


dr. eduardo a. rodrÍguez tertello/algorithms/sesion12.pdf · divide y vencerás divide y vencerás...

Documents