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

problema del par de puntos más cercanos

Question

Estoy buscando un algoritmo para ser utilizado en un juego de carreras que estoy haciendo. El mapa / nivel / pista se genera de forma aleatoria, así que necesito encontrar dos ubicaciones, inicio y objetivo, que hagan uso de la mayor parte del mapa.

• El algoritmo es para 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 pueden ser bloqueados o no bloqueados, solo se pueden atravesar puntos no bloqueados

En cuanto al cálculo de la distancia, no debería ser el "camino de los pájaros" por falta de una palabra mejor. La ruta entre A y B debería ser más larga si hay una pared (u otra área de bloqueo) entre ellos.

No estoy seguro de dónde empezar, los comentarios son bienvenidos y las soluciones propuestas son preferidas en el pseudo código.

Editar: Derecha. Después de mirar el código de gs, le di otra oportunidad. En lugar de Python, esta vez lo escribí en C ++. Pero aún así, incluso después de leer el algoritmo de Dijkstras , el relleno de inundación y la solución de Hosam Alys , no veo ninguna diferencia crucial. Mi código aún funciona, pero no tan rápido como parece que está haciendo funcionar el suyo. La fuente completa está en pastie . Las únicas líneas interesantes (supongo) es la variante de 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 de Hosam Alys, ¿la única diferencia es que escanea desde los bordes en lugar de cada nodo?
• En Dijkstras, realiza un seguimiento y sobrescribe la distancia recorrida, pero no en inundaciones, ¿pero eso es todo?

Answer 1

Parece que lo que quieres son los puntos finales separados por el diámetro del gráfico . Una aproximación bastante buena y fácil de calcular es escoger un punto aleatorio, encontrar el punto más alejado de eso, y luego encontrar el punto más alejado desde allí. Estos dos últimos puntos deberían 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 final.

Answer 2

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 precalcular la distancia entre las cuadrículas. Luego, la selección de pares de puntos que ocupen las cuadrículas más distantes es una cuestión de simple búsqueda de tablas. En el caso promedio, deberás verificar 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.

Answer 3

Terminó una maqueta de pitón de la solución dijkstra al problema. El código se hizo un poco largo, 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 configuro, se tarda aproximadamente 1,5 segundos en ejecutar el algoritmo para un nodo. Ejecutarlo para cada nodo toma unos minutos.

Sin embargo, parece que no funciona, siempre muestra la esquina superior e inferior como el camino más largo; 58 fichas Lo cual por supuesto es cierto, cuando no tienes obstáculos. Pero incluso agregando un par de elementos colocados al azar, el programa aún encuentra uno más largo. Tal vez sigue siendo cierto, difícil de probar sin formas más avanzadas.

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

Answer 4

Tu descripción me suena como un problema de enrutamiento de laberinto . Mira el algoritmo de Lee . Los libros sobre los problemas de lugar y ruta en el diseño de VLSI pueden ayudarlo: "Algoritmos para la automatización de diseño físico VLSI" de Sherwani es bueno, y es posible que la Automatización de diseño físico VLSI de Sait y Youssef sea útil (y más económica en su versión de Google ... )

Answer 5

Raimund Seidel proporciona un método simple usando la multiplicación de matrices para calcular la matriz de distancias de todos los pares en un gráfico no ponderado, no dirigido (que es exactamente lo que desea) en la primera sección de su documento Sobre el problema de todos los pares de ruta más corta en Unweighted Gráficos sin dirección [pdf] .

La entrada es la matriz de adyacencia y la salida es la matriz de distancia de trayectos más cortos 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 porque nuestro gráfico es escaso. Sin embargo, esta puede ser una buena opción (a pesar del tiempo de ejecución ligeramente 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 un derrame 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)

Answer 6

De acuerdo, el "algoritmo de Hosam" es una primera búsqueda de amplitud 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 el peso de los bordes varía, necesita mantener abiertas muchas opciones (rutas alternativas) y verificarlas en cada paso. Esto hace que el algoritmo sea más complejo. Con la primera búsqueda de ancho, simplemente explora todos los bordes de una manera que garantice que encuentre la ruta más corta a cada nodo. es decir, explorando los bordes en el orden en que los encuentra.

Básicamente, la diferencia radica en que Dijkstra tiene que "retroceder" y mirar los bordes que exploró antes para asegurarse de que sigue la ruta más corta, mientras que la primera búsqueda de amplitud 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 sean parte de la ruta más larga. Por ejemplo, si tienes un laberinto en forma de espiral gigante, pero con el extremo externo volviendo al centro, podrías tener dos puntos uno en el corazón de la espiral y el otro al final de la espiral, ambos ¡en el medio!

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

Answer 7

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

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 serí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 fronterizos 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 ² ) . (Si el mapa es cuadrado, el orden sería O(16n ^1.5 ) .)

Actualización: según los comentarios, dado que el mapa es más un laberinto (que uno con obstáculos simples como estaba pensando inicialmente), podría hacer la misma lógica anterior, pero verificando todos los puntos en el mapa (en oposición a los puntos en el borde solo). Esto debería estar en orden de O(4n ² ) , que es mejor que tanto FW como Dijkstra.

Nota: El relleno de inundación 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 ancho del mapa puede arrojar resultados relativamente rápido (en solo 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 .

PD: cualquier comentario o corrección son bienvenidos.

Answer 8

Sigue 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:

• creador de laberinto
• encontrar la distancia más larga

En todos los casos de prueba, Floyd-Warshall fue por una gran magnitud más lenta, probablemente debido a la cantidad muy limitada de bordes que ayudan a este algoritmo a lograr esto.

Estos eran los tiempos, cada vez que el campo era cuadruplete 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 ² , claramente más de lo necesario. Si tienes alguna idea de por qué Floyd-Warshall es tan lenta, por favor deja un comentario o edita esta publicación.

PD: No escribí C o C ++ en mucho tiempo, espero no haber cometido demasiados errores.

Answer 9

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

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

Para el registro:

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