Follow

Bonjour à tous.
J'ai vraiment besoin de votre aide. J'ai un projet d'informatique à rendre pour mercredi. Le problème c'est que "ça marche pas" malgré mes efforts vains pour que cela fonctionne.
Le projet est une implémentation de l'algorithme de Dijkstra pour la recherche du plus court chemin dans un espace 2D encombré.
Mon code est en Java.
Vous pourrez le trouvez ici (framagit.org/Elijah-ru/dijkstr)
ça m'aiderait beaucoup. Merci d'avance enormément.

Le souci ne vient pas de l'algo en lui même que je pense avoir compris mais de l'implémentation qui est foireuse.

La première itération de Dijkstra fonctionne sans problème mais c'est quand je cherche à raffiner que les problèmes adviennent.

Bien sûr je ne vous demandrait pas si ce n'était pas important et si je n'avais pas essayé du plus dur que je pouvais. Cela fait maintenant une petite semaine je suis dessus presque tout le temps (dès que je n'ai pas court). J'ai recommencé plusieurs fois et je pense que je manque quelque chose.

@Elijah__ En lisant vite-fait comme ça, j'ai l'impression que ton implémentation n'est pas récursive. Je me trompe ? 🤔

@Elijah__ Ton implémentation m'a l'air pas mal compliquée. T'as essayé de regarder cette page : baeldung.com/java-dijkstra ?

@Elijah__ C'est normal de faire compliqué quand tu débutes. Et l'algo de Dikjstra n'est pas le plus simple du monde.

@Elijah__

Avant même de commencer à regarder le contenu src du fichier tar.gz devrait être directement dans git, versionner un tar.gz n'est pas pratique.

@Elijah__

Est-ce que le projet a déjà fonctionné sur un petit nombre d'obstacles ?
Pourquoi génère t'on des obstacles dans raffinement ?

@PhilippeLhardy
j'avais une fonction qui générait aléatoirement des obstacles que j'ai remplacé (j'ai commenté la première) par une autre avec des obstacles fixes.
Le programme marche pour ce qui est de la recherche du PCC. le souci est au niveau du raffinement (la deuxieme fois).
La condition d'aret du tant que (a savoir que le sommet d'arrivee soit contenu dans la liste renvoyée par PCC) n'est jamais remplie.

@Elijah__

J'ai un peu de mal à comprendre l'algorithme même dans le cas de base.
On créé aléatoirement une liste de sommets qui ne sont pas dans les obstacles et puis on construit un graphe qui relie ces points, le voisins sont ordonnés du haut vers bas donc de l'arrivée vers le départ dans un rayon donné.
si on trouve un chemin qui part de la fin et qui fini par l'arrivé alors c'est clui que l'on garde.

@Elijah__

Cependant ce graphe contient des points adjacents qui, s'il ne sont pas dans les obstacles peuvent constituer un segment qui coupe l'obstacle, et donc le résultat peut être inférieur au chemin minimum, le seul garde fou le rayon, dont si l'on souhaite utiliser cette solution on doit s'assurer qu'il est supérieur au plus gros obstacle.

@Elijah__

Le nombre d'itérations pour obtenir un chemin valide varie très fortement ( de 300 à 8000 ) pour le même ensemble d"obstacles initiaux. si l'on réduit le rayon alors il faut aussi augmenter le nombre de points sinon il y a un risque qu'il soit statistiquement très difficile d'obtenir une distributions de points assez proches.

@Elijah__

Etant donné que tout l'algoritheme se base sur du random, la preuve que l'algorithme fini est entièrement relative à la nature de l'aléa.

@PhilippeLhardy
on est d'accord.
C'est pour cela que j'ai ajouté des boucles "tant que" dans la fonction raffinement.

@PhilippeLhardy
ce n'est pas tout a fait le cas.
en fait, comme dit ici fr.wikipedia.org/wiki/Algorith, on itère à travers la liste des sommets.
On choisit a chaque fois le sommet avec une distance minimale (appelons le S) et on modifie la distance de ses voisins si passer par S est plus court.

@Elijah__

Parles tu d'autre chose que l'algorithem PCC ? Car ton code l'utilise, mais ta distiibution de point pour les collisions elle n'est pas un algorithme décrit par wikipédia, ou bien je me trompe ?

@PhilippeLhardy
Non tu as raison. La génération "aléatoire" de point sert à approcher progressivement le chemin le plus court.

@Elijah__

Dans le cas nominal ( raffinement() sans arguments ) la nature aléatoire sert d'abord à trouver un chemin de contournement des obstacles.

Si je m'amuse à créer un rectangle fin qui coupe l'espace en deux avec cela :

obstacles[3]=new Rectangle(new Point(0, 300), 800, 5);

Le programme raffinement() n'y voit que du feu alors qu'aucun chemin ne peut passer au travers de ce mur.

Lors de la construction des voisins la vérification de non intersection des segments devrait être faite pour éviter ceci.

@Elijah__

un truc en java ça ressemble assez à une sorte de punition.

/o\

@valere pas vraiment. J'ai un oral pour le présenter à 14h. ça va le faire.
Merci quand même à tosu pour l'aide...

@Elijah__ ça marche, bon courage, tient nous au courant

@valere pas vraiment. J'ai un oral pour le présenter à 14h. ça va le faire.
Merci quand même à tosu pour l'aide...

Sign in to participate in the conversation
La Quadrature du Net - Mastodon - Media Fédéré

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!