Inscription / Connexion Nouveau Sujet
Trouver les chemins les plus courts d'un type de graphe
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)
extrait de 
la FAQ du forum :Q12 - Dois-je forcément indiquer mon niveau lorsque je poste un nouveau sujet ?
équivalences des systèmes de niveaux scolaires
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.
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.
Correction :
Pour chaque tracé X ayant le coût le plus bas
-> récupérer les voisines de la dernière position (avec une liste adjacente)
-> pour chaque voisine dupliquer le tracé X et ajouter la voisine en dernière position
-> supprimer le tracé X
-> calculer le coût de chaque nouveau tracé : le nombre de passages nécessaires sur les sommets A et B + le nombre de déplacements du tracé
Trier les tracés en fonction de leur coût et recommencer.
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.
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.
Effectivement je pourrais avoir des chemins infinis, mais arrivera un cycle où j'obtiendrai tous les chemins les plus courts et alors j'arrête l'algorithme. Le calcul du coût est le suivant : après analyse des différents passages effectués sur les sommets j'additionne le nombre de passage nécessaire pour chaque sommet du graphe (0 ou 1) et j'ajoute le nombre de déplacement du chemin/tracé.
Une piste, c'est de chercher dans un premier temps un chemin qui satisfait toutes les contraintes. Un chemin pas forcément optimal.
.
Alors j'ai trouvé une petite fonction qui me permet d'avoir ça, brièvement elle consiste à enchainer des aller-retour entre le sommet de départ et chaque sommet A.
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.
Pour trouver les chemins les plus courts je dois générer au fur et à mesure tous les chemins possibles et il arrive un moment, avant même d'avoir trouver la longueur minimale, ou je sature en chemins possibles.
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.
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.
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.
Oui à chaque fois que l'on passe sur une case elle change de couleur.
L'idée de créer des filtres est effectivement une piste que j'ai suivie, mais il m'a fallu beaucoup plus de temps que toi pour les trouver haha.
Comme filtres j'ai :
- si un tracé aboutit à une grille identique à celle d'un tracé ayant moins de déplacements je le supprime.
- si un tracé aboutit à une grille identique à celle d'un tracé de même longueur je le mets de côté
- d'autres filtres qui sont un peu approximatifs (par exemple le nombre de groupes de cases blanches qui obligent à passer sur un certain nombre de cases bleues).
Hélas ces filtres n'ont pas été suffisants dans mon algorithme pour limiter suffisamment le nombre de tracés.
Par exemple pour une grille de 5x5, pour tous les tracés ayant 13 déplacements j'étais à plus de 100 000 résultats...
Donc j'en conclue que cette méthode de filtrage n'est pas suffisante, et je cherche une autre approche...
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..
Annuler
connectez vous