Algoritmo para encontrar dos puntos más alejados el uno del otro

StackOverflow https://stackoverflow.com/questions/477591

Pregunta

Estoy buscando un algoritmo para usar en un juego de carreras que estoy haciendo. El mapa / nivel / seguimiento se genera aleatoriamente, por lo que necesito encontrar dos ubicaciones, inicio y objetivo, que aprovechen al máximo el mapa.

  • El algoritmo es trabajar dentro de un espacio bidimensional
  • Desde cada punto, uno solo puede atravesar el siguiente punto en cuatro direcciones; arriba, abajo, izquierda, derecha
  • Los puntos solo se pueden bloquear o no bloquear, solo los puntos no bloqueados se pueden atravesar

Con respecto al cálculo de la distancia, no debe ser el '' camino del pájaro '' por falta de una palabra mejor. El camino entre A y B debería ser más largo si hay una pared (u otra área de bloqueo) entre ellos.

No estoy seguro de por dónde empezar, los comentarios son muy bienvenidos y las soluciones propuestas se prefieren en pseudocódigo.

Editar: Derecha. Después de mirar código de gs I Le di otra oportunidad. En lugar de Python, esta vez lo escribí en C ++. Pero aún así, incluso después de leer sobre algoritmo Dijkstras , el floodfill y Solución Hosam Alys , no puedo detectar ninguna diferencia crucial. Mi código aún funciona, pero no tan rápido como parece que está ejecutando el suyo. La fuente completa está en pastie . Las únicas líneas interesantes (supongo) es la variante Dijkstra en las líneas 78-118.

Pero la velocidad no es el problema principal aquí. Realmente agradecería la ayuda si alguien tuviera la amabilidad de señalar las diferencias en los algoritmos.

  • En el algoritmo Hosam Alys, ¿es la única diferencia que escanea desde los bordes en lugar de cada nodo?
  • En Dijkstras, realiza un seguimiento y sobrescribe la distancia recorrida, pero no en el relleno, ¿pero eso es todo?
¿Fue útil?

Solución

Suponiendo que el mapa es rectangular, puede recorrer todos los puntos de borde e iniciar un relleno de inundación para encontrar el punto más distante desde el punto de partida: 

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

Supongo que esto estaría en O (n ^ 2) . Si no me equivoco, es (L + W) * 2 * (L * W) * 4 , donde L es la longitud y W es el ancho del mapa, (L + W) * 2 representa el número de puntos de borde sobre el perímetro, (L * W) es el número de puntos, y 4 es la suposición de que el relleno de inundación accedería a un punto un máximo de 4 veces (desde todas las direcciones). Como n es equivalente al número de puntos, esto es equivalente a (L + W) * 8 * n , que debería ser mejor que O (n 2 ) . (Si el mapa es cuadrado, el orden sería O(16n1.5 ) .)

Actualización: según los comentarios, ya que el mapa es más un laberinto (que uno con obstáculos simples como pensaba inicialmente), podría hacer la misma lógica anterior, pero verificando todos los puntos en el mapa (a diferencia de los puntos en el borde solamente). Esto debería estar en el orden de O(4n2 ) , que aún es mejor que F-W y Dijkstra.

Nota: El llenado de inundaciones es más adecuado para este problema , ya que todos los vértices están conectados directamente a través de solo 4 bordes. Un primer recorrido amplio del mapa puede arrojar resultados relativamente rápidos (solo en O (n) ). Supongo que cada punto puede verificarse en el relleno de inundación de cada uno de sus 4 vecinos, por lo tanto, el coeficiente en las fórmulas anteriores.

Actualización 2: Estoy agradecido por todos los comentarios positivos que he recibido con respecto a este algoritmo. Un agradecimiento especial a @Georg por su revisión .

P.S. Cualquier comentario o corrección es bienvenido.

Otros consejos

Siga la pregunta sobre Floyd-Warshall o el algoritmo simple de Hosam Aly :

Creé un programa de prueba que puede usar ambos métodos. Esos son los archivos:

En todos los casos de prueba, Floyd-Warshall fue mucho más lento, probablemente debido a la cantidad muy limitada de bordes que ayudan a este algoritmo a lograrlo.

Estos fueron los tiempos, cada vez que el campo era cuádruple y 3 de cada 10 campos eran un obstáculo. 

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

El tiempo de Hosam Aly parece ser cuadrático, por lo tanto, recomendaría usar ese algoritmo.  Además, el consumo de memoria de Floyd-Warshall es n 2 , claramente más de lo necesario. Si tienes alguna idea de por qué Floyd-Warshall es tan lento, deja un comentario o edita esta publicación.

PD: no he escrito C o C ++ en mucho tiempo, espero no haber cometido demasiados errores.

Eliminé mi publicación original recomendando el algoritmo Floyd-Warshall. :(

gs hizo un punto de referencia realista y adivina qué, FW es sustancialmente más lento que el "llenado por inundación" de Hosam Aly algoritmo para tamaños de mapas típicos! Entonces, aunque F-W es un algoritmo genial y mucho más rápido que el de Dijkstra para gráficos densos, no puedo recomendarlo más para el problema del OP, que involucra gráficos muy dispersos (cada vértice tiene solo 4 bordes).

Para el registro:

  • Una implementación eficiente de El algoritmo de Dijkstra toma tiempo O (Elog V) para un gráfico con bordes E y vértices V.
  • Hosam Aly '' relleno de inundación '' es una amplía la primera búsqueda , que es O (V). Esto puede considerarse como un caso especial del algoritmo de Dijkstra en el que ningún vértice puede tener su estimación de distancia revisada.
  • El el algoritmo Floyd-Warshall toma O (V ^ 3 ) tiempo, es muy fácil de codificar, y sigue siendo el más rápido para gráficos densos (aquellos gráficos en los que los vértices están típicamente conectados a muchos otros vértices). Pero no es la opción correcta para la tarea del OP, que implica gráficos muy escasos.

Parece que lo que quiere son los puntos finales separados por el diámetro del gráfico . Una aproximación bastante buena y fácil de calcular es elegir un punto aleatorio, encontrar el punto más alejado de ese punto y luego encontrar el punto más alejado de allí. Estos dos últimos puntos deben estar cerca de la máxima separación.

Para un laberinto rectangular, esto significa que dos rellenos de inundación deberían proporcionarle un buen par de puntos de inicio y finalización.

Raimund Seidel ofrece un método simple que utiliza la multiplicación de matrices para calcular la matriz de distancia de todos los pares en un gráfico no ponderado y no dirigido (que es exactamente lo que desea) en la primera sección de su artículo Sobre el problema de todos los pares de la ruta más corta en gráficos no ponderados no dirigidos  [pdf] .

La entrada es la matriz de adyacencia y la salida es la matriz de distancia de trayecto más corto de todos los pares. El tiempo de ejecución es O (M (n) * log (n)) para n puntos donde M (n) es el tiempo de ejecución de su algoritmo de multiplicación de matriz.

El documento también proporciona el método para calcular las rutas reales (en el mismo tiempo de ejecución) si lo necesita también.

El algoritmo de Seidel es genial porque el tiempo de ejecución es independiente del número de bordes, pero en realidad no nos importa aquí porque nuestro gráfico es escaso. Sin embargo, esta puede ser una buena opción (a pesar del tiempo de ejecución un poco peor que n ^ 2) si desea la matriz de distancia de todos los pares, y esto también podría ser más fácil de implementar y depurar que el relleno en un laberinto.

Aquí está el pseudocódigo: 

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

Para obtener el par de puntos con la mayor distancia simplemente devolvemos argmax_ij (d_ij)

Terminó una maqueta de Python de la solución dijkstra al problema. El código se alargó un poco, así que lo publiqué en otro lugar: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

En el tamaño que configuré, toma alrededor de 1.5 segundos ejecutar el algoritmo para un nodo. Ejecutarlo para cada nodo lleva unos minutos.

Sin embargo, no parece funcionar, siempre muestra la esquina superior izquierda y derecha como el camino más largo; 58 azulejos. Lo cual, por supuesto, es cierto, cuando no tienes obstáculos. Pero incluso agregando un par de aleatoriamente colocados, el programa todavía encuentra que ese es el más largo. Quizás todavía sea cierto, difícil de probar sin formas más avanzadas.

Pero tal vez al menos pueda mostrar mi ambición.

Ok, " algoritmo de Hosam " es una primera búsqueda amplia con una preselección en los nodos. El algoritmo de Dijkstra NO debe aplicarse aquí, porque sus bordes no tienen pesos.

La diferencia es crucial, porque si los pesos de los bordes varían, debe mantener abiertas muchas opciones (rutas alternativas) y verificarlas con cada paso. Esto hace que el algoritmo sea más complejo. Con la primera búsqueda de amplitud, simplemente explora todos los bordes una vez de una manera que garantiza que encuentre la ruta más corta a cada nodo. es decir, explorando los bordes en el orden en que los encuentra.

Entonces, básicamente, la diferencia es que Dijkstra tiene que 'retroceder' y mirar los bordes que ha explorado antes para asegurarse de que está siguiendo la ruta más corta, mientras que la primera búsqueda amplia siempre sabe que está siguiendo la ruta más corta.

Además, en un laberinto no se garantiza que los puntos en el borde exterior formen parte de la ruta más larga. Por ejemplo, si tiene un laberinto en forma de espiral gigante, pero con el extremo exterior volviendo a la mitad, podría tener dos puntos, uno en el corazón de la espiral y el otro en el extremo de la espiral, ambos en el medio!

Entonces, una buena manera de hacer esto es usar una primera búsqueda amplia de cada punto, pero eliminar el punto de partida después de una búsqueda (ya conoce todas las rutas hacia y desde él). La complejidad de la amplitud primero es O (n), donde n = | V | + | E |. Hacemos esto una vez para cada nodo en V, por lo que se convierte en O (n ^ 2).

Su descripción me parece un problema de enrutamiento de laberinto . Consulte el Algoritmo de Lee . Los libros sobre problemas de ubicación y ruta en el diseño de VLSI pueden ayudarlo: Algoritmos de Sherwani " VLSI Physical Design Automation " es bueno, y puede encontrar Automatización de diseño físico VLSI por Sait y Youssef útil (y más barato en su versión de Google ...)

Si sus objetos (puntos) no se mueven con frecuencia, puede realizar dicho cálculo en un tiempo mucho más corto que O (n ^ 3).

Todo lo que necesita es dividir el espacio en grandes cuadrículas y calcular previamente la distancia entre cuadrículas. Luego, seleccionar pares de puntos que ocupen las cuadrículas más distantes es una simple búsqueda en la tabla. En el caso promedio, deberá verificar por pares solo un pequeño conjunto de objetos.

Esta solución funciona si las métricas de distancia son continuas. Por lo tanto, si, por ejemplo, hay muchas barreras en el mapa (como en los laberintos), este método podría fallar.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top