algorithm - ubicar - punto medio de un segmento

Cómo calcular el camino más corto entre dos puntos en una grilla

Question

Sé que hay muchos algoritmos disponibles para calcular la ruta más corta entre dos puntos en un gráfico o una grilla, como la anchura primero, todos los pares (Floyd), Dijkstra.

Sin embargo, como noté, todos estos algoritmos computan todas las rutas en ese gráfico o cuadrícula, no solo aquellas entre los dos puntos que nos interesan.

MI PREGUNTA ES: si tengo una grilla, es decir, una matriz bidimensional, y estoy interesado en calcular la ruta más corta entre dos puntos, digamos P1 y P2, y si hay restricciones en la forma en que puedo moverme en la grilla ( por ejemplo, solo en diagonal, o solo en diagonal y hacia arriba, etc.), ¿qué algoritmo puede calcular esto?

Tenga en cuenta que si tiene una respuesta, me gustaría que escriba el nombre del algoritmo en lugar del algoritmo en sí (por supuesto, incluso mejor si también publica el algoritmo); por ejemplo, si es el algoritmo de Dijkstra, o el de Floyd, o lo que sea.

Por favor, ayúdenme, ¡he estado pensando en esto por meses!

okey chicos, encontré este algoritmo en TOPCODER.COM aquí en la grilla solo se puede mover (en diagonal y arriba) pero no puedo entender qué algoritmo es esto de ninguna manera, ¿podría saber alguien?

#include<iostream>
#include <cmath>
using namespace std;
inline int Calc(int x,int y)
{
if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
}
class SliverDistance
{
public:
int minSteps(int x1,int y1, int x2, int y2)
{
int ret=0;
if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
return ret+Calc(x2-x1,y2-y1);
}
};

Answer 1

Algoritmo de Lee: http://en.wikipedia.org/wiki/Lee_algorithm

Básicamente es una búsqueda de BF, aquí hay un ejemplo: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

Para implementarlo de manera efectiva, verifique mi respuesta aquí: ¿ Cambiar el FloodFill-Algorithm para obtener el territorio de Voronoi para dos puntos de datos? - cuando digo marcar, lo marca con el número en la posición de la que vino de + 1.

Por ejemplo, si tiene esta cuadrícula, donde a * = obstáculo y puede moverse hacia arriba, abajo, izquierda y derecha, y comienza desde S y debe ir a D, y 0 = posición libre:

S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

Pones S en tu cola y luego la "expandes":

S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

Luego expande todos sus vecinos:

S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

Y todos los vecinos de esos vecinos:

S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D

Y así sucesivamente, al final obtendrás:

S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9

Entonces la distancia de S a D es 9. El tiempo de ejecución es O (NM), donde N = número de líneas y M = número de columnas. Creo que este es el algoritmo más fácil de implementar en las grillas, y también es muy eficiente en la práctica. Debería ser más rápido que un dijkstra clásico, aunque dijkstra podría ganar si lo implementas usando montones.

Answer 2

Aquí hay una implementación de Python de la ruta más corta en una matriz de (0,0) a (0, m-1) usando BFS. Puede cambiarlo para ajustar puntos variables.

n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
curr=q[0]
rem=q.pop(0)
vis[curr]=True
r=curr[0]
c=curr[1]
if r-1>=0 and arr[r-1][c]==0:
if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
q.append((r-1,c))
x[r-1][c]=x[r][c]+1
if r+1<n and arr[r+1][c]==0:
if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
q.append((r+1,c))
x[r+1][c]=x[r][c]+1
if c-1>=0 and arr[r][c-1]==0:
if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
q.append((r,c-1))
x[r][c-1]=x[r][c]+1
if c+1<m and arr[r][c+1]==0:
if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
q.append((r,c+1))
x[r][c+1]=x[r][c]+1
#for i in x:
#print(i)
ans=x[0][m-1]
if ans==-1:
print(-1)
else:
print(ans)

• matriz de entrada debe constar de 0 y 1. 0 es para un posible movimiento.
• n es el número de filas.
• m es el número de columnas.
• arr es la matriz dada.
• x es la matriz de distancia de (0,0).
• vis es un diccionario que proporciona un valor booleano si se visita el nodo.
• La salida de -1 muestra que no existe tal ruta posible.

Answer 3

Lo que no entiendo es, si quieres el camino más corto entre A y B, ¿no necesitas mirar A hasta C y A a D si C y D apuntan a B? Su camino más corto podría ser ACB o ADB. Solo necesita tirar los nodos desconectados. En uno de mis proyectos, tomé los puntos A y B, revisé para ver qué otros puntos estaban conectados, y los que no fueron borrados de todo el gráfico. Luego procedí con el uso del algoritmo de Dijkstra.

Answer 4

Si su movimiento es lo suficientemente restrictivo (por ejemplo, solo puede moverse hacia la derecha, hacia arriba o hacia la diagonal hacia arriba y hacia la derecha), puede explotar sus subproblemas superpuestos y la naturaleza subóptima de la subestructura y utilizar la programación dinámica .

Answer 5

Su cuadrícula forma un gráfico (o al menos puede verse como un gráfico). La eliminación de algunas direcciones de movimiento indica que se trata de un gráfico dirigido. Si no puede moverse de un nodo a otro, ese es un borde que no está presente en el gráfico.

Una vez que haya codificado su cuadrícula en forma de gráfico, es una simple cuestión de seleccionar entre los algoritmos de gráficos conocidos (de los cuales aparentemente ya está enterado) para recorrer el tipo de resultado que desea (por ejemplo, el camino más corto).

Editar: miré la respuesta que publicaste, pero no estoy seguro de qué se supone que es ese código. Solo por ejemplo, tiene: if(y>=0) max(abs(x),y); . Esto no parece (al menos para mí) tener mucho sentido; el resultado del max simplemente se descarta. Para lograr algo útil, necesita ser devuelto o asignado o algo en ese orden. Tal como está, lo mejor que puedes esperar es que el compilador lo vea como código inactivo y no genere nada para él.

Supongo que el código realmente no funciona como se esperaba, y si hace algo útil, es más por accidente que por diseño. Tomaría una buena cantidad de tiempo y esfuerzo para asegurarse de que ha resuelto los problemas hasta el punto en que estaba realmente seguro de lo que hizo, y aún más difícil de adivinar lo que realmente se pretendía.

Answer 6

Usted puede estar desinformado. Existen diferentes variantes del algoritmo de Dijkstra. Uno calcula las rutas más cortas de cada punto a cada otro punto (como el de Floyd).

Sin embargo, el algoritmo típico de Dijkstra se basa en una cola de prioridad y solo calcula su ruta más corta requerida. Sí construye varias rutas durante su ejecución, pero todas son rutas parciales desde A hasta algunos otros nodos que podrían estar en la ruta de la solución final.

Por lo tanto, puede interpretar fácilmente su cuadrícula como un gráfico (las restricciones como las diagonales se pueden tener en cuenta en consecuencia) y ejecutar una búsqueda de Dijkstra para la ruta más corta de A a B sobre eso. Realmente es solo una cuestión de modelar su problema, no es que necesite un algoritmo sofisticado.

Answer 7

Utilice el algoritmo A Star (A *) .

Answer 8

use un algoritmo A * para encontrar la ruta entre dos puntos en una grilla 2D. theory.stanford.edu/~amitp/GameProgramming/…