Bonjour a tous (ca fait 3 fois que je retape ce message a cause de mon mot de pass qui n'etait pas correcte........)
 
Donc j'ai cet arbre (je suis pas sure que ce soit un arbre, mais appelons ca un arbre tout de même que que son fonctionnement reste le même)
on dira que cet arbre a une dimension 10*10, 10 en largeur, 10 en hauteur :

 
et je souhaite récuperer 100 DES plus LONG chemins (je n'ai pas besoins d'avoir les 100 plus longs, un chemin de longueur Dim/2 me suffirai) pour joindre 01 à 99 en suivant quelques règles :

• Pas de retour en arrière
• Pas de boucle
• Pas de blocs. Exemple de chemin incorrecte : 01 -> 02 ->12 -> 11

Donc je suis a la recherche d'un algo performant qui pourrai réaliser cette tache relativement rapidement
 
J'ai déja essayé plusieurs algo classiques (parcours en largeur et en profondeur) et Dijkstra mais c'est trop long puisque ces algo parcourent tout l'arbre et il y a a peu près 54 000 possibilitées pour joindre 01 à 99 en suivant ces règles, et environ 230 000 pour un arbre de dimension 11*10. Je vous laisse immaginer le temps que mettra ces algo pour parcourir un arbre de dimension 18*15 (mon objectif)...  
Et je ne vois pas comment A* pourrai m'aider pour cette tache.
 
Pour l'incetant, le plus rapide que j'ai c'est un parcours en profondeur : si le parcours atteinds 99 avec une distance de parcours supérieur a Dim/1.8 alors on le conserve, et on continue jusqu'a en obtenir 100. Le problème c'est la diversité : avec cette methode jobtiens 100 chemins, mais 90 qui se ressemplent vraiment (à 2 noeuds près c'est les mêmes). Donc je suis obligé d'en générer 1000 et de supprimer ceux qui se ressemblent trop
 
 
Merci de votre aide, et désolé pur les fautes de français ^^

j'ai eu la réponse sur ce forum de CommentCaMarche 3 heures après avoir posté mon message sur leur forum. (pour bientot 3 jours sur ce forum toujours sans aucun réponse, ni même une demande de précision     )
 
Pour ceux qui aurai le même problème : http://www.commentcamarche.net/for [...] ong-chemin
 
 
Merci de votre inactivité.
 
 
 
 
 
 
ps, pour ce qui est du forum, proposerz d'heberger les photos, ca évite de devoir passer par un hebergeur externe donc c'est plus lisible

Pas besoin d'être condescendant.
 
Aller pour redorer le blason de ce forum, un nouvel algo pour la route.
Avantage:
- ultra rapide
- facile à implémenter
- peu couteux en ressources
- probablement une solution proche du maxima (mais pas la meilleure solution)
 
Le plus simple serait de valuer ton graphe:
Tu pars du nœud 01, chaque arrête en partant choppe 1. De chaque arrête derrière ces premiers nœuds (Je parle donc des nœuds 02 et 11), te donneras alors 2. Et ainsi de suite.
=> c'est assez proche de la première réponse, sauf que le gus value les nœuds, il est rare qu'on est besoin de valuer les nœuds, c'est bien plus intéressant de valuer les arrêtes.
 
 
Partant de là, reste à parcourir le merdier:
Tu pars du noeud avec les plus grosses arrêtes, et tu remontes en choisissant toujours l'arrête dont la valeur est la plus proche MAIS pas égale au maximum.
 
Autrement dit, ton algo ressemble bcp à du toposort par exemple, cad tu as nécessité de savoir si tu es passé par là ou pas. En valuant tes arrêtes de la sorte, tu es sur un parcours plus ou moins linéaire/dichotomique tout en étant sur de ne pas être passé par là.
 
Pour toposort (ca se rapproche dans l'idée, pas dans le résultat):
https://en.wikipedia.org/wiki/Topological_sorting
 
De facto:
- La valuation, couplé à la façon dont ton graphe est, empêche les retours en arrière, et les boucles.
- Prise du dernier point vers le premier, tu évites aussi les chemins "longs" pour le plaisir. Cad pas de bloc possible.
- Au passage tu te permets d'avoir quelque chose d'assez linéaire, tout en ayant un résultat qui ne sera pas le meilleur, mais en tout cas assez proche du plus long possible.

Merci pour ta réponse Devil'sTiger
 
Mais ce type d'algo est préféremment utilisé utilisé pour la recherche du plus court chemin, pas dans la recherche des plus long..
 
En fait c'est Dijkstra en valuant les arretes plutot que les noeuds ^^
 
J'avais déja essayé ce type d'algo, mais le temps de calcul explose radicalement vue le nombre de récursion de l'algo.. (et peut prendre quelques heures pour trouver un chemin suffisemment long pour un graphe de 12*12...) j'ai pas encore codé la premiere solution que j'ai trouvé, mais a prioi vue son fonctionnement je devrai arriver a une solution utilisable en un nombre d'iteration limité (techniquement, une 500 iterations devraient suffire pour trouver un chemin long)
 
Mais merci quand meme

On peut ptete tourner le résultat et la recherche autrement, question conne, mais pourquoi tu as besoin du chemin le plus long ?
 
D'ab c'est plutôt l'inverse que l'on cherche...
 
Au passage ton pb à première vue est NP Complet donc tu ne peux effectivement pas calculer la solution directement, il te faudra dans tous les cas soit faire des stats, soit des raccourcis pour y arriver en un temps polynomial correct...
 
PS: nope c'est pas dijkstra ce que j'ai fait là, bien plus rapide
PS2: l'algo que j'ai fait est à mi-chemin: il va chercher le plus long MAIS sans faire le serpentin (cad il va quand même essayer d'arriver à une sorte de droite entre les deux extrémités).
Normalement un algo comme ca devrait suffire, il est très rapide, et consomme rien, mais comme dit a aucune chance de donner "le plus long" puisque le plus long est de faire le serpentin ligne par ligne (cad le chemin possible qui compte le plus d’arête et sans boucle).

L'algo de Floyd-Warshall en utilisant le Max au lieu du Min ne pourrait-il pas résoudre ton pb ?
 
https://fr.wikipedia.org/wiki/Algor [...] d-Warshall
 
Edit : l'algo de Kruskal des poids min d'un arbre peut être intéressant aussi, pareil, en remplaçant le tri croissant par un tri décroissant.
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal