Dado un nodo de origen, nodo de destino y nodos intermedios, ¿cómo se detecta si la distancia más corta de Manhattan está bloqueada?

Question

Aquí es el título completo habría publicado, pero pasa a ser demasiado largo:

Dado un nodo de origen, el nodo dest, y los nodos intermedios, ¿cómo se puede detectar si el menor distancia de Manhattan está bloqueado por los nodos intermedios?

He dibujado un diagrama para que sea más clara. En el lado izquierdo, "u" es el nodo fuente y "v" es el nodo de destino. Los nodos etiquetados del 1 al 6 son los nodos intermedios. La distancia más corta a Manhattan desde u -> v sería 12, pero los nodos intermedios forman un muro que la bloquea. El diagrama de la derecha, donde u 'es la fuente y v' el destino, muestra que los nodos intermedios 1 a 5 no bloquean la distancia más corta de Manhattan desde u 'a v'.

Estoy tratando de encontrar un algoritmo que no me obligue a realizar una búsqueda de gráficos (por ejemplo, BFS), porque la distancia entre u y v podría ser muy grande.

Answer 1

Si todo lo que quiere hacer es detectar si la ruta más corta (una que consiste en movimientos monótonamente en la dirección correcta) está bloqueada, entonces está tratando de verificar si los nodos de bloqueo cortan el rectángulo cuyas esquinas están dadas por el nodo de origen y destino en dos regiones diferentes que están desconectadas. Si no es posible un camino más corto desde el origen hasta el destino, entonces cada ruta debe tener algún punto que esté bloqueado.

Supongamos por simplicidad que su punto de inicio está debajo ya la izquierda del punto de destino. En ese caso, encuentre, en O (n), todos los otros puntos que son puntos de obstáculo contenidos en el cuadro delimitador que contiene el punto inicial y final. Ahora quiere ver si hay algún subconjunto de esos nodos que corta el rectángulo en dos partes, una que contiene la esquina inferior izquierda y otra que contiene la esquina superior derecha. Esto es posible si hay una ruta de los nodos de bloqueo desde el lado izquierdo al lado derecho, desde el lado izquierdo al lado inferior, desde el lado superior al lado derecho, o desde el lado superior al lado inferior. Por lo tanto, solo debemos verificar si alguno de estos es posible.

Afortunadamente, esto se puede hacer eficientemente modelando el problema como una búsqueda de gráfico en un gráfico que tiene tamaño O (n), donde n es el número de puntos de bloqueo y no tiene nada que ver con el tamaño del límite caja. Es decir, no importa qué tan separados estén los puntos de prueba, el tamaño del gráfico para buscar depende únicamente de la cantidad de puntos de bloqueo.

El gráfico que desea construir tiene dos partes. Primero, construya un gráfico donde cada punto de bloqueo esté conectado a cada otro punto de bloqueo en el cuadrado de 3x3 que lo rodea. Estos bordes unen los puntos de bloqueo que podrían formar parte de la misma barrera, ya que ningún camino desde la fuente al objetivo podría pasar entre dos puntos de bloqueo unidos por un borde. Ahora, agregue cuatro nuevos nodos que representen la pared superior, la pared izquierda, la pared derecha y la pared inferior y conéctelos a cada nodo adyacente a la pared correspondiente. De esta forma, por ejemplo, una ruta desde el nodo de la pared izquierda hasta el nodo de la pared derecha representaría una serie de nodos de bloqueo que hacen imposible llegar desde el nodo inferior izquierdo al nodo superior derecho.

Este gráfico tiene el tamaño O (n), donde n es el número de nodos de bloqueo, ya que hay O (n) nodos y cada nodo puede tener como máximo 12 bordes, uno para cada uno de los 8 vecinos y potencialmente para cada una de las cuatro paredes. Podrías construirlo en el peor tiempo cuadrático escaneando sobre cada nodo y, para cada otro nodo, ver si son adyacentes. Probablemente haya una mejor manera de hacerlo, pero en este momento no se me ocurre nada.

Ahora que tiene el gráfico, para cada uno de los pares de paredes que, si están conectados, desconectarían el gráfico, ejecute una búsqueda de gráfico en este gráfico entre esos dos nodos de pared. Si existe una ruta, informe que la ruta más corta está bloqueada. De lo contrario, informe que se ha desbloqueado el camino más corto. Estas búsquedas podrían realizarse con un DFS simple, o dado que está ejecutando múltiples búsquedas y solo quiere saber si están conectadas, usando un algoritmo de componentes fuertemente conectados una vez y verificando si hay un par de nodos importantes en el mismo SCC. Cualquiera de los enfoques toma tiempo O (n).

Por lo tanto, el tiempo para resolver este problema es como máximo O (n), siendo el cuello de botella el tiempo requerido para construir el gráfico.

Espero que esto ayude!

Answer 2

Aquí es mi idea:

Voy a describir el caso cuando el destino es superior ya la derecha de la fuente, para otros casos, gire. (Para casos simples donde los nodos tienen la misma coordenada x/y, solo comprueba si hay un nodo de bloqueo directamente entre ellos)

Tome la matriz con origen y destino en las esquinas. Ahora, una columna a la vez, de izquierda a derecha y dentro de la columna, de abajo hacia arriba, marca nodos bloqueados. Un nodo B es bloqueado si y sólo si cualquiera de los siguientes es verdadera:

• B es un nodo intermedio
• los nodos de izquierda a B y la parte inferior de B están ambos bloqueado (ambos ya fueron verificados dado el orden de procesamiento) o fuera de los límites de la matriz

Al final, si el destino es bloqueado, no hay una ruta libre más corta.

El tiempo requerido es O (m * n), donde m, n son las longitudes de los lados de la matriz. Entonces, cuando solo tenga varios nodos intermedios, la solución de templatetypedef puede ser más apropiada.

EDITAR: Lo tengo un poco mal anteriormente, ahora espero que no me perdí nada