J'essaie d'implémenter l'algorithme de Dijkstra afin de trouver le chemin le plus court entre 2 points d'une grille (x, y), mais le problème est que je ne peux que monter, descendre, droite et gauche.
J'ai une ArrayList contenant les x et les y deles points que j’ai besoin de transmettre et une autre liste ArrayList des points constituant des obstacles sur la grille, j’essaie d’écrire une fonction qui renvoie une liste ArrayList du mouvement nécessaire pour terminer tout le chemin.
Dans l'exemple: 1,1,1,2,3,4,1 .. 1 étant à droite 2 étant à gauche et 3 étant en haut et enfin 4 en bas.
Pouvez-vous s'il vous plaît me donner quelques conseils et / ou exemples.
Réponses:
2 pour la réponse № 1Tout d’abord, sachez que l’algorithme de Dijkstra s’applique traditionnellement aux graphes pondérés. Il peut toujours fonctionner avec des arêtes unitaires (tout le poids 1) mais ce n’est peut-être pas la solution la plus efficace.
De toute façon, quel que soit l'algorithme que vous utilisez, vousbesoin de traiter votre grille comme un graphique. Pour ce faire, créez un ensemble d’arêtes. S'il n'y a pas de restrictions au-delà de "pas de diagonales", vos arêtes seront la connexion entre chaque point et ses voisins au-dessus, au-dessous et à côté. Vous pouvez ensuite utiliser le graphique en effectuant une itération sur les arêtes et les points du graphique.