Bonjour,
Je cherche à créer un algorithme pour trouver tous les chemins les plus courts d'un certain type de graphe que voici.
Soit un graphe connecté non-orienté (j'utilise une grille x*y) ayant des sommets A ou B :
- les sommets A doivent être passés un nombre impair de fois
- les sommet B doivent être passés 0 fois ou bien un nombre pair de fois
L'objectif est de trouver tous les chemins les plus courts, partant d'un sommet défini B, qui remplissent les conditions ci-dessus.
J'utilise une variante de l'algorithme A*, en créant progressivement tous les chemins possibles et en leur associant un coût, le coût étant le nombre de sommets devant être atteints.
Je ne continue qu'avec les chemins ayant le plus faible coût.
Le problème est que à partir d'une certaine grandeur de la grille, le nombre de chemins générés est trop grand.
Mon schéma algorithmique :
Pour chaque tracé ayant le coût le plus bas
-> récupérer les voisines de la dernière position (avec une liste adjacente)
-> dupliquer le tracé et ajouter chaque voisine à la fin
-> supprimer le tracé original
-> calculer le coût de chaque nouveau tracé : le nombre de passages nécessaires sur les sommets A et B
Trier les tracés en fonction de leur coût et recommencer.
Je suis bloqué sur ce problème de nombre de tracés générés, si des personnes ont une solution, peut-être en revoyant un calcul de coût plus précis et qui filtre mieux?
Merci d'avance
Bonjour
obwil, quel est ton niveau sil te plaît ? (à mettre dans ton profil)
Pardon, j'ai rajouté l'information, je suis de niveau BTS mais sans rapport avec les mathématiques, mon apprentissage des maths s'est arrêté au bac scientifique option physique chimie.
Ce problème est lié à un projet personnel, et toutes les connaissances sur les algorithmes, la programmation et les graphes ont été acquises en autodidacte.
Dans les chemins qui sont acceptables, tu peux avoir des chemins qui font plein de fois un zig-zag entre 2 points, tu peux avoir des chemins de longueur infinie.
A priori, même si la grille est toute petite, tu as ce problème de 'nombre de chemins générés trop grand', ou alors, il y a un truc que tu ne dis pas.
Une piste, c'est de chercher dans un premier temps un chemin qui satisfait toutes les contraintes. Un chemin pas forcément optimal.
Ensuite, quand tu recenses tous les chemins possibles, tu te limites aux chemins qui sont plus courts (ou de même longueur) que le chemin déjà trouvé,parce que de toutes façons, ceux qui sont plus longs ne t'intéresseront pas au final.
Sinon, le point bizarre dans ton histoire, c'est que tu envisages de passer plusieurs fois par le même point. Pour une recherche de plus court chemin, c'est bizarre. Détaille les raisons, et on trouvera certainement une modélisation qui prendra en compte tes contraintes et tes objectifs.
Cet algorithme est lié à un jeu que je crée dont le but est de remplir une grille d'une même couleur. Il y a des cases blanches, et quand on passe dessus elle deviennent bleues (=> les sommets A), et il y a des cases bleues qui deviennent blanches quand on passe dessus (=> les sommets B). L'objectif est d'avoir toutes les cases en bleu en le moins de déplacements possibles.
Je ne retiens que cette partie de ton message. Le début était moins clair.
Du coup, pour décrire une position, tu as besoin de dire : Mon 'personnage' est sur telle case, et les cases qui sont bleues sont .... et la liste des cases bleues.
Si à un moment, le personnage fait des aller-retour, et il se retrouve sur la même case que 8 ou 10 tours avant, avec en plus les mêmes cases en bleu, ça veut dire que les 8 ou 10 mouvements en question n'ont servi à rien.
Et donc tu peux interdire cette configuration.
La séquence (case1, case2, case1, case2, case1) a un sens, uniquement si à la fin des cette succession de 4 mouvement, on a des couleurs différentes sur l'une ou l'autre des cases.
Sinon, c'est une branche morte dans notre arbre.
En supprimant les branches mortes, tu devrais t'en sortir sans trop te prendre la tête.
Sauf si ta grille de jeu est vraiment très grande (100x100 par exemple)
Juste pour éclairer un peu, au cas où :
A chaque fois qu'on passe sur une case, elle change de couleur ?
Ou bien, c'est autre chose.
Un autre paramètre dans le calcul du coût qui pourrait être intéressant serait de rajouter la distance entre le curseur et toutes les cases blanches (sommets A).
Juste pour info, tu cherches un parcours pour que toutes les cases soient bleues au final.
J'imagine que tu as une grille constituée de carrés, une grille classique (pas une grille constituée de triangles ou d'hexagones ou de je ne sais quoi).
Et en fait, il y a plein de configurations où il n'y a aucune solution.
100 000 possibilités pour 13 étapes, c'est normal : 2 ou 3 possibilités à chaque étape, ça nous fait plus de 100000 branches à l'arrivée.
Dans ce genre de problème, une piste, c'est de garder sous le coude les pistes les moins prometteuses, et d'explorer à fond les pistes les plus prometteuses. Et pour savoir si une piste est prometteuse, on peut regarder si elle nous approche de la solution, c'est à dire si on a beaucoup de cases bleues.
Et donc dans ton tableau avec toutes les situations possibles et imaginables, tu auras des parcours avec 2 étapes par exemple, et en même temps, d'autres parcours avec 10 ou 20 étapes.
Oui c'est une grille classique constituée de carrés.
Je suis d'accord avec toi, c'est pour ça que j'utilise le principe de l'algorithme A* qui fait appel au concept de "coût" qui est plus ou moins le niveau de rapprochement de la solution.
Quand je génère tous les tracés possibles d'une grille pour trouver les plus courts j'ai toujours une évolution du nombre de tracés sous la forme d'une bosse.
Pour une grille de 5x5 avec un chemin le plus court qui est à 28 déplacements, vers les 13 à 17 déplacements j'atteins le haut de la bosse avec plus de 100 000 tracés, malgré les filtres évoqués précédemment..
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :