Greedy: Interval Scheduling & Interval Partitioning Problem

Question 1

¿Para qué tipo de problemas es la metodología de resolución greedy?

Answer 1

Para problemas de optimización (maximización o minimización).

Question 2

¿Cómo funciona Greedy?

Answer 2

Greedy divide al problema en subproblemas, con una jerarquía entre ellos.

Cada subproblema se va resolviendo iterativamente mediante una elección heurística, habilitsndo nuevos subproblemas.

Question 3

¿Todos los problemas pueden resolverse por el mismo algoritmo Greedy? ¿Todos resultan en la solución óptima?

Answer 3

No.

Para cada problema, existen diferentes algoritmos Greedy, y no todos resultan en la solución óptima.

Además, no todos los problemas pueden resolverse mediente un algoritmo greedy (no todos llegan a soluciones óptimas), para ello deben tener ciertas propiedades.

Question 4

¿Cuáles son las propiedades requeridas para una resolución óptima con un algoritmo Greedy?

Answer 4

1. Elección Greedy

• Seleccionar una solución local óptima, esperando que la misma nos acerque a la solución óptima global.
• Analizar el conjunto de los elementos del problema en el estado en que llegaron al mismo y elegir heurísticamente “la mejor solución” local.
• Un subproblema está condicionado por las elecciones de los anteriores subproblemas y así mismo condiciona a los subproblemas siguientes.

2. Subestructura Óptima

• Un problema contiene una subestructura óptima si la solución óptima global del mismo contiene en su interior a las soluciones óptimas de sus subproblemas.
• La elección greedy resolverá iterativamente los subproblemas de forma óptima y los llevará a la solución óptima global.

Question 5

Indique los 6 pasos en la construcción de una estrategia Greedy

Answer 5

1. Determinar la subestructura óptima del problema
2. Construir una solución recursiva
3. Mostrar que si realizamos la elección greedy, nos quedaremos en última instancia con sólo 1 subproblema.
4. Mostrar que la elección greedy se puede realizar siempre y de forma segura.
5. Construir el algoritmo recursivo que solucione el problema.
6. Convertir el algoritmo recursivo en uno iterativo.

Question 6

Describa el problema de Interval Scheduling

Answer 6

Sea P un conjunto de n pedidos {p1, p2, ..., pn}.

Cada pedido i tiene un tiempo s_i donde inicia y un tiempo t_i donde finaliza.

Lo que se quiere hacer es seleccionar el subconjunto de P de mayor tamaño posible de modo que todas las tareas seleccionadas sean compatibles entre sí.

Question 7

¿Cuándo un par de tareas son compatibles?

Answer 7

Un par de tareas son compatibles si y sólo si no hay solapamiento en el tiempo entre ellas.

Question 8

Interval Scheduling: ¿Cuáles son las heurísticas que no funcionan y cuál es la que sí lo hace?

Answer 8

Las que no funcionan:
- Aquel que comienza antes
- Aquel que dura menos tiempo
- Aquel que tiene menos incompatibilidades

La que sí funciona:
- Aquel que termina antes.

Question 9

Explique el comportamiento del algoritmo tradicional de Interval Scheduling (O(n^2))

Answer 9

Sea P un set de pedidos
Sea A el subconjunto máximo

Mientras P no esté vacío
        Sea i el pedido en P con menor tiempo de finalización
        A += i

        Quitar de P todos los pedidos incompatibles con i

Retornar A

Question 10

Resolver:

Evento A: Inicia a las 9:00 y termina a las 10:30 (duración de 1.5 horas).

Evento B: Inicia a las 10:15 y termina a las 11:45 (duración de 1.5 horas).

Evento C: Inicia a las 11:00 y termina a las 12:30 (duración de 1.5 horas).

Evento D: Inicia a las 12:00 y termina a las 13:30 (duración de 1.5 horas).

Evento E: Inicia a las 13:15 y termina a las 14:45 (duración de 1.5 horas).

Answer 10

{a, c, e}

Question 11

Optimalidad: Explique cómo se verifica que la solución A del problema de Interval Scheduling es óptima

Answer 11

No se puede asegurar que A = O.

Pero podemos ver que |A| = |O|.
Esto significa que el número de elementos en el conjunto A es igual al número de elemntos en el conjunto O.
=> El algoritmo encontró una solución con la misma cantidad de elementos que la óptima.

Si A no fuese óptimo, O debería tener más pedidos. Como no los tiene, se dice que A es óptimo.

Question 12

¿El algoritmo Greedy retorna siempre un set A óptimo para Interval Scheduling?

Answer 12

Sí.

Question 13

¿Cuál es la implementación eficiente de Interval scheduling?

Answer 13

• Ordenamos los pedidos por tiempo de finalización
• Iteramos, ignorando los incompatibles y seleccionando el próximo disponible, y guardando el tiempo de finalización del último elemento elegido (para poder comparar).

Question 14

¿Cuál es la complejidad de Interval Scheduling (implementación eficiente) en cada una de sus partes, y cuál es la complejidad temporal y espacial general?

Answer 14

• El proceso de ordenamiento es O(n logn)
• La iteración es O(n)

=> Entonces:
- La complejidad temporal es O(n logn)
- La complejidad espacial es O(n)

Question 15

Interval Scheduling: Con los siguientes pedidos, resolver.

evento	s	f
a		4	6
b		2	5
c		1	3
d		6	8
e		3	7

Answer 15

A = {c,a,d}

Question 16

Describa el Interval Partitioning Problem

Answer 16

Sea E un conjunto de n eventos {e1, e2, ..., en}.
Sea S un conjunto de salas.

Cada evento e tiene:
- Una fecha de inicio f_s
- Una fecha de finalización f_e

Se quiere asignar cada evento a una sala, minimizando la cantidad de salas utilizadas.

Question 17

¿Cómo se le llama al número máximo de salas necesarias en Interval Partitioning Problem?

Answer 17

Se le llama profundidad.

Question 18

Explique qué implica la solución eficiente (no mejorada, O(n^2) de complejidad) de Interval Partitioning Problem.
Describa el pseudocódigo.

Answer 18

Sea d la profundidad del conjunto de eventos:

1. Usamos etiquetas {1, 2, …, d} para asignar eventos a una sala.
2. Ordenamos los eventos por su fecha de inicio (O(n logn)).
3. Iteramos por los eventos ordenados, etiquetando uno a uno con una etiqueta que no haya sido asignada previamente a un evento que se superpone.

Sea E el set de eventos.
Ordenar E según fecha de inicio.

Por cada evento Ej:
        Por cada evento Ei que precede a Ej y con el que se superpone:
                  Excluir la etiqueta de Ei para Ej

       Si existe una etiqueta {1, 2, ..., d} que no fue excluida:
              Asignar la menor etiqueta posible a Ej
       De lo contrario:
              Dejar Ej sin etiquetar

Retornar los eventos etiquetados.

Question 19

Resuelva Interval Partitioning Problem:
evento s f
a 1 8
b 2 6
c 6 9
d 10 11
e 3 4
f 5 7

Answer 19

• Etiqueta 1: a, d
• Etiqueta 2: b, c
• Etiqueta 3: e, f

Question 20

¿Qué complejidad tiene Interval Partitioning Problem (forma no mejorada)? Explique parte por parte, y en general.

Answer 20

• Ordenar es O(n logn)
• Iterar por cada evento es O(n)
• Verificar por cada evento anterior es O(n)

=> Complejidad total es O(n^2)

Question 21

Interval Partitioning Problem: ¿Puede quedar un evento sin etiquetar?

Answer 21

En el peor de los casos, podemos llegar hasta la etiqueta d (profundidad). Podría quedar un evento sin etiquetar.

Question 22

Interval Partitioning Problem: ¿Pueden dos eventos superpuestos tener la misma etiqueta?

Answer 22

No, por diseño del algoritmo.

Question 23

Interval Partitioning Problem: ¿Puedo asignar cualquier etiqueta?

Answer 23

No, siempre se van reutilizando las etiquetas a medida que se van liberando.

Question 24

Interval Partitioning Problem: ¿Cómo se puede mejorar la eficiencia?

Answer 24

• Podemos evitar tener uan segunda iteración de eventos usando una estructura de datos diferente.
• También nos interesa conocer la primer etiqueta disponible, por cada etiqueta podríamos almacenar la fecha de liberación.
• Si la fecha de inicio del evento es anterior a la liberación, necesitamos una sala nueva. Sino, se asigna y se actualiza la fecha.

=> Se puede usar un heap de mínimos.

Question 25

Interval Partitioning Problem: Describa el algoritmo mejorado

Answer 25

- Sea E los eventos ordenados por fecha de inicio. - Sea Q una cola de prioridad - Sea u la última sala usada ``` 1. Tomar el primer evento, asignar la primer etiqueta. 2. Agregar a la cola de prioridad la etiqueta con la fecha de finalización del primer evento. 3. Para todos los otros eventos, repetir lo siguiente: a) Obtener el minimo de Q. b) si la liberación del minimo es menor al tiempo de inicio del evento, actualizar la etiqueta de u en Q con el tiempo finalización del evento. c) Si no es menor, sumar 1 a la etiqueta, y guardar en Q la etiqueta nueva con el tiempo de finalización del evento. 4. Retornar los eventos etiquetados. ```

Question 26

Interval Partitioning Problem: Con los siguientes pedidos, resolver a) con método no mejorado (O(n^2)) b) con método mejorado (O(n logn)) evento s f a 4 6 b 2 5 c 1 3 d 6 8 e 3 7

Answer 26

Etiquetas: 1: c, e 2: b, d 3: a

Question 27

Interval Partitioning Problem: Explique la complejidad del algoritmo mejorado, parte por parte y de forma general.

Answer 27

- Ordenar es `O(n logn)` - Usar un heap es `O(logn)` para `push` y `O(1)` para `pop`. - Se itera 1 vez por cada evento, y por cada evento, se hacen operaciones de heap. => Complejidad total: `O(n logn)`

Question 28

¿Qué es la **latencia**?

Answer 28

La latencia es "cuánto tarda en terminar un evento, una vez pasado el deadline". Si una tarea se prorgama para comenzar en el tiempo `s`, dura un tiempo `t` y su deadline es `d`, decimos que la latencia es: ``` l = s + t - d, si es mayor o igual a cero ó l = 0, si la suma es menor a cero ```

Question 29

Describa el modelo de planificación para minimizar la latencia

Answer 29

Sea `P` un conjunto de `n` pedidos `{p1, p2, ..., pn}`. Cada pedido `i` tiene: - Una duración `ti` no fraccionable - Una fecha de entrega (deadline) `di`. Queremos programar el inicio de cada uno de los pedidos a realizar sin superposición, de forma de minimizar la máxima latencia.

Question 30

¿Qué es la latencia máxima?

Answer 30

La latencia máxima de una secuencia de pedidos programados es la máxima de esas latencias.

Question 31

Latencia: explique el pseudocódigo. ¿La solución deja tiempos muertos? ¿Existe una solución óptima?

Answer 31

1. Ordenar los pedidos en función de su deadline. 2. Hora de finalización, 0 3. Recorriendo los pedidos: a. Asignar el pedido `i` al intervalo que comienza en `f` b. Sumar a f la duración del pedido, actualizando su valor. 4. Retornar el set de intervalos programados. --- La solución no deja tiempos muertos ni de inactividad, y podemos afirmar que existe una solución óptima sin tiempos muertos.

Question 32

Latencia: Tenemos los siguientes pedidos: - 1 = (1,2) - 2 = (3,6) - 3 = (2,4) ¿Cómo los programamos?

Answer 32

Debemos programarlos de acuerdo al deadline (del más cercano al más lejano), para minimizar la latencia. (1, 3, 2)

Question 33

¿Qué son las inversiones?

Answer 33

Sea `A'` una programación de pedidos, decimos que `A'` tiene una inversión si un pedido `i (ti, di)` está programado antes que otro pedido `j (tj, dj)`, siendo que el deadline de `j` es menor que el deadline de `i`.

Question 34

¿Qué posibles casos de inversiones hay? ¿Resolver una inversión, qué resultados puede tener?

Answer 34

1. Ambos deadlines ocurren después de la finalización de los pedidos. Intercambiar no empeora la latencia total, sigue siendo óptimo. 2. Los deadlines ocurren antes de los pedidos, intercambiarlos *podría* mejorar la latencia. En general, resolver una inversión mejora o mantiene la latencia máxima, pero no la empeora.

Question 35

Interval Partitioning Problem: Sean B, C programaciones diferentes y sin inversiones ni tiempos muertos, ¿entonces qué tiempo de latencia tienen B y C?

Answer 35

Si B y C no tienen inversiones ni tiempos muertos, pero son diferentes, entonces existen pedidos que comparten el mismo deadline. Por lo tanto B y C tienen el mismo tiempo de latencia total, porque invertir el orden de esos pedidos no altera la latencia máxima.

Question 36

Interval Partitioning Problem: ¿Qué pasa si B y C no tienen inversiones, pero son diferentes?

Answer 36

Si B y C no tienen inversiones, pero son diferentes, entonces existen pedidos que comparten el mismo deadline. Invertir el orden de esos pedidos no altera la latencia máxima.

Question 37

Interval Partitioning Problem: ¿Qué se debe hacer mientras exista una inversión?

Answer 37

Mientras exista una inversión, se van a realizar intercambios. Al finalizar, nos quedaremos con una programación óptima, sin inversiones.

Question 38

Interval Partitioning Problem: ¿Por qué la solución por Greedy es óptima?

Answer 38

Sea A una programación sin inversiones ni tiempos muertos. - Existe una programación sin tiempos muertos y sin inversiones. - Cualquier programación sin tiempos muertos e inversiones es equivalente a otra de iguales características (como el óptimo). - El algoritmo Greedy retorna una programación sin tiempos muertos e inversiones. => La solución entregada por Greedy es óptima.