+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Théorie des graphes - Nombre de chemins possibles (/showthread.php?tid=3380)
Théorie des graphes - Nombre de chemins possibles - Sephi-Chan - 06-12-2008
Bonjour,
Cette semaine, je suis des cours de théorie des graphes, et je dois reconnaître que j'aime bien ça. Il faut dire aussi que c'est très utile dans le cas des jeux.
Toutefois, j'ai un petit problème… Je cherche un algorithme de pathfinding qui détermine le nombre de chemins possibles (pas les plus court, seulement la totalité). Je ne suis pas fou, c'est un algorithme qui sera utilisé sur de petits graphes.
Connaissez-vous un tel algorithme ?
Sephi-Chan
RE: Théorie des graphes - Nombre de chemins possibles - phenix - 06-12-2008
Peut être en modifiant l'algorithme de Dijkstra.
Enfin, ce serait plus s'en inspiré voir l'utilisé en "bouchant" successivement les chemins déjà trouvé.
D'un autre coté, j'ai du mal a voir l'intérêt, car il suffit de changé une case pour trouvé un autre chemin, tu te retrouve donc avec beaucoup de chemin...
RE: Théorie des graphes - Nombre de chemins possibles - Seren - 06-12-2008
J'en connais pas, par contre je vois un problème si ton graphe à des cycles, il y a une infinité de chemins possibles.
Je suis tombé là dessus par hasard, ça ne parait pas totalement complet, notamment comment construire tous les chemins à partir du tableau.
http://www.loria.fr/~cirstea/TEACHING/ALGOAV/algo002.html
RE: Théorie des graphes - Nombre de chemins possibles - rygnes - 06-12-2008
Tous les chemins implique de trouver le nombre chromatique.
Or, il n'existe pas d'algorithme généraliste à ce niveau.
Tu peux te baser sur l'algorithme de Welsh et Powell (qui semble plus intéressant dans une large mesure que celui de Disjkstra) mais pour trouver tous les chemins possibles tu devras développer toi même un algorithme propre à tes besoins.
Comme phenix, je m'interroge sur l'intérêt de cette méthode.
Pourquoi vouloir concevoir un tel algorithme alors que le cerveau humain est capable de le résoudre sans trop de problème avec un bon graphe ?
(Ton lien est intéressant Seren).
RE: Théorie des graphes - Nombre de chemins possibles - Sephi-Chan - 06-12-2008
Ça n'a strictement aucun intérêt, c'est purement didactique.
Merci en tout cas, je vais chercher de mon côté et demander à ma prof'.
Sephi-Chan
RE: Théorie des graphes - Nombre de chemins possibles - rygnes - 06-12-2008
Tout s'explique !
Si toutefois tu pouvais poster la réponse de ta prof, ne te gêne pas !