Théorie des graphes - Nombre de chemins possibles

[Sephi-Chan]

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

[phenix]

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...

[Seren]

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/AL...go002.html

[rygnes]

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).

[Sephi-Chan]

Ç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

[rygnes]

Tout s'explique !
Si toutefois tu pouvais poster la réponse de ta prof, ne te gêne pas !