Comment calculer le plus court chemin entre deux points dans une grille

Je sais que de nombreux algorithmes sont disponibles pour calculer le plus court chemin entre deux points dans un graphique ou d'une grille, comme en largeur d'abord, toutes les paires (Floyd), Dijkstra est.

Cependant, comme je l'ai remarqué, tous ces algorithmes de calcul de tous les chemins dans ce graphe ou de la grille, et pas seulement ceux entre les deux points nous intéressent.

MA QUESTION EST:
si j'ai une grille, c'est à dire un tableau à deux dimensions, et je suis intéressé dans le calcul du plus court chemin entre deux points, par exemple P1 et P2, et si il y a des restrictions sur la façon dont je peux me déplacer sur la grille (par exemple, seulement en diagonale, ou seulement en diagonale et vers le haut, etc.),
quel algorithme permet de calculer cela?

Veuillez remarquer que si vous avez une réponse, je voudrais vous poster le nom de l'algorithme plutôt que l'algorithme lui-même (bien sûr, encore mieux si vous aussi poster l'algorithme); par exemple, si c'est l'algorithme de Dijkstra, ou Floyd, ou quoi que ce soit.

S'il vous plaît aidez-moi, j'ai été de penser à ce sujet pendant des mois!

okey les gars j'ai trouvé cet algorithme sur TOPCODER.COM
ici, dans la grille, vous pouvez déplacer uniquement (en diagonale et vers le haut)
mais je ne peux pas comprendre ce que l'algorithme est-ce par quelque moyen que pouvait-on le savoir?

#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);
}
};
  • Voulez-vous la longueur du chemin le plus court ou le chemin d'accès réel? Est la grille la garantie d'être dégagée de l'uniforme et de "coût" pour traverser?
  • je veux que la longueur du chemin le plus court, la grille est complètement uniforme , penser que c'est un plan cartésien dont les coordiantes sont des entiers
  • Dijkstra ne veut pas nécessairement calculer les plus courts chemins à tous les autres points sur le graphique. Il doit calculer les plus courts chemins pour tout point à ce qui a un chemin plus court que votre objectif (et il peut aussi trouver le chemin d'accès à des points qui ont la même longueur du plus court chemin que votre but). Alors il peut aller d'un point au-delà de ces points, mais cela devrait être tout.
InformationsquelleAutor Alan_AI | 2010-02-22
  1. 38

    Lee algorithme: http://en.wikipedia.org/wiki/Lee_algorithm

    Il s'agit essentiellement d'un BF de recherche, voici un exemple: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

    À mettre efficacement en œuvre, de vérifier ma réponse ici: Changement de Diffuseur-Algorithme pour obtenir de Voronoi Territoire de deux points de données? - quand je dis que marque, vous le marquez avec le numéro sur le poste qui vous est venu à partir de + 1.

    Par exemple, si vous avez cette grille, où a * = obstacle et vous pouvez déplacer vers le haut, le bas, la gauche et la droite, et vous commencez à partir de S et doit aller à D, 0 = position libre:

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

    Vous mettre S dans votre file d'attente, ensuite "élargir" c':

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

    Puis développez l'ensemble de ses voisins:

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

    Et tous les voisins, les voisins:

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

    Et ainsi de suite, à la fin vous obtiendrez:

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

    De sorte que la distance de S à D est 9. Le temps d'exécution est O(NM), où N = nombre de lignes et M = nombre de colonnes. Je pense que c'est la méthode la plus simple de l'algorithme à mettre en œuvre sur les grilles, et c'est aussi très efficace dans la pratique. Il devrait être plus rapide qu'une classique dijkstra, bien que dijkstra peut gagner, si vous la mettre en œuvre à l'aide de segments.

    • veuillez vérifier l'algorithme que je l'ai posté une réponse
    • Ok, c'est une bien meilleure explication de Ala question. Maintenant, je comprends exactement ce qu'il demandait, mais je n'aurais pas connu cette réponse. Intéressant!
    • Dans le passé j'ai utilisé le Lee algo pour les PCB; nous avons fait les cellules dans le sens du courant moins cher que ceux sur le côté: ainsi nous éviter les "irréguliers" les lignes en faveur de droites.
    • Oh, et "only diagonally" serait simple à mettre en œuvre. Etant donné que les "étincelles" grandir à partir de tous les/les deux points de terminaison "only diagonally and upwards" vous obligeraient abord classer quel point est "supérieure" et d'avoir son étincelle progrès, vers le bas.
    • "Puis développez l'ensemble de ses voisins:" que voulez-vous dire par là? pour ajouter tous les non visités voisins de la file d'attente?
    • oui, exactement.
    • Beaucoup mieux que l'explication wikipedia. Merci!

    InformationsquelleAutor IVlad
  3. 5

    Vous avez peut-être disinformed. Il existe différentes variantes de l'algorithme de Dijkstra. On calcule les plus courts chemins à partir de chaque point à tous les autres points (comme Floyd).

    Cependant, typique de Dijkstra algorithme est basé sur une file d'attente de priorité et seulement calcule votre chemin le plus court. Il fait construire plusieurs chemins au cours de son exécution, mais ceux-ci sont tous des chemins partiels à partir d'Un pour certains autres nœuds qui pourraient être sur la solution finale chemin.

    Donc, vous pouvez facilement interpréter votre grille comme un graphe (les restrictions comme les diagonales peuvent ensuite être pris en compte en conséquence) et de lancer un Dijkstra recherche du plus court chemin de A à B sur que. C'est vraiment juste une question de modélisation votre problème, pas que vous avez besoin d'un peu de fantaisie algorithme.

    • +1 pour s'assurer que l'on pense de leur problème correctement. Je suis tombé sur cette question, pensant que j'avais besoin d'un plus court chemin algorithme, mais cela m'a aidé à comprendre que, même s'il aurait travaillé pour mon problème finalement, ce n'était pas ce que j'essaye vraiment de le résoudre.
    InformationsquelleAutor Frank
  4. 2

    Si votre mouvement est assez restrictive (par exemple, vous ne pouvez vous déplacer vers la droite, ou vers le haut, ou à la diagonale en haut et à droite), alors vous pouvez exploiter son chevauchement des sous-problèmes et sous-optimal sous-structure de la nature et de l'utilisation la programmation dynamique.

    • Cet algorithme est appelé DAG-chemin le plus court, et comme leur nom l'indique, ne fonctionne que sur les dirigés acycliques graphiques.
    • C'est pourquoi @polygenelubricants dit "restrictive assez". Dans les exemples qui polygenelubricants mentionne, qu'on ait affaire à réalisé graphes acycliques (Dag). Donc, il est toujours très utile de commentaires relatifs à la question à portée de main.
    InformationsquelleAutor polygenelubricants
  5. 1

    Ce que je n'arrive pas à comprendre est que si vous voulez le chemin le plus court entre A et B, vous n'avez pas toujours besoin de regarder à C et à D si C et D, point B? Votre chemin le plus court pourrait très bien être A-C-B ou A-D-B. Vous avez juste besoin de jeter sans lien nœuds. Dans un de mes projets, j'ai pris les points A et B, vérifié pour voir ce que d'autres points ont été connectés, et ceux qui n'ont pas été supprimés de l'ensemble du graphique. Puis je me rendis à l'aide de l'algorithme de Dijkstra.

    • je n'ai pas de calculer le chemin, c'est à dire l'algorithme ne sais pas comment aller de A à B, il ne connais que le plus court chemin entre eux depenting sur il coordonne, p.s. ce n'est pas un graphique c'est une grille dans laquelle chaque nœud a pour coordonnées
    • Pour info: Si vous voulez juste le plus court chemin de A à B à l'aide de Dijkstra, vous n'avez pas besoin de vérifier la connectivité et de supprimer inaccessible éléments. En fait, cela aggrave votre exécution de la complexité, comme Dijkstra sera implicitement décider de la connectivité entre A et B et peut-être seulement besoin de regarder un petit sous-graphe pour que, alors que vous regardez le graphique entier lors de la suppression d'éléments.
    • Je n'ai jamais fait aucune analyse comparative, mais sur le plan conceptuel, il me semblait que si j'avais 100 nœuds dans le graphe, Dijkstra est de rendre visite à chacun et puis le poids du coût de la voie de nœud à nœud. Mais si je peux l'enlever 95 des 100 nœuds à l'avant, pourquoi n'aurais-je pas envie de faire cela, au lieu de laisser Dijkstra, de le traiter comme on traite le graphique?
    • désolé, je me suis pris dans Dijkstra et a échoué de se rappeler que vous êtes à l'aide d'une grille. 🙂
    • alors les gars, vérifier l'algorithme que j'ai posté une réponse
    InformationsquelleAutor Dave
  6. 1

    Voici un python de la mise en œuvre d'un plus court chemin dans une matrice de (0,0) à (0,m-1) à l'aide de BFS. Vous pouvez le modifier pour l'adapter variable de points.

    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)
    • matrice d'entrée devrait être composé de 0 et de 1. 0 est de 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 de (0, 0).
    • vis est un dictionnaire donnant un booléen si le nœud est visité.
    • sortie de -1 indique qu'il n'existe pas de chemin possible.
    InformationsquelleAutor Apurv
  7. 0

    Votre grille forme un graphe (ou au moins peut être vu comme un graphe). L'élimination de certaines directions de mouvement indique que c'est un graphe orienté. 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 codé votre grille en forme de graphe, c'est une simple question de choisir entre le bien-connu algorithmes de graphes (dont vous êtes apparemment déjà au courant) de la traverser pour le type de résultat que vous souhaitez (par exemple, le chemin le plus court).

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

    Ma conjecture est que le code ne fonctionne pas vraiment tout à fait comme prévu, et si elle ne fait rien d'utile, c'est plus par accident que la conception. Il faudrait une quantité considérable de temps et d'efforts pour être sûr que vous avez trié ce type de problèmes, au point que vous vous êtes vraiment sûr de ce qu'il a fait, et encore plus difficile à deviner ce qui était vraiment destiné.

    • veuillez vérifier l'algorithme de poster une réponse
    • vous avez raison sur la ligne qui ne fait rien, je vous redit mon poste et de l'effacer, mais j'ai essayé d'écrire une fonction main() pour tester et j'ai été étonné qu'elle pourrait résoudre tous les intrants je suis entré y compris les valeurs du bord.. je suis étonné
    • Je ne suis pas sûr de savoir comment vous êtes tester -- basé sur le code en lui-même, il n'est pas clair du tout ce format d'entrée qu'il attend. Le résultat semble être à seulement une longueur du chemin, n'ayant aucune information sur ce chemin, il en fait calculé. En tout cas, une petite quantité de code à produire des résultats corrects n'est pas particulièrement étonnant, une recherche exhaustive est souvent assez simple, juste assez lente pour de grands graphes.
    • oui il ne calcule la longueur du chemin, c'est de quoi je parle, je ne suis pas intéressé par le chemin lui-même... j'ai vraiment testé, et beaucoup de participants sur topcoder posté algorithmes semblables à ceci, que ce qui m'a enthousiasmée
    InformationsquelleAutor Jerry Coffin
  8. -1

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

    • Une telle suggestion a déjà été donné et reçu 5 upvotes.
    InformationsquelleAutor badal ahuja