[algo] Recherche du plus long chemin

Recherche du plus long chemin [algo] - Algo - Programmation

Marsh Posté le 02-06-2004 à 19:44:09    

Voila, je suis arrive tranquille a l'algo du plus court chemin avec dijkstra (mon graphe est entierement pondere et est oriente). Maintenant j'aimerais faire l'inverse. J'ai beau tourner l'algo de Dijkstra dans tous les sens, je me rends compte qu'on ne peut pas l'appliquer  [:wam]  
Conclusion : existe-t-il une autre solution que la recherche exhaustive ?
 
PS: j'ai cherche sur google mais j'ai rien trouve de bien convaincant comme doc.
 
EDIT : j'ai trouve ceci : http://mathforum.org/epigone/sci.m [...] ntu.edu.tw
...apparemment c l'algo de Floyd qu'il faudrait voir...


Message édité par Giz le 02-06-2004 à 19:51:13
Reply

Marsh Posté le 02-06-2004 à 19:44:09   

Reply

Marsh Posté le 02-06-2004 à 21:17:07    

La recherche du plus long chemin??? Est-ce que t'es sur qu'il existe?

Reply

Marsh Posté le 02-06-2004 à 21:19:47    

A priori, le chemin le plus long est infiniment long... ca va être dur à calculer...


---------------
Au royaume des sourds, les borgnes sont sourds.
Reply

Marsh Posté le 02-06-2004 à 22:47:27    

Le chemin le plus long d'un point a un autre....
 
 
 
... c'est de ne pas y aller :D

Reply

Marsh Posté le 02-06-2004 à 22:49:20    

Giz a écrit :

Voila, je suis arrive tranquille a l'algo du plus court chemin avec dijkstra (mon graphe est entierement pondere et est oriente). Maintenant j'aimerais faire l'inverse. J'ai beau tourner l'algo de Dijkstra dans tous les sens, je me rends compte qu'on ne peut pas l'appliquer  [:wam]  
Conclusion : existe-t-il une autre solution que la recherche exhaustive ?
 
PS: j'ai cherche sur google mais j'ai rien trouve de bien convaincant comme doc.
 
EDIT : j'ai trouve ceci : http://mathforum.org/epigone/sci.m [...] ntu.edu.tw
...apparemment c l'algo de Floyd qu'il faudrait voir...


 
tu cherches un chemin hamiltonien ?

Reply

Marsh Posté le 02-06-2004 à 23:19:39    

black_lord a écrit :

tu cherches un chemin hamiltonien ?


Probleme NP-complet... :whistle:  
Bonne chance :p

Reply

Marsh Posté le 02-06-2004 à 23:55:34    

Ce problème prends du sens uniquement sur des graphes orientés. En effet, s'il existe plus d'un chemin entre deux points d'un graphe non orienté, ce problème n'as pas de solution puisqu'alors un cycle existe passant par ces deux points. Donc pour deux points d'un graphe non orienté, on a trois cas de figure:
-pas de chemin du tout, pas de solution
-un seul chemin, solution égale au cout de ce chemin
-plusieurs chemin, pas de solution non plus (aussi grand qu'on le souhaite)
 
Pour un graphe non orienté, c'est la même chose sauf qu'il peut y avoir plusieurs chemins entre deux points sans pour autant y avoir de cycle (et il est facile de le vérifier par un parcours quelconque).
En excluant ce cas, il reste deux cas de figure:
-pas de chemin du tout, pas de solution
-un ou plusieurs chemin, solution égale au cout du plus long chemin(s)
 
Dans ce dernier cas de figure, peut être peut on entreprendre d'appliquer un stratégie gloutone semblable à l'algo de dijkstra sur le calcul du plus court chemin à origine unique, mais j'avoue que je n'ai pas la preuve que ça marche [:autobot]


Message édité par schnapsmann le 02-06-2004 à 23:56:29
Reply

Marsh Posté le 03-06-2004 à 11:12:29    

black_lord a écrit :

tu cherches un chemin hamiltonien ?


 
vivi  :jap: ... et meme le circuit hamiltonien :
(cf def ci apres) -> http://www.bruno-garcia.net/www/polyro/node11.html
 
En fait je cherche a resoudre le probleme du travelling salesman. (voyageur de commerce).
Bien entendu, j'arrive a trouver le chemin le plus court avec Dijkstra avec 8 villes. Je voudrais maintenant trouver le chemin le plus long avec ces 8 villes. (pour etablir des statistiques)...moi qui croyait au depart que c t un pb trivial (inverser Dijkstra) ben en fait c'est moins facile que ca  [:ke-c]  
J'ai pu voir dans un ebook de McGraw Hill :
 


A critical path is a longest path through the dag, corresponding to the longest time to perform an ordered sequence of jobs. The weight of a critical path is a lower bound on the total time to perform all the jobs. We can find a critical path by either " negating the edge weights and running [g]DAG-SHORTEST-PATHS[/g], or " running [g]DAG-SHORTEST-PATHS[/g], with the modification that we replace " " by "-  " in line 2 of INITIALIZE-SINGLE-SOURCE and ">" by "<" in the RELAX procedure.


 
je connais pas cet algo...v voir ca de plus pres

Reply

Marsh Posté le 03-06-2004 à 11:24:09    

Pour le plus long chemin...
 
Prend le taxi !
 

Citation :

Désolé ;)

Reply

Marsh Posté le 03-06-2004 à 11:31:17    

j'ai pu voir encore :


 Am I seeking the longest path in a directed acyclic graph (DAG)? - The problem of finding the longest path in a DAG can be solved in linear time using dynamic programming. This is about the only interesting case of longest path for which efficient algorithms exist.    


 
Donc il doit bien exister un algo efficace

Reply

Marsh Posté le 03-06-2004 à 11:31:17   

Reply

Marsh Posté le 03-06-2004 à 12:56:53    

Giz a écrit :

Bien entendu, j'arrive a trouver le chemin le plus court avec Dijkstra avec 8 villes


Et tu fais comment?

Reply

Marsh Posté le 03-06-2004 à 13:24:50    


Finding longest paths :
 
Finding longest weight paths is important for critical path analysis in schedul-ing problems. However, the graphs must be acyclic, otherwise paths can have arbitrarily large weights. We can find longest paths just by negating all of the edge weights, and then using a shortest path algorithm. Unfortunately, Dijk-stra s algorithm does not work if edges are allowed to have negative weights. However, the Floyd-Warshall algorithm does work, as long as there are no negative weight cycles, and so it can be used to find longest weight paths in acyclic graphs.


 
bon cette fois je crois que je tiens le bon bout :sol:


Message édité par Giz le 03-06-2004 à 13:25:18
Reply

Marsh Posté le 03-06-2004 à 13:31:58    

Ace17 a écrit :

Et tu fais comment?


 
ben  [:google] , tu trouveras l'algo  :sarcastic:

Reply

Marsh Posté le 03-06-2004 à 13:57:52    

Giz a écrit :

ben  [:google] , tu trouveras l'algo  :sarcastic:


Oups désolé en fait je t'avais mal compris. Oui, pour trouver le chemin le plus court on utilise effectivement Dijkstra. J'avais compris que tu parvenais a résoudre le PVC avec 8 villes. Alors forcément je me demandais comment tu faisais, et si ca pourrait marcher avec plus de villes!

Reply

Marsh Posté le 23-07-2004 à 09:04:54    

Algorithme de Bellman modifié ? ( mais bon si ya un cycle c'est mort. )
 
www.google.fr


Message édité par KneXtasY le 23-07-2004 à 09:06:58
Reply

Marsh Posté le 23-07-2004 à 09:42:13    

je vais dire une connerie, mais t'as essayé en faisant 'nouvelle longueur = 1 / longueur' pour chaque segment ? ou avec une soustraction ? ça donne quoi ?

Reply

Marsh Posté le 23-07-2004 à 09:49:23    

KneXtasY a écrit :

Algorithme de Bellman modifié ? ( mais bon si ya un cycle c'est mort. )

Ben de toutes facons si y'a un cycle le plus long chemin n'existe pas...

Reply

Marsh Posté le 23-07-2004 à 15:34:08    

laisse faire, l'algo est aussi complique que de resoudre le voyageur de commerce. Ca revient au meme que de resoudre le PVC (c un pb de bonne permutation).


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 23-07-2004 à 16:38:47    

Ca revient au meme que si ton graphe est complet... je me trompe?


Message édité par Ace17 le 23-07-2004 à 16:39:04
Reply

Marsh Posté le 28-07-2004 à 10:58:50    


 
tiens je viens de faire une recherche sur les problemes NP-difficiles
dont :


Number: 17  
 
Name: Longest Circuit [ND28] 2  
 
 
Input: n-node undirected graph G(V,E); positive integer k.  
 
 
Question: Does G contain a simple cycle containing at least k nodes?  
 
 
Comments: Special cases of this are the famous Travelling Salesman Problem and Hamiltonian Circuit Problem. The latter corresponds to the cases k=n; the former to the case with each graph edge being weighted and also having k=n.  


 
Je l'a v dit, c'est le meme probleme que le PVC  :sarcastic:
 
Ace17 : le graph est considere complet, c'est plus sportif comme ca ;)
 
ou encore plus clairement :
 


Name: Longest Path [ND29] 2  
 
 
Input: n-node undirected graph G(V,E); nodes s and t in V; positive integer k.  
 
 
Question: Is there a simple path between s and t in G that contains at least k edges?  
 
 
Comments: The similarity to Problem 17 should be noted


 
y'en a pas mal sur ce site : http://www.csc.liv.ac.uk/~ped/teac [...] ed_np.html


Message édité par Giz le 28-07-2004 à 11:05:20

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 28-07-2004 à 11:27:30    

et si tu passes tous tes poids en négatif, et que tu cherches le plus court, ça te donnerai pas ce que tu cherches ? :??:

Reply

Marsh Posté le 28-07-2004 à 11:53:00    

bobuse a écrit :

et si tu passes tous tes poids en négatif, et que tu cherches le plus court, ça te donnerai pas ce que tu cherches ? :??:


 
 :non:  
 
1) Dijsktra ne marche pas avec des poids negatifs.
 
2) l'algorithme de Floyd, meme s'il marche avec des poids negatifs,  ne resouds que le chemin le plus court entre une PAIRE de sommet. Trouver le chemin le plus long ne se reduit pas seulement a verifier le chemin le plus long entre toutes les paires de sommets.


Message édité par Giz le 28-07-2004 à 11:57:27

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 09-08-2004 à 15:36:06    

Hello,
 
Pour les DAGs (directed acyclic graph), avec le tri topologique [g]inversé[\g] on sais trouver la longueur du plus long chemin. c'est facile à faire avec un DFS (parcourt depht first search), tu peux utiliser l'ordre preorder. Je sais pas si ça peux t'aider car ce n'est que pour les DAGs.

Reply

Marsh Posté le 09-08-2004 à 19:37:54    

mexx20 a écrit :

Hello,
 
Pour les DAGs (directed acyclic graph), avec le tri topologique [g]inversé[\g] on sais trouver la longueur du plus long chemin. c'est facile à faire avec un DFS (parcourt depht first search), tu peux utiliser l'ordre preorder. Je sais pas si ça peux t'aider car ce n'est que pour les DAGs.


 
Oui tout a fait  :jap:  
...et tu sais comment on construit un DAG ?  :D ... comme tu l'a dis : avec un depth-first search. Bref en gros tu construis tout l'arbre, donc c'est un peu pourri  :p . Comme d'hab, 10 noeud OK, 11 ca commence a ralentir, 12 c'est mort.  [:darkmavis tt]


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 09-08-2004 à 21:36:43    

Construire un DAG ? ben si tu n'as pas de cycle alors tu as un DAG. Pour voir si ton graphe est un DAG il suffit que tu lances un DFS et que tu vérifie qu'il n'y a pas de backedges. Un DAG ce n'est qu'un graphe sans cycles.
 
Mais en fait je pense pas que ca te convienne car il s'agit ici du plus long chemin en terme d'étape, de sommet travesé, on ne tiens pas compte des poids sur les arcs commes le fait dijkstra

Reply

Marsh Posté le 09-08-2004 à 21:41:18    

mais le DFS c'est juste pour faire le tri topologique et ne t'inquiète pas ca marche avec plus de 10 noeuds biensur... DFS c'est un tps proportionel à V2 si tu utilises un matrice d'adjacense et V+E pour une liste d'adjacence ... donc rien de terrible
 
V= nb de sommets
E= nb d'arcs
 
quand tu dis construire tout l'arbre ? tu veux dire du backtracking ? oui mais ca c'est la pire des solutions que tu peux faire ... oui ca marche mais c'est vraiment pas optimal, ce n'est pas un dfs, mais un backtracking (ou brute force)

Reply

Marsh Posté le 09-08-2004 à 21:44:15    

joubliais, apres la tri topologique, il reste a faire un truc en un tps proportionel à V ... donc au total ca reste la complexité du DFS.  
 
si tu penses que ca te convient comme truc je peux te poser l'algo en pseudo code mais je te demande avant pour pas faire l'effort de m'en souvenir pour rien (meme si c un bon exo) =)

Reply

Marsh Posté le 10-08-2004 à 10:11:23    

mexx20=> avec ton tri topologique tu crées tout l'arbre. Je veux dire que tu vas tout le parcourir avec un DFS !. Parcourir un arbre entièrement va poser un énorme problème de temps !. Il s'agit d'un algo à complexité exponentielle (= NP-complet). Comme je l'ai dis, pour un graphe avec 10 noeuds OK, 11 ça ralenti, 12 c'est mort (==> complexité de x puissance N, x constante et N taille du probleme (dans ce cas N = nombre de noeuds/relations)).
De toute facon, il n'est pas difficile de voir que c'est un problème NP-complet, pourquoi ?
 
Imagine que tu developpes TOUT l'arbre SAUF une arête (la dernière qui te crée la dernière feuille de l'arbre). Ben il se peut très bien que en ayant developpé cette dernière arête, celle-ci appartient au chemin le plus long (dans le cas où son coût est gigantesque par rapport à toutes les autres arêtes) => conclusion : ben tu es obligé de développer tout l'arbre pour être sûr d'avoir la solution optimale. Bon après il y a toujours moyen de faire un algo de type B&B (branch and bound) qui permet de couper des branches dans ton arbre. Mais l'algo devient difficile pour ne pas gagner énorme...ton algo restera toujours d'une complexité exponentielle du fait que tu résouds le problème en développant l'arbre.
 
PS : et quand je parle du plus long chemin, c'est bien en terme de poids, pas du nombre d'arête du chemin (qui revient à dire que toutes les arêtes ont un poids de 1...ce qui est réducteur comme généralisation du problème.) hein  :ange:


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 10-08-2004 à 15:20:49    

Bon apparement tu n'as pas bien compris.
 
Oui le problème du plus long chemin EN TERME DE POIDS est "intractable" (NP-Complet si tu veux). Il faut un backtracking (recherce exhaustive).  
 
Moi je suis venu te dire qu'il existe une solution efficace pour le problème en TERME DES SOMMETS.  
 
Tu dis que c'est réducteur, je ne suis pas d'accord. Il s'agit de 2 problèmes différents.  
 
Encore une fois : un DFS n'est pas un backtracking.
 
[quote]
ne t'inquiète pas ca marche avec plus de 10 noeuds biensur... DFS c'est un tps proportionel à V2 si tu utilises un matrice d'adjacense et V+E pour une liste d'adjacence ... donc rien de terrible
 
V= nb de sommets
E= nb d'arcs  
[\quote]
 
Tu peux lancer DFS sur des graphes enormes pour construire un tri topologique. Aucun problèmes.
 
Bon maintenant; il reste à savoir si pour ton application tu as besoin du plus long chemin en terme de poids ou en terme de sommets.

Reply

Marsh Posté le 10-08-2004 à 15:27:57    

Ouais pour le coup de la généralisation finalement tu as quand meme raison car comme tu le dis si bien ce sont des arcs de longueur 1. Enfin voilà, si t'es intéressé par l'algo pour ce cas particulier donc, fait moi signe et je te montrerai que le tri topologique c'est une connerie qui fonctionne sur des graphes gigantesques.

Reply

Marsh Posté le 10-08-2004 à 15:32:54    

En fait c'est meme tres réducteur :)
1. Tout les poids sont à 1.
2. C'est uniquement pour les DAGs
3. Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...
 
Ouais c'est bien nul comme truc, mais c'est la seule méthode efficace dont je me souvienne, mais je pense qu'il y a d'autres astuces pour d'autres types de graphes pour éviter la recherce exhaustive  ... => Google :)

Reply

Marsh Posté le 10-08-2004 à 16:20:20    

mexx20 a écrit :

En fait c'est meme tres réducteur :)
1. Tout les poids sont à 1.
2. C'est uniquement pour les DAGs
3. Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...
 
Ouais c'est bien nul comme truc, mais c'est la seule méthode efficace dont je me souvienne, mais je pense qu'il y a d'autres astuces pour d'autres types de graphes pour éviter la recherce exhaustive  ... => Google :)


 
Ouai bof j'apelle pas ca efficace. Honnêtement, ca sert a quoi un algo de chemin le plus court/long en utilisant un DAG. Rien qu'a faire un tri topologique, tu construis l'arbre donc, si tu parcours l'arbre en entier, ca ne sert a rien de construire un DAG apres [:figti]  :??:


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 10-08-2004 à 16:30:02    

Heu... pas efficace ? V^2 ou V+E ... :-|
 
C'est efficace car ce n'est ni plus ni moins qu'un DFS.
 
On ne construit pas l'arbre des solutions on fait un simple parcours du graph ! C'est linéaire. Tu veux du constant ? T'es fou toi :)
 
Je te rappelle que le tri topologique ce n'est rien de terrible, un simple DFS ! Il suffit de garder la numérotation postordre. Il exisste d'autres méthodes comme celle qui consiste à retirer les sources une à une en diminuant le degré entrant, mais c'est équivalent en terme de complexité. Il y a d'autre méthodes, toutes équivalentes.
 
Je ne te parle pas de construire un DAG, mais c'est une hypthèse que ton graph soit un DAG.

Reply

Marsh Posté le 10-08-2004 à 16:55:06    

Mais bon, c'est pour une classe de graph correspondant aux critères énoncés plus haut. Mais c'est toujours comme ça pour les problèmes où on ne connait pas de solutions efficaces, il y a toujours certaines classes parfois très restreintes pour lesquelles il existe de solutions efficaces. Jusqu'au jour où un génie magicien nous sortira la solution élégante.
 
Bon allez pour l'exercice voici de mémoire l'algo pas très compliqué finalement :
 

DFS_TRI_TOPOLOGIQUE ( int v )
   marquer( v )
   POUR (tout les sommets t adjacent à v) FAIRE
      SI ( t n'est pas marqué ) DFS_TRI_TOPOLOGIQUE (t)
   FINPOUR
   post[v]= postordre
   postindex[postordre++] = v


 
Voilà, ici tu auras le tri topologique, après un simple DFS :)
Ensuite, il reste un truc de la meme complexité, donc ca reste toujours celle du DFS.
 

POUR(tout les sommets v du graphe)
   longueur = -1
   vers = -1
   POUR (tout les sommets t adjacent à post[v])
      SI (lg[postindex[t]] > longueur) ALORS
         longueur = lg[postindex[t]] ;
         vers = t;
      FINSI
   lg[i] = ++ longueur;
   chemin[post[v]] = vers;
   FINPOUR


 
Alors c'est simple mais un peu complexe à s'y retrouver : la longueur du plus long chemin de post[i] vaut lg[i]. Si maintenant tu veux connaitre le chemin le plus long en partant du sommet s, il suffit de parcourir le vecteur chemin de cette façon :
 

TANTQUE( chemin[s] != -1)
   afficher(s);
   s = path[s];  
FINTANTQUE

Reply

Marsh Posté le 10-08-2004 à 16:59:57    

C'est pas efficace, d'accord, c'est optimal :)

Reply

Marsh Posté le 10-08-2004 à 17:42:09    

mexx20 a écrit :


Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...  


 
Deux phrases contradictoires ? :heink: (en anglais : ALL-PAIRS-SHORTEST-PATH => cf. Floyd)
 

mexx20 a écrit :


1. Tout les poids sont à 1.


 
La valeur du poids n'a pas d'importance. Le probleme reste NP-Complet
 

mexx20 a écrit :


Heu... pas efficace ? V^2 ou V+E ... :-|  
 
C'est efficace car ce n'est ni plus ni moins qu'un DFS.  


 
Oui le DFS est efficace en mémoire. En temps non !
 

mexx20 a écrit :


On ne construit pas l'arbre des solutions on fait un simple parcours du graph


 
Encore contradictoire. Ton parcours de tous les chemins possibles dans ton graphe, c'est comme la complexité d'un arbre. Imagine un graphe complètement connecté, le temps du DFS explose.
 

mexx20 a écrit :


C'est efficace car ce n'est ni plus ni moins qu'un DFS.  
...
C'est pas efficace, d'accord


 
Encore contradictoire.
 
Et enfin, le rappelle le sujet de l'algo (peut etre plus explicite cette fois): Etant donné un graphe sans cycle, orienté et pondéré, trouver le chemin le plus long.
 
Et pour finir :


For example, we saw an efficient algorithm in Chapter 31 for the following problem:  Find the shortest path from vertex z to vertex y in a given weighted graph.  But if we ask for the longest path (without cycles) from x to y, we have a problem for which no one knows a solution substantially better than checking all possible paths.
 
ROBERT SEDGEWICK - Algorithms.


 
Je pense donc qu'il est inutile de s'attarder plus sur ce problème...que j'ai abandonné depuis longtemps ;).


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 10-08-2004 à 20:27:23    

"Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...  "
 
Non ce n'est pas contradictoire. Bon, soyons plus clair car il vrai que cette phrase porte à confusion. En fait ce dont je parle c'est : tu donnes un sommet S et depuis ce sommet il te calcule le plus long chemin, mais tu ne sais pas où tu vas aboutir, c'est ça que je voulais te dire lorsque je disais "vers n'importe quel sommet". Tu l'aurais compris si tu avais un peu regardé l'algo ...
 
Moi je laisse tomber le problème de faire comprendre que dans certains problèmes non résolu il y a parfois des cas particulier où une solution efficace existe. En l'occurence les graphes ayant les caractéristiques précitées plus haut.
 
Oui je sais bien que tu veux la solution générale, moi j'ai juste dis ce que je savais sur le sujet. Et puis on en sais rien, ca dépend des applications, tu pouvais aussi ne pas être certain de ce que tu souhaitais.
 
Soit tu es de mauvaise foi, soit tu ne comprend rien.
 
Ca m'apprendra à perdre mon temps à vouloir rendre service, j'ai comme l'impression que tu n'as même pas fait l'effort de comprendre ce que je voulais dire.  
 
Et puis arrête de te cacher derrière Floyd et Sedgewick, les choses évoluent, la théorie des graphes est étudiée massivement de part le monde et tes bouquins sont statiques.

Reply

Marsh Posté le 10-08-2004 à 20:32:39    

Pour la complexité du DFS, je maintient ce que j'ai dis. Elle est moindre que celle d'un backtracking (recherche exhaustive).

Reply

Marsh Posté le 10-08-2004 à 20:45:00    

Honnêtement je préfère une bonne explication à un algo. Et d'après ton explication j'ai comme l'impression que tu parcours tout l'arbre.
Pour le DFS ca te parcours un chemin du graphe, backtracking, ca te parcours tout les chemins du graphe. On peut assimiler le backtraking comme une succession de DFS
Bon pour résumer de la complexité du DFS:


Completude : non, si la profondeur est infinie (cycles ?) ; oui, si evitement d' etats repetes ou espace de recherche fini
Complexite temporelle : O(b puissance m)
Complexite spatiale : O(bm), lineaire
Optimale : non


 
et voila ;)


Message édité par Giz le 10-08-2004 à 20:45:24

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 10-08-2004 à 21:11:49    

Non, je ne parcours pas tout l'arbre, je ne fais qu'un tri topologique avec un DFS.
 
Bon, un DFS n'a pas une complexité exponentielle. Sa complexité temporelle est en V^2 si tu utilises une matrice d'adjacence pour représenter ton graphe (de part la structure d'une matrice) et en V+E si tu utilises une listes d'adjacence (de part la structure de liste). Il s'agit donc d'une complexité temporelle LINEAIRE (part rapport aux données). Ca n'explose rien du tout avec tes 12 sommets de rien du tout.
 
Faut-il te rappeller l'algo du DFS ? De toute façon je l'ai posté plus haut.
 
Par contre un backtracking (qui parcout l'arbre de toutes les solutions, aussi appelé recherche exhaustive) à une complexité exponentielle. Et dans ce cas en effet, ca explose vite lorsque le nombre de sommets grandit.
 
Les complexités que tu exposes de je-ne-sais-ou sont celles d'une recherche exhaustive.
 
Je pense donc que tu confonds DFS et backtracking. Si c'est le cas, je te pardonne. Sinon je souhaite te voir bruler vif.
 
Bon, et pour l'algo je veux bien t'expliquer son fonctionnement si le code ne te suffit pas mais je perd un petit peu patience.


Message édité par mexx20 le 11-08-2004 à 15:10:47
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed