Cómo calcular el camino más corto entre dos puntos en una cuadrícula

Utilice el algoritmo A Star (A*).

Usted puede estar desinformado. Existen diferentes variantes del algoritmo de Dijkstra. Uno calcula los caminos más cortos 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 la ruta más corta requerida. Construye varias rutas durante su ejecución, pero todas son rutas parciales desde A a otros nodos que podrían estar en la ruta final de la solución.

Por lo tanto, puede interpretar fácilmente su cuadrícula como un gráfico (las restricciones como diagonales se pueden tener en cuenta en consecuencia) y ejecute una búsqueda Dijkstra para el camino más corto de A a B en eso. Es solo una cuestión de modelar tu problema, no es que necesites algún algoritmo sofisticado.

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

Lo que no entiendo es, si quieres el camino más corto entre A y B, ¿no necesitas mirar A A a C y a a D si C y D apuntan a B? Tu camino más corto podría ser A-C-B o A-D-B. Solo necesitas lanzar nodos desconectados. En uno de mis proyectos, tomé los puntos A y B, comprobé qué otros puntos estaban conectados, y los que no estaban se eliminaron de todo el gráfico. Luego procedí con el uso del algoritmo de Dijkstra.

Aquí está una implementación de python de shortest path en una matriz de (0,0) a (0,m-1) usando BFS. Puede cambiarlo para que se ajuste a 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)

• la matriz de entrada debe consistir en 0's y 1's. 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 desde (0,0).
• vis es un diccionario que da un booleano si el nodo es visitado.
• la salida de -1 muestra que hay no es posible tal camino.

Su cuadrícula forma un gráfico (o al menos se puede ver como un gráfico). Eliminar algunas direcciones de movimiento indica que es un gráfico dirigido. Si no puede moverse de un nodo a otro en absoluto, esa es una arista 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 bien conocidos (de los que aparentemente ya conoce) para recorrerla para el tipo de resultado que desea (por ejemplo, más corto camino).

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

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

Utilice un algoritmo* para encontrar la ruta entre dos puntos en una cuadrícula 2D. http://theory.stanford.edu / ~amitp/GameProgramming/ImplementationNotes.html