Probleme de recherche de tous les chemins en théorie des graphes

Discutez d'informatique ici !
Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 02 Juil 2012, 20:42

serieux, vous etes toujours entrain de tergiverser sur la datastructure mais vous relevez pas le truc sur les matrices.

L'idée, j'insiste, c'est d'éviter de tout parcourir à chaque fois. Typiquement en partant de la racine...
Il vaut mieux partir de la fin. Prendre les parents, les numéroter de distance 0,
puis pour chacun des grands parents, voir combien de fils (les parents de la fin) solution ils ont (et les numéroter ainsi), et ainsi de suite, jusqu'à tomber sur la racine et l'épuisement du graphe.

Mais bon, faire des additions/multiplications, ca va aussi je crois :bad:

Enfin pour ta structure de noeuds dlzlogic, non c'est pas la meilleure solution, et c'est certainement pas l'unique. Les matrices sont pas forcément stockées comme un vulgaire tableau 2D (ex: adjency matrix), et je crois pas que quelques miliers de noeuds ralentissent de tant le traitement, ce n'est pas parce que ca prend de la place en mémoire, que ca consomme plus de temps. (généralement, c'est le contraire)

nb: je dis pas qu'il faut utiliser les matrices, notamment si le graphe est déjà représenté sous forme de noeuds.
la vie est une fête :)



Kvas²
Membre Naturel
Messages: 23
Enregistré le: 20 Juin 2012, 14:35

par Kvas² » 03 Juil 2012, 14:00

fatal_error a écrit:serieux, vous etes toujours entrain de tergiverser sur la datastructure mais vous relevez pas le truc sur les matrices.

L'idée, j'insiste, c'est d'éviter de tout parcourir à chaque fois. Typiquement en partant de la racine...
Il vaut mieux partir de la fin. Prendre les parents, les numéroter de distance 0,
puis pour chacun des grands parents, voir combien de fils (les parents de la fin) solution ils ont (et les numéroter ainsi), et ainsi de suite, jusqu'à tomber sur la racine et l'épuisement du graphe.

Mais bon, faire des additions/multiplications, ca va aussi je crois :bad:

Enfin pour ta structure de noeuds dlzlogic, non c'est pas la meilleure solution, et c'est certainement pas l'unique. Les matrices sont pas forcément stockées comme un vulgaire tableau 2D (ex: adjency matrix), et je crois pas que quelques miliers de noeuds ralentissent de tant le traitement, ce n'est pas parce que ca prend de la place en mémoire, que ca consomme plus de temps. (généralement, c'est le contraire)

nb: je dis pas qu'il faut utiliser les matrices, notamment si le graphe est déjà représenté sous forme de noeuds.

Merci Fatal_error mais j'ai un peu de mal à te suivre. C'est facile de dire qu'on part des feuilles et qu'on essaie de remonter jusqu'à la racine. Pour un etre humain c'est facile car nous avons sur un tableau, une ardoise, ou une feuille sur laquelle la structure est déjà organisée.

Eh oui, maintenant, il faut qu'on trouve une structure qui nous permettra de faire ce parcours là et surtout pas une matrice.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 03 Juil 2012, 15:20

et surtout pas une matrice

ah bon? pourquoi?

et sinon il suffit d'avoir la liste de parents dans chacun de noeuds...
la vie est une fête :)

Cliffe
Membre Rationnel
Messages: 967
Enregistré le: 12 Juin 2012, 15:25

par Cliffe » 03 Juil 2012, 17:53

Essaye ça : Lien

Tu fais une dérécursification et tu rajoute une condition qui te fait sortir lorsque que tu dépasse "l" éléments.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 03 Juil 2012, 19:56

premier poste:
Je veux alors dresser la liste de tous les chemins possibles entre ces deux sommets

ici, on veut simplement les compter.
la vie est une fête :)

Cliffe
Membre Rationnel
Messages: 967
Enregistré le: 12 Juin 2012, 15:25

par Cliffe » 03 Juil 2012, 21:54

lol, tu rajoute un compteur et tu supprime la structure qui enregistre les chemins ...

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 03 Juil 2012, 22:33

et maintenant si tu relis le premier post, Kvas cherche un algorithme optimisé. Aucun intérêt de parcourir deux fois le même noeud...
la vie est une fête :)

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 03 Juil 2012, 22:45

fatal_error a écrit:et maintenant si tu relis le premier post, Kvas cherche un algorithme optimisé. Aucun intérêt de parcourir deux fois le même noeud...
Sauf si ce noeud est l'intersection de deux chemins différents.
La question posée est bien définie, mais il serait peut-être intéressant de savoir le but de cette opération.

Cliffe
Membre Rationnel
Messages: 967
Enregistré le: 12 Juin 2012, 15:25

par Cliffe » 04 Juil 2012, 08:29

On a pas le droit de repasser par le même sommets pour un même chemin.

Ex :

[CENTER]Image [/CENTER]

Code: Tout sélectionner
1 2 5
1 2 3 4 5
1 2 4 5
1 3 2 4 5
1 3 4 2 5
1 3 2 5
1 3 4 5

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 04 Juil 2012, 12:47

Bonjour, ça d'accord, mais si le sommet 2 a été emprunté une fois, rien n'interdit de l'emprunter une deuxième et une troisième fois.
Dans le cas présent (5 sommets) on a 7 chemins, je n'ose pas imaginer le nombre de chemins possibles avec les milliers de nœuds.

Kvas²
Membre Naturel
Messages: 23
Enregistré le: 20 Juin 2012, 14:35

par Kvas² » 04 Juil 2012, 14:55

Dlzlogic a écrit:Bonjour, ça d'accord, mais si le sommet 2 a été emprunté une fois, rien n'interdit de l'emprunter une deuxième et une troisième fois.
Dans le cas présent (5 sommets) on a 7 chemins, je n'ose pas imaginer le nombre de chemins possibles avec les milliers de nœuds.

C'est justement l'objectif Dlzlogic peu importe la taille et le diametre du graphe.

Kvas²
Membre Naturel
Messages: 23
Enregistré le: 20 Juin 2012, 14:35

par Kvas² » 04 Juil 2012, 14:56

Cliffe a écrit:On a pas le droit de passer par le même sommets pour un même chemin.

Ex :

[CENTER]Image [/CENTER]

Code: Tout sélectionner
1 2 5
1 2 3 4 5
1 2 4 5
1 3 2 4 5
1 3 4 2 5
1 3 2 5
1 3 4 5

t'as tout compris Cliffe!

Cliffe
Membre Rationnel
Messages: 967
Enregistré le: 12 Juin 2012, 15:25

par Cliffe » 04 Juil 2012, 15:00

:lol3:

Reste plus qu'a programmer.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 04 Juil 2012, 16:12

1 2 5
1 2 3 4 5
1 2 4 5
1 3 2 4 5
1 3 4 2 5
1 3 2 5
1 3 4 5
certes mais cest dommage.

on sait que 2 donne deux chemins solutions :
2-5
2-4-5

lorsquon fait 1 2 on a pas encore explore 2.
lorsquon fait 1 3 2, on a deja explore 2...inutile de reexplorer. C'est ce que je m'evertue a dire depuis le debut.
la vie est une fête :)

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite