Je crée un algorithme pour trouver le chemin le plus court entre deux points dans un labyrinthe, mais ma solution actuelle est trop lente.
C'est ce que j'ai fait:
Helper Cours: < / strong> J'ai ajouté un troisième paramètre paramètre Comment pourrais-je améliorer la performance de cet algorithme? Mindistance afin que je puisse comparer avec les calculs des chemins précédents à différents points mais cela ne devrait pas être pertinent ici.
3 Réponses :
Si vous demandez à propos de Chemin de trouver des alghortims. Dijkstra est un moyen d'aller. Recherchez cette grande bibliothèque open source: JavaScript-Alghoritms . Essentiellement ce que vous voulez faire, c'est créer une représentation pondérée graphique. (Vous devez connaître les bases de la "théorie des graphes".) Votre poids entre les points sera dans ce cas. Distance euclidienne entre les points. Et quel mot clé vous devriez utiliser pour chaque point. (J'ai utilisé Mac Adresse dans mon scénario). Dans votre cas, il devrait s'agir de l'identifiant unique de chaque point.
Vous voudrez peut-être lire sur Algorithme de Dijkstra . Il semble que ce que vous avez mis en œuvre est un peu similaire mais plus compliqué. Vous n'avez pas besoin de garder une trace de tout le chemin à chaque point, juste la distance minimale à chaque position. Vous obtenez le chemin le plus court simplement en allant à la cellule voisine avec la valeur de distance la plus basse.
Edit: On dirait que quelqu'un m'a battu!
Merci pour le commentaire. J'essaie de mettre en œuvre cette approche, mais j'ai besoin de garder une trace de tous les chemins, car au cas où la distance de chemin la plus courte est par exemple 10 et que cela peut être atteint de différentes manières, je dois choisir l'un des critères suivants. "ordre de lecture" de haut à Botton, de gauche à droite et cela échoue lorsque, par exemple, la cible est sur le côté gauche de l'origine ou vers le haut. Le "recul" ne fonctionne pas comme prévu.
Merci pour les recommandations.
J'ai pris fin avec cette solution:
Vous pourriez être plus heureux de poster votre question sur codereview.stackexchange.com