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.
Sauf si ce noeud est l'intersection de deux chemins différents.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...
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 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 nuds.
Cliffe a écrit:On a pas le droit de passer par le même sommets pour un même chemin.
Ex :
[CENTER] [/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
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :