Algoritmos eficientes para problemas de visibilidad vertical

18

Al pensar en un problema, me di cuenta de que necesitaba crear un algoritmo eficiente para resolver la siguiente tarea:

El problema: se nos da una caja cuadrada bidimensional del lado n cuyos lados son paralelos a los ejes. Podemos verlo a través de la parte superior. Sin embargo, también hay m segmentos horizontales. Cada segmento tiene un entero y -coordinado ( 0yn ) x -coordinado ( 0x1<x2n ) y conecta los puntos (x1,y) y (x2,y) (mire el imagen debajo).

Nos gustaría saber, para cada segmento de la unidad en la parte superior de la caja, qué tan profundo podemos mirar verticalmente dentro de la caja si miramos a través de este segmento.

x{0,,n1}maxi: [x,x+1][x1,i,x2,i]yi

Ejemplo: dado y m = 7 segmentos situados como en la imagen siguiente, el resultado es (5, 5, 5, 3, 8, 3, 7, 8, 7) . Mira cuán profunda puede entrar la luz en la caja.m = 7 ( 5 , 5 , 5 , 3 , 8 , 3 , 7 , 8 , 7 )n=9m=7(5,5,5,3,8,3,7,8,7)

Siete segmentos;  la parte sombreada indica la región a la que se puede llegar con luz

Afortunadamente para nosotros, tanto n como m son bastante pequeños y podemos hacer los cálculos fuera de línea.

El algoritmo más fácil para resolver este problema es la fuerza bruta: para cada segmento atraviese toda la matriz y actualícela cuando sea necesario. Sin embargo, no nos da muy impresionante .O(mn)

Una gran mejora es utilizar un árbol de segmentos que pueda maximizar los valores en el segmento durante la consulta y leer los valores finales. No lo describiré más, pero vemos que la complejidad del tiempo es .O((m+n)logn)

Sin embargo, se me ocurrió un algoritmo más rápido:

Contorno:

  1. Ordene los segmentos en orden decreciente de coordenada (tiempo lineal usando una variación del orden de conteo). Ahora tenga en cuenta que si algún segmento de la unidad ha sido cubierto por algún segmento anteriormente, ningún segmento siguiente puede limitar el haz de luz que atraviesa este segmento de la unidad . Luego haremos un barrido de línea desde la parte superior a la inferior de la caja.x xyxx

  2. Ahora introduzcamos algunas definiciones: el segmento de la unidad es un segmento horizontal imaginario en el barrido cuyas coordenadas son enteros y cuya longitud es 1. Cada segmento durante el proceso de barrido puede estar sin marcar (es decir, un haz de luz que va desde la parte superior del cuadro puede alcanzar este segmento) o marcado (caso opuesto). Considere un segmento de unidad con , siempre sin marcar. También presentemos los conjuntos . Cada conjunto contendrá una secuencia completa de segmentos de unidades marcados consecutivos (si hay alguno) con los siguientes elementos sin marcarx x x 1 = n x 2 = n + 1 S 0 = { 0 } , S 1 = { 1 } , , S n = { n } xxxxx1=nx2=n+1S0={0},S1={1},,Sn={n} x segmento.

  3. Necesitamos una estructura de datos que pueda operar en estos segmentos y conjuntos de manera eficiente. Usaremos una estructura de búsqueda-unión extendida por un campo que contenga el índice máximo del segmento de la unidad (índice del segmento sin marcar ).x

  4. Ahora podemos manejar los segmentos de manera eficiente. Digamos que ahora estamos considerando el -ésimo segmento en orden (llámelo "consulta"), que comienza en y termina en . Necesitamos encontrar todos los segmentos de la unidad sin marcar que están contenidos dentro del segmento -ésimo (estos son exactamente los segmentos en los que el haz de luz terminará su camino). Haremos lo siguiente: en primer lugar, encontramos el primer segmento sin marcar dentro de la consulta ( Encuentre el representante del conjunto en el que está contenido y obtenga el índice máximo de este conjunto, que es el segmento sin marcar por definición ). Entonces este índicex 1 x 2 x i x 1 x y x x + 1 x x 2ix1x2 xix1xestá dentro de la consulta, agréguelo al resultado (el resultado para este segmento es ) y marque este índice ( conjuntos de unión que contienen y ). Luego repita este procedimiento hasta que encontremos todos los segmentos sin marcar , es decir, la siguiente consulta Buscar nos da el índice .yxx+1xx2

Tenga en cuenta que cada operación de búsqueda y unión se realizará solo en dos casos: comenzamos a considerar un segmento (que puede suceder veces) o acabamos de marcar un segmento de unidad (esto puede suceder veces). Por lo tanto, la complejidad general es ( es una función inversa de Ackermann ). Si algo no está claro, puedo elaborar más sobre esto. Quizás pueda agregar algunas fotos si tengo algo de tiempo.mxnO((n+m)α(n))α

Ahora llegué a "la pared". No puedo encontrar un algoritmo lineal, aunque parece que debería haber uno. Entonces, tengo dos preguntas:

  • ¿Existe un algoritmo de tiempo lineal (es decir, ) para resolver el problema de visibilidad del segmento horizontal?O(n+m)
  • Si no, ¿cuál es la prueba de que el problema de visibilidad es ?ω(n+m)
mnbvmar
fuente
¿Qué tan rápido clasificas tus segmentos m ?
babou
@babou, la pregunta especifica el orden de conteo, que como dice la pregunta, se ejecuta en tiempo lineal ("tiempo lineal usando una variación del orden de conteo").
DW
¿Intentaste barrer de izquierda a derecha? Todo lo que necesita es ordenar en y tanto en los pasos como en para caminar hacia la derecha. Entonces en total . x1x2O(m)O(m)O(m)
invalid_id
@invalid_id Sí, lo intenté. Sin embargo, en este caso, la línea de barrido debe reaccionar adecuadamente cuando se encuentra con el comienzo del segmento (en otras palabras, agregue el número igual a la coordenada del segmento al conjunto múltiple), se encuentra con el final del segmento (eliminar una ocurrencia de -coordinar) y generar el segmento activo más alto (valor máximo de salida en el conjunto múltiple). No he oído hablar de ninguna estructura de datos que nos permita hacer esto en tiempo constante (amortizado). yy
mnbvmar
@mnbvmar puede ser una sugerencia tonta, pero ¿qué tal una matriz de tamaño , barre y detiene cada celda . Para evry cell sabes max puedes ingresarlo en la matriz, además puedes hacer un seguimiento del máximo general con una variable. nO(n)y
invalid_id

Respuestas:

1
  1. Primero ordenar tanto y coordenadas de las líneas en dos matrices separadas y . x 2 A B O ( m )x1x2ABO(m)
  2. También mantenemos un tamaño de matriz de bits auxiliar para realizar un seguimiento de los segmentos activos.n
  3. Comience a barrer de izquierda a derecha:
  4. para(i=0,i<n,i++)
  5. {
  6. ..if exist con valory c O ( 1 )x1=iyc O(1)
  7. .. {
  8. .... encontrar ( )max
  9. .... tienda ( )O ( 1 )maxO(1)
  10. ..}
  11. ..if con valor y c O ( 1 )x2=iyc O(1)
  12. .. {
  13. .... encontrar ( )max
  14. .... tienda ( ) O ( 1 )maxO(1)
  15. ..}
  16. }

find ( ) se puede implementar usando una matriz de bits con n bits. Ahora, siempre que eliminemos o agreguemos un elemento a L , podemos actualizar este número entero estableciendo un bit en verdadero o falso respectivamente. Ahora tiene dos opciones dependiendo del lenguaje de programación utilizado y la suposición n es relativamente pequeña, es decir, más pequeña que l o n g l o n g i n t, que es al menos 64 bits o una cantidad fija de estos enteros:maxnLnlonglongint

  • Obtener el bit menos significativo en tiempo constante es compatible con algunos hardware y gcc.
  • Al convertir a un número entero O ( 1 ) obtendrá el máximo (no directamente, pero puede derivarlo).LO(1)

Sé que esto es un gran truco porque asume un valor máximo para y, por lo tanto, n puede verse como una constante entonces ...nn

identificación invalida
fuente
Como veo, suponiendo que tenga un procesador x86 de 64 bits, solo puede manejar . ¿Qué pasa si n está en el orden de millones? n64n
mnbvmar
Entonces necesitarás más números enteros. Con dos enteros, puede manejar hasta 128, etc. Por lo tanto, el paso de búsqueda máxima O ( m ) está oculto en la cantidad de enteros necesarios, que aún puede optimizar si m es pequeño. Usted mencionó en su pregunta que n es relativamente pequeño, así que supongo que no está en el orden de millones. Por cierto, long long int siempre tiene al menos 64 bits por definición, incluso en un procesador de 32 bits. nO(m)mn
invalid_id
Por supuesto que es cierto, el estándar C ++ se define long long intcomo un tipo entero de al menos 64 bits. Sin embargo, no será que si es enorme y denotamos el tamaño de la palabra como w (generalmente w = 64 ), entonces cada uno tomará O ( nnww=64findtiempo? Entonces terminaríamos conOtotal(mnO(nw). O(mnw)
mnbvmar
Sí, desafortunadamente para grandes valores de ese es el caso. Así que ahora me pregunto qué tan grande será n en su caso y si está limitado. Si realmente es del orden de millones, este corte ya no funcionará, pero si c w n para valores bajos de c será rápido y prácticamente O ( n + m ) . Entonces, la mejor opción de algoritmo es, como de costumbre, dependiente de la entrada. Por ejemplo, para n 100 la ordenación por inserción es normalmente más rápida que la ordenación por fusión, incluso con un tiempo de ejecución de O ( n 2 ) en comparación connncwncO(n+m)n100O(n2) . O(nlogn)
invalid_id
3
Estoy confundido por su elección de formato. Sabes que puedes escribir código aquí, ¿verdad?
Raphael
0

No tengo un algoritmo lineal, pero este parece ser O (m log m).

Ordenar los segmentos según la primera coordenada y la altura. Esto significa que (x1, l1) siempre viene antes (x2, l2) siempre que x1 <x2. Además, (x1, l1) a la altura y1 viene antes (x1, l2) a la altura y2 siempre que y1> y2.

Para cada subconjunto con la misma primera coordenada, hacemos lo siguiente. Deje que el primer segmento sea (x1, L). Para todos los demás segmentos del subconjunto: si el segmento es más largo que el primero, cámbielo de (x1, xt) a (L, xt) y agréguelo al subconjunto L en el orden correcto. De lo contrario, déjalo caer. Finalmente, si el siguiente subconjunto tiene una primera coordenada menor que L, luego divida el (x1, L) en (x1, x2) y (x2, L). Agregue (x2, L) al siguiente subconjunto en el orden correcto. Podemos hacer esto porque el primer segmento en el subconjunto es más alto y cubre el rango de (x1, L). Este nuevo segmento puede ser el que cubre (L, x2), pero no lo sabremos hasta que veamos el subconjunto que primero tiene la coordenada L.

Después de recorrer todos los subconjuntos, tendremos un conjunto de segmentos que no se superponen. Para determinar cuál es el valor de Y para una X dada, solo tenemos que recorrer los segmentos restantes.

Entonces, ¿cuál es la complejidad aquí: el tipo es O (m log m). Recorriendo los subconjuntos está O (m). Una búsqueda también es O (m).

Entonces parece que este algoritmo es independiente de n.

Nadie en particular
fuente