Greedy: Interval Scheduling & Interval Partitioning Problem Flashcards
¿Para qué tipo de problemas es la metodología de resolución greedy?
Para problemas de optimización (maximización o minimización).
¿Cómo funciona Greedy?
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.
¿Todos los problemas pueden resolverse por el mismo algoritmo Greedy? ¿Todos resultan en la solución óptima?
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.
¿Cuáles son las propiedades requeridas para una resolución óptima con un algoritmo Greedy?
- 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.
- 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.
Indique los 6 pasos en la construcción de una estrategia Greedy
- Determinar la subestructura óptima del problema
- Construir una solución recursiva
- Mostrar que si realizamos la elección greedy, nos quedaremos en última instancia con sólo 1 subproblema.
- Mostrar que la elección greedy se puede realizar siempre y de forma segura.
- Construir el algoritmo recursivo que solucione el problema.
- Convertir el algoritmo recursivo en uno iterativo.
Describa el problema de Interval Scheduling
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í.
¿Cuándo un par de tareas son compatibles?
Un par de tareas son compatibles si y sólo si no hay solapamiento en el tiempo entre ellas.
Interval Scheduling: ¿Cuáles son las heurísticas que no funcionan y cuál es la que sí lo hace?
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.
Explique el comportamiento del algoritmo tradicional de Interval Scheduling (O(n^2))
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 AResolver:
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).
{a, c, e}
Optimalidad: Explique cómo se verifica que la solución A del problema de Interval Scheduling es óptima
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.
¿El algoritmo Greedy retorna siempre un set A óptimo para Interval Scheduling?
Sí.
¿Cuál es la implementación eficiente de Interval scheduling?
- 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).
¿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?
- 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)
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
A = {c,a,d}
Describa el Interval Partitioning Problem
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.
¿Cómo se le llama al número máximo de salas necesarias en Interval Partitioning Problem?
Se le llama profundidad.
Explique qué implica la solución eficiente (no mejorada, O(n^2) de complejidad) de Interval Partitioning Problem.
Describa el pseudocódigo.
Sea d la profundidad del conjunto de eventos:
- Usamos etiquetas {1, 2, …, d} para asignar eventos a una sala.
- Ordenamos los eventos por su fecha de inicio (O(n logn)).
- 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.
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
- Etiqueta 1:
a, d - Etiqueta 2:
b, c - Etiqueta 3:
e, f
¿Qué complejidad tiene Interval Partitioning Problem (forma no mejorada)? Explique parte por parte, y en general.
- 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)
Interval Partitioning Problem: ¿Puede quedar un evento sin etiquetar?
En el peor de los casos, podemos llegar hasta la etiqueta d (profundidad). Podría quedar un evento sin etiquetar.
Interval Partitioning Problem: ¿Pueden dos eventos superpuestos tener la misma etiqueta?
No, por diseño del algoritmo.
Interval Partitioning Problem: ¿Puedo asignar cualquier etiqueta?
No, siempre se van reutilizando las etiquetas a medida que se van liberando.
Interval Partitioning Problem: ¿Cómo se puede mejorar la eficiencia?
- 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.
