Encontrar la cobertura mínima de un intervalo con subintervalos

Question

Supongamos que tengo un intervalo (a, b), y un número de subintervalos {(un _i, b _i)} _i cuya unión es todo (a, b). ¿Existe una manera eficiente de elegir un subconjunto de cardinalidad mínima de estos subintervalos que todavía cubre (a, b)?

Answer 1

Un algoritmo ambicioso que comienza en aob siempre da la solución óptima.

Prueba: considere el conjunto S _a de todos los subintervalos que cubren a. Claramente, uno de ellos debe pertenecer a la solución óptima. Si reemplazamos con un subintervalo (un _máximo, b _máximo) de S _un cuyo derecho de punto final b _máximo es máxima en S _{un (alcanza más a la derecha), el intervalo descubierto} restante (b _max, b) será un subconjunto del intervalo restante de la solución óptima, por lo que puede cubrirse con no más subintervalos que el intervalo descubierto análogo de la solución óptima.Por lo tanto, una solución construida a partir de (a _max, b _max) y la solución óptima para el intervalo restante (b _max, b) también será óptima.

Por lo tanto, simplemente comience en a y elija iterativamente el intervalo que se extiende más a la derecha (y cubriendo el final del intervalo anterior), repita hasta que pulse b. Creo que puede elegir el siguiente intervalo en log (n) si almacena los intervalos en un árbol de intervalos aumentados.

Answer 2

Suena como la programación dinámica.

Aquí es una ilustración del algoritmo (asumen intervalos están en una lista ordenada por hora de finalización):

//works backwards from the end 
int minCard(int current, int must_end_after) 
{ 
    if (current < 0) 
     if (must_end_after == 0) 
      return 0; //no more intervals needed 
     else 
      return infinity; //doesn't cover (a,b) 

    if (intervals[current].end < must_end_after) 
     return infinity; //doesn't cover (a,b) 

    return min(1 + minCard(current - 1, intervals[current].start), 
       minCard(current - 1, must_end_after)); 
      //include current interval or not? 
} 

sino que también debe implicar el almacenamiento en caché (memoisation).

Answer 3

¿Quiere decir que los subintervalos todavía se superponen de tal manera que (a, b) permanece completamente cubierto en todos los puntos?

Tal vez dividiendo los subintervalos en bloques básicos asociados con su origen, por lo que puede enumerar las opciones para cada intervalo de bloque básico que representa otras regiones cubiertas por el subintervalo también. Luego puede usar una búsqueda basada en cada subintervalo secundario y al menos asegurarse de que no queden espacios vacíos.
Entonces tendría que buscar ... de manera eficiente ... eso sería más difícil.

Podría eliminar cualquier colección de intervalos que estén completamente cubiertos por otro conjunto de números más pequeños y resolver el problema después del preprocesamiento.
¿No sería el mínimo para el conjunto mínimo de al menos la mitad? No estoy seguro.

Encontrado un link en un diario pero no pudo leerlo. :(

Esto sería un problema hitting set y se NP_hard en general.
No se pudo leer this tampoco, pero parece que tipo opuesto del problema.
no podía leer, pero otra link que menciona a intervalos de separarse.
Here es una referencia disponible en aleatorios algoritmos para GeometricOptimization problemas.
Página 35 de este pdf tiene un algoritmo voraz.
Página 11 de Karp (1972) menciones golpear-set y se cita mucho.
Google result. Investigar fue divertido, pero tengo que irme ahora.

Answer 4

Hay dos casos a considerar: Caso 1: No hay intervalos de solapamiento después del tiempo de finalización de un intervalo. En este caso, elija el siguiente intervalo con el tiempo de inicio más pequeño y el tiempo de finalización más largo. (amin, bmax). Caso 2: hay 1 o más intervalos de solapamiento con el último intervalo que está mirando. En este caso, la hora de inicio no importa porque ya has cubierto eso. Así que optimiza para el tiempo de finalización. (a, bmax).

Caso 1 siempre elige el primer intervalo como el primer intervalo en el conjunto óptimo también (la prueba es la misma que la proporcionada por @RafalDowgrid).