PDF de programación - Algoritmos con Python - Intervalos

Imágen de pdf Algoritmos con Python - Intervalos

Algoritmos con Python - Intervalosgráfica de visualizaciones

Publicado el 7 de Marzo del 2021
147 visualizaciones desde el 7 de Marzo del 2021
204,3 KB
10 paginas
Creado hace 43d (01/03/2021)
Algoritmos con Python

Intervalos

1 de marzo de 2021

Índice

1 Árboles de intervalo

1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Estructura de datos con O(log n + m) por consulta . . . . . . . . . . . . . .
1.3 Elección del centro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Detalles de implementación . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Unión de intervalos

2.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Detalles de implementación . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 El problema de la cobertura del punto de intervalo

3.1 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Observación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
3
3
3
5

6
6
6
6

7
7
7
7
8

I

Introducción

Varios problemas relacionados con los intervalos pueden resolverse mediante programa-
ción dinámica. El conjunto de intervalos que están antes o después de un umbral puede
formar dos subinstancias independientes.

Si el problema lo permite, es conveniente utilizar intervalos semiabiertos de la forma [s,
t), ya que el número de enteros que contienen es fácil de calcular (aquí simplemente t -
s, siempre que s, t sean enteros).

1

1. Árboles de intervalo

1.1. Definición

El problema consiste en almacenar n intervalos dados en una estructura para responder
rápidamente consultas de la siguiente forma: para un valor p dado, ¿cuál es la lista de
todos los intervalos que contienen p? Suponemos que todos los intervalos son de la forma
semiabierta [l, h), pero la estructura se puede adaptar a otras formas.

1.2. Estructura de datos con O(log n + m) por consulta

Aquí, m es el número de intervalos devueltos. La estructura es un árbol binario construido
de la siguiente manera. Sea S un conjunto de intervalos para almacenar. Elegimos un
centro de valor como se describe a continuación. Este valor divide los intervalos en tres
grupos: el conjunto L de intervalos a la izquierda del centro, el conjunto C de intervalos
que contienen el centro y el conjunto R de intervalos a la derecha del centro. Luego, la raíz
del árbol almacena center y C, y de manera recursiva, los subárboles izquierdo y derecho
almacenan L y R, ver Figura 1.

Para responder rápidamente a las consultas, el conjunto C se almacena en forma de lis-
tas ordenadas. La lista by_low almacena los intervalos de C ordenados por sus extremos
izquierdos, mientras que la lista by_high almacena los intervalos de C ordenados por sus
extremos derechos.

Para responder a una consulta sobre un punto p, basta comparar p con el centro. Si p <
center, buscamos recursivamente intervalos que contengan p en el subárbol izquierdo y
sumamos los intervalos [l, h) de C con l p. Esto es correcto, ya que por construcción
estos intervalos satisfacen h>center y por lo tanto p ∈ [l, h). Si no, y p center,
entonces buscamos recursivamente intervalos que contengan p en el subárbol derecho y
sumamos los intervalos [l, h) de C con p<h.

2

Figura 1: Un árbol que almacena 7 intervalos

1.3. Elección del centro

Para que el árbol binario esté equilibrado, podemos elegir el centro como el valor mediano
de los extremos izquierdos de los intervalos que se almacenarán. Luego, la mitad de los
intervalos se almacenarán en el subárbol derecho, garantizando una profundidad loga-
rítmica. De manera similar al comportamiento del algoritmo de clasificación rápida, si el
centro se elige al azar entre los puntos finales de la izquierda, el rendimiento será similar
en expectativa.

1.4. Complejidad

La construcción del árbol toma tiempo O(n log n), y el procesamiento de una consulta
cuesta O(log n + m), donde el término logarítmico se debe a la búsqueda binaria en las
listas ordenadas.

1.5. Detalles de implementación

En nuestra implementación, los intervalos están representados por n-tuplas cuyos prime-
ros dos elementos contienen los puntos finales de un intervalo. Se pueden agregar otros

3

elementos para transportar información complementaria.

La búsqueda binaria se realiza mediante la función bisect_right(t, x), que devuelve i
tal que t[j]>x si y solo si j>i. Tenga en cuenta que no debe realizar un bucle en el array
by_high con la ayuda de la selección de sublista by_high [i:], ya que la creación de la
sublista es lineal en len(by_high), lo que aumenta la complejidad a O(log n + n) en
lugar de O(log n + m), donde m es el tamaño de la lista devuelta.

punto de inserción de un elemento x de la forma (p, (∞,∞)).

Las matrices contienen pares (valor, intervalo), por lo que buscamos con bisect_right el

class _Node:

def __init__(self, center, by_low, by_high, left, right):

self.center = center
self.by_low = by_low
self.by_high = by_high
self.left = left
self.right = right

def interval_tree(intervals):

if intervals == []:

return None

center = intervals[len(intervals) // 2][0]
L = []
R = []
C = []
for I in intervals:

if I[1] <= center:

L.append(I)

elif center < I[0]:

R.append(I)

else:

C.append(I)

by_low = sorted((I[0], I) for I in C)
by_high = sorted((I[1], I) for I in C)
IL = interval_tree(L)
IR = interval_tree(R)
return _Node(center, by_low, by_high, IL, IR)

def intervals_containing(t, p):

INF = float(inf)

4

if t is None:
return []

if p < t.center:

retval = intervals_containing(t.left, p)
j = bisect_right(t.by_low, (p, (INF, INF)))
for i in range(j):

retval.append(t.by_low[i][1])

else:

retval = intervals_containing(t.right, p)
i = bisect_right(t.by_high, (p, (INF, INF)))
for j in range(i, len(t.by_high)):
retval.append(t.by_high[j][1])

return retval

1.6. Variante

Si el objetivo es solo determinar el número de intervalos que contienen un valor dado, y
no la lista, entonces existe una solución mucho más simple con un algoritmo de línea de
barrido. Barremos los intervalos contenidos en un nodo de izquierda a derecha, avanzando
de un extremo al otro. En cualquier momento dado, mantenemos el número de intervalos
abiertos (es decir, aún no se ha visto el extremo derecho) y, por lo tanto, producimos una
matriz que contiene pares de la forma (x, k), de modo que para dos pares sucesivos
(x, k), (x, k), el número de intervalos que contienen p es k para x p < x.

5

2. Unión de intervalos

2.1. Definición

ordenada L de intervalos disjuntos, con la propiedad

Dado un conjunto S de n intervalos, deseamos determinar su unión, en forma de una lista

I∈S =

I∈L.

2.2. Algoritmo

La complejidad es O(n log n) usando un algoritmo de línea de barrido. Barremos los pun-
tos finales de los intervalos de izquierda a derecha. En un momento dado, mantenemos
en nb_open el número de intervalos abiertos (es decir, aún no se ha visto el extremo de-
recho). Cuando este número se vuelve cero, agregamos a la solución un nuevo intervalo
[last, x), donde x es la posición actual de la línea de barrido y last es la última posición
de barrido donde nb_open se volvió positivo.

2.3. Detalles de implementación

Tenga en cuenta el orden en el que se procesan los puntos finales de los intervalos. Este
orden es correcto cuando los intervalos están cerrados o semiabiertos. Para intervalos
abiertos, el final del intervalo (x, y) debe manejarse antes del comienzo del intervalo
(y, z).

def intervals_union(S):

E = [(low, -1) for (low, high) in S]
E += [(high, +1) for (low, high) in S]
nb_open = 0
last = None
retval = []
for x, _dir in sorted(E):

if _dir == -1:

if nb_open == 0:

last = x
nb_open += 1

else:

nb_open -= 1
if nb_open == 0:

retval.append((last, x))

return retval

6

3. El problema de la cobertura del punto de intervalo

3.1. Aplicación

Necesitamos instalar una cantidad mínima de antenas a lo largo de una playa recta para
brindar cobertura a una cantidad de pequeñas islas cercanas a la costa (¡tan pequeñas
como puntos individuales!).

Una antena puede cubrir todas las islas dentro de un radio determinado r (una lástima
para las islas más alejadas que r), que es el mismo para todas las antenas.

3.2. Observación

La intersección de la playa con un círculo de radio r dibujado alrededor de una isla define
un intervalo en la playa que debe contener una antena. Por tanto, el problema se reduce a
lo siguiente, consulte la Figura 2.

Figura 2: Cobertura de antenas

¿Cuántas antenas se necesitan para cubrir todas las islas? Este problema se reduce al problema de cobertura
de puntos de intervalo.

3.3. Definición

Para n intervalos dados, encuentre un conjunto mínimo de puntos S tal que cada intervalo
interseque a S.

7

3.4. Algoritmo

La complejidad es O(n log n) utilizando la técnica de la línea de barrido. Procesamos los
intervalos en orden creciente de su punto final correcto. En cada paso, mantenemos una
solución S para los intervalos ya vistos, que minimiza |S| y en caso de igualdad maximiza
max S.
El algoritmo es simple. Si para un intervalo [l, r] tenemos l max S, entonces no
hacemos nada, de lo contrario agregamos r a S. La idea es que en cualquier caso debemos
cubrir [l, r], y eligiendo el valor más grande que lo cubre, aumentamos la posibilidad de
cubrir adicionalmente intervalos posteriores.

Para estar convencido de la optimalidad, sea Sn la solución construida para el conjunto
de intervalos I1, . . . , In ya procesado. Obviamente, S1 es óptimo para I1. Suponga que Sn
es óptimo y considere In+1 = [l, r]. Cualquier l máx Sn, en cuyo caso Sn ya es una
solución óptima para In+1, o l > max Sn, y |Sn+1| = |Sn| + 1. E
  • Links de descarga
http://lwp-l.com/pdf18968

Comentarios de: Algoritmos con Python - Intervalos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad