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 cuyos lados son paralelos a los ejes. Podemos verlo a través de la parte superior. Sin embargo, también hay segmentos horizontales. Cada segmento tiene un entero -coordinado ( ) -coordinado ( ) y conecta los puntos 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.
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 )
Afortunadamente para nosotros, tanto como 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 .
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 .
Sin embargo, se me ocurrió un algoritmo más rápido:
Contorno:
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 x
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 } x segmento.
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 ).
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 2 está 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 .
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.
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?
- Si no, ¿cuál es la prueba de que el problema de visibilidad es ?
Respuestas:
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:max n L n longlongint
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 ...n n
fuente
long long int
como 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 ( nfind
tiempo? Entonces terminaríamos conOtotal(mnNo 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.
fuente