Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2470 connectés 

  FORUM HardWare.fr
  Programmation
  Divers

  Recherche des plus longs chemins dans un arbre [Resulu]

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Recherche des plus longs chemins dans un arbre [Resulu]

n°2264835
gueuldange
Posté le 26-08-2015 à 10:11:47  profilanswer
 

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 :
http://img15.hostingpics.net/pics/310802Capture2.png
 
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 ^^


Message édité par gueuldange le 28-08-2015 à 20:05:53
mood
Publicité
Posté le 26-08-2015 à 10:11:47  profilanswer
 

n°2264952
gueuldange
Posté le 28-08-2015 à 20:01:43  profilanswer
 

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  :pfff:  :pfff: )
 
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


Message édité par gueuldange le 28-08-2015 à 20:08:11
n°2264983
Devil'sTig​er
Posté le 29-08-2015 à 23:34:30  profilanswer
 

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.

n°2265026
gueuldange
Posté le 31-08-2015 à 09:37:47  profilanswer
 

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


Message édité par gueuldange le 31-08-2015 à 10:23:06
n°2265151
Devil'sTig​er
Posté le 01-09-2015 à 19:39:57  profilanswer
 

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

n°2265230
rufo
Pas me confondre avec Lycos!
Posté le 03-09-2015 à 13:54:34  profilanswer
 

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


Message édité par rufo le 03-09-2015 à 13:59:29

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Divers

  Recherche des plus longs chemins dans un arbre [Resulu]

 

Sujets relatifs
[VBA] Créer une fonction "Recherche", "Bug liste déroulante" ...Recherche de script - relancer un .exe en cas de crash
[Shell Linux] Recherche dans un fichier evoluéWordpress - modifier langue du moteur de recherche
VBS copie de fichiers avec recherche de nomRecherche de développeur de jeux tout niveau pour site
VBA avec recherche vRecherche d'un caractère dans un tableau et affichage d'un message
Plus de sujets relatifs à : Recherche des plus longs chemins dans un arbre [Resulu]


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR