Comment calculer le chemin le plus court entre deux points d'une grille

Utiliser le Une Étoile (*) de l'algorithme.

vous pouvez être désinformé. Il existe différentes variantes de l'algorithme de Dijkstra. On calcule les chemins Les plus courts de chaque point à chaque autre point (comme Floyd).

cependant, L'algorithme typique de Dijkstra est basé sur une file d'attente prioritaire et calcule seulement votre chemin le plus court requis. Il construit plusieurs chemins pendant son exécution, mais ce sont tous des chemins partiels de A vers d'autres noeuds qui pourraient être sur le chemin de la solution finale.

ainsi, vous pouvez facilement interpréter votre grille comme un graphe (les restrictions comme les diagonales peuvent alors être prises en compte en conséquence) et exécuter une recherche Dijkstra pour le chemin le plus court de A à B sur cela. C'est juste une question de modeler ton problème, pas que tu aies besoin d'un algorithme sophistiqué.

si votre mouvement est suffisamment restrictif (par exemple, vous ne pouvez vous déplacer qu'à droite, ou vers le haut, ou en diagonale vers le haut et à droite), alors vous pouvez exploiter ses sous-problèmes de chevauchement et sa sous-structure sous-optimale nature et utiliser programmation dynamique .

ce que je ne comprends pas c'est, si vous voulez le chemin le plus court entre A et B, ne devez-vous pas toujours regarder A à C et a à d si C et d pointent vers B? Votre chemin le plus court pourrait très bien être A-C-B ou A-D-B. Vous avez juste besoin de jeter les noeuds non connectés. Dans l'un de mes projets, j'ai pris les points A et B, j'ai vérifié quels autres points étaient connectés, et ceux qui n'étaient pas ont été supprimés de l'ensemble du graphique. Puis je me rendis à l'aide de l'algorithme de Dijkstra.

Voici une implémentation python du chemin le plus court dans une matrice de (0,0) à (0,m-1) en utilisant BFS. Vous pouvez le modifier pour ajuster les points 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 matrice d'entrée doit être composée de 0 et de 1. 0 est pour mouvement possible.
• n est le nombre de lignes .
• m est le nombre de colonnes.
• arr est la matrice donnée.
• x est la matrice de distance à partir de (0,0).
• vis est un dictionnaire donnant un booléen si le nœud est visité.
La sortie
• de -1 montre qu'il n'y a pas de chemin possible.

votre grille forme un graphique (ou du moins peut être vue comme un graphique). L'élimination de certaines directions du mouvement indique que c'est un graphe dirigé. Si vous ne pouvez pas passer d'un nœud à un autre, c'est un avantage qui n'est pas présente dans le graphe.

une fois que vous avez encodé votre grille en forme de graphe, il s'agit simplement de choisir parmi les algorithmes de graphe bien connus (dont vous êtes apparemment déjà au courant) pour la traverser pour le type de résultat que vous voulez (par ex. le chemin le plus court).

Edit: j'ai regardé la réponse que vous avez postée, mais je ne suis pas sûr de ce que ce code est supposé être/faire. Juste pour exemple, il a: if(y>=0) max(abs(x),y); . Cela ne semble pas (du moins pour moi) avoir beaucoup de sens -- le résultat du max est tout simplement jeté. Pour accomplir quelque chose d'utile, il doit être retourné ou affectés ou quelque chose de cet ordre. Comme il se présente, le mieux que vous pouvez espérer est que le compilateur le repère comme code mort, et ne génère pas rien pour elle.

à mon avis, le code ne fonctionne pas vraiment comme prévu, et s'il fait quelque chose d'utile, c'est plus par accident que par conception. Il faudrait beaucoup de temps et d'efforts pour être sûr que vous avez réglé des problèmes comme celui-ci au point que vous étiez vraiment sûr de ce qu'il a fait, et encore plus difficile de deviner ce qui était vraiment prévu.

utilisez un algorithme* pour trouver le chemin entre deux points dans une grille 2D. http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html