Reprise du message précédent :
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.

 
Bon on va dire que j'ai pas compris mais avant :
 
- Démontre moi que dans ta récursivité, tu ne parcours pas tout l'arbre !  
- Démontre moi que la complexité temporelle de ton "DFS_TRI_TOPOLOGIQUE" est linéaire
Je pense connaître l'algo du DFS et un backtracking est un DFS sur chacun des chemins de l'arbre. Je te signale que ton algo "DFS_TRI_TOPOLOGIQUE" est une belle implémentation du backtracking
 
J'attends tes explications    
 
PS : surveille ton vocabulaire un peu  , je ne t'ai jamais "traiter" moi  

je m'y connais que très peu, mais ca m'intéresse l'algo en question.
 
Je m'en sers dans l'optique citée plus haut, pour trouver le chemin critique (ordonancement de taches)...donc sur un graph orienté avec un puit et une source, le poid étant sur les sommets (on peut le faire avec le poid sur les arcs, mais c moins puissant)...
 
si qqn pouvait au moins me donner le nom de cet algo ca m'intéresserait bcp ...g lu Hamilton, je sais pas si c ca...

 
Pour moi, il s'agit d'un problème NP-Complet. J'attends la démonstration de mexx20 qui semble avoir trouvé un algo polynomial (et meme linéaire   )

pour etre sur qu'on soit d'accord, je parle d'un truc comme ca :  
http://www.mindtools.com/critpath.html (avec le tableau source qui donne le poid des taches, le recouvrement éventuel, les dates de départ forcées, etc...)
 
pour sortir un graph avec des noeuds comme ca :  
 

 
Je vois ton problème, c'est de l'ordonnancement des tâches. Je résume ce que j'ai cru comprendre (j'ai regardé ton lien vite fait). En fait il s'agit de trouver la pire séquence qui prendra le plus de temps selon un ordonnacement des tâches donné. Le but est de trouver le bon ordonnacement qui te permettra de minimiser la pire séquence (pire = qui prends le plus de temps) tout en étant sûr de mener a bien (de réaliser) toutes les tâches. C'est ça ?

c pas tout à fait ca :  
 
tt les noeuds ont une durée...
la durée du projet maximum est bien évidemment la somme des durées des noeuds (mais c complètement pas efficace) ==> on fait des taches de manière concurrente. on va chercher à obtenir une durée réelle plus courte que la durée maximum, en jouant sur le fait qu'on peut faire plusieurs taches en même temps
 
Seulement, certaines taches ont des prérequis.
 
Donc tu cherches le chemin qui te permettra d'obtenir le temps le plus court global sur le projet : tt les noeuds ne sont pas inclus sur ce chemin, mais ces noeuds sont dit critique : tt allongement de la durée d'un de ces noeuds allonge la durée du projet
 
sinon oui : de toutes les séquences valides (cad qui complètent le projet), faut trouver la moins grave, sachant que tt les noeuds doivent etre positionnés sur le graph (même si tous n'appartiennent pas au chemin critique), et qu'il y a des contraintes :  
- la transitivité joue : si b dépend de a, et c de b, alors c dépend de b...ce qui se traduit par le fait que si c dépend de b et de a, et que b dépend de a aussi, il suffit de relier a à b, et b à c, sans relier a à c
- les noeuds ont tous une durée fixe, mais certains peuvent avoir des contraintes en plus : date de départ forcée, date d'arrivée forcée, recouvrement de tache, etc...
 
je voudrais me faire un truc qui calcule ca, mais g pas idée de l'algo a utiliser...peut etre aussi que je pourris le topic avec ma question...

Ton problème est très interessant en effet . Cependant je ne pense pas qu'il s'agit vraiment d'un problème de recherche de plus long chemin. Ton problème est purement un problème d'ordonnancement. Il s'agit de trouver le bon ordonnacement tout en satisfaisant un certain nombre de contraintes (par exemple qu'une tâche x soit réalisée avant une tâche y). A partir de l'ensemble des ordonnancements possibles (c'est à dire qui satisfont toutes les contraintes) il faut trouver celui dont la tâche ayant le plus long coût de calcul soit minimal (pour attendre le moins possible).
Une contrainte peut être :
- qu'une tâche s'execute seulement après une autre
- qu'une tâche doit impérativement se terminer avant telle date
- La contrainte qu'une tâche doit impérativement commencer avant telle date me semble pas pertinente : elle se résout automatiquement en fonction des 2 précédentes.
 
Par contre le prérequis est de connaître la durée des tâches
Je pense que tu peux carrément créer un nouveau sujet la dessus en explicitant bien tes données (ce que tu connais) et ce que tu cherches.
Ton problème ne se résume-t-il pas a "Sequential ordering problem (SOP)"
http://www.iwr.uni-heidelberg.de/g [...] /TSPLIB95/

Tu confonds graphe et arbre de solution. Deux choses totalement différentes.
 
Bon Giz, ma patience à des limites et le déroulement du topic converge vers ton ignorance et ta méprise de ceux qui peuvent t'apprendre des choses. Tu ne mérites même pas ma réponse. Regarde comme la nature est bien faite, je vais encore essayer, après de multiples tentatives, de te faire comprendre ton erreur.
 
On va citer Sedgewick, ton Dieu, peut être que ça t'ouvrira ton petit esprit. Attention, c'est ton Dieu qui parle, ce n'est plus moi.  
 
Algorithms in C++ Third Edition Part 5 Graph Algorithms.
Page 95, Proprety 18.3

 
Proprety 18.4 :

 
et un deux lignes plus loin :

 
En conclusion, tu es encore bien ignorant en algorithmique.  Commence par comprendre comment on parcourt un vecteur et revient nous voir quand tu auras compris ce qu'est un backtracking et un DFS. Prosterne toi devant tes maîtres et respectent-les. Pauvre fou, oser venir contredire sans réfléchir. Je pourrais t'ignorer pendant ton apprentissage, mais je suis plus sage que n'importe qui.

Jubijub, je parle ici d'un cas particulier (DAG et pas de poids).
 
Si tu souhaites le chemin Hamiltonien, c'est très facile. Si l'on trouve un chemin de longueur égale au nombre de sommet alors il s'agit d'un tel chemin. Dans le cas contraire, il n'existe pas.
 
PS: Cet algo n'a pas de nom, ce sont de bêtes déductions du tri topologique et des propriétés des DAGs.
 
Encore 2 petites citations de Sedgewick pour notre célèbre Giz :
 
Page 224 :

 
Et ce fameux exercice 19.114 à la page 201 :

 
J'ai résolu cet exercice pour toi, mon petit Giz.
 
D'un côté, je suis un peu décu j'aurais voulu que ce soit plus difficile de te trouver des preuves. Mais venant de ton Dieu, j'ose espérer que tu ne douteras plus un instant, de ma suprématie tout au long de ton topic. Maintenant, prosterne toi et je te pardonerai peut être de tes insultes à ma gentillesse.

je crois que j'ai confondu arbre de solution et graphe alors.   J'ai fais des recherches sur le net aussi et ils disent tous que le "longest path" se trouve en un temps lineaire etant donne un DAG.
 
Concretement, j'ai du mal a percevoir la chose. En fait c'etait pour resoudre Le pvc (voyageur de commerce) mais a l'inverse (trouver le chemin le plus long).
Comme le pvc est graphe a n noeuds et completement connecte, on peut trouve le chemin le plus long en un tps lineaire ? (je pense que c non mais si non, qu'est ce que tu apelles un trouver le chemin le plus long dans un tel graphe (pour avoir cette complexité linéaire) ?  
 
Pour le pvc, il suffirait de construire n arbres, l'un après l'autre, n étant le nombre de noeud dans le graphe. Chaque arbre aurait pour valeur racine un noeud parmi les n existant. Chaque arbre aurait bien une racine differente. Ou encore mieux, suffit de rajouter un noeud supplementaire qui serait racine et dont ses aretes en aval aurait pour cout 0. Ainsi pas besoin de construire n arbres mais un seul suffirait.
Ensuite tu crees ton tri topologique (tps lineaire) (mais ca, ca m'échappe le fait que tu ne vas pas parcourir tout l'arbre) et tu trouves le chemin le plus long. Bon et pour trouver le chemin le plus court, ben c'est un algo identique (tri topologique + calcul du chemin le plus court).
Y'a vraiment quelquechose qui m'échappe sur cette complexité linéaire que tout le monde dit  
 
EDIT : par contre je te trouve tres stupide (pour rester poli) dans tes remarques completement inutiles

Pour que ce soit TRES clair je reste toujours dans l'hypothèse d'un graphe E avec n noeuds completement connecte (c'est plus sport) dont chaque arete a un poids (bref comme le pvc quoi)

merci, je crée mon sujet...

En fait, non je me rends que le pvc contient toujours des cycles, ce n'est jamais un dag. Du coup la complexité linéaire qu'ils disent, ca vient du fait que le graphe est peu dense indirectement (du fait qu'il ne contient pas de cycle)  non ?  

Ben dans le pvc, tu peux aller de la ville A a la ville B tout autant que tu peux aller de la ville B a la ville A... Donc orienté ( dans le cas de pondérations différentes ) ou pas, y'aura toujours des cycles, non?

Si ton but c'est de résoudre le PVC, pourquoi ne te penches tu pas du coté des algorithmes génétiques ( a moins que ca ait déja été proposé? )

 
tout a fait, c'est pour ca que je dis qu'il y a toujours des cycles.
A la base, oui c'était pour trouver le plus long chemin dans le pvc. Et l'algo de mexx20 est linéaire donc j'essayais de voir si je pouvais l'appliquer au pvc. Mais en fait non (ca m'aurait bien étonné aussi   car si j'arriverais a le résoudre avec tri topo+calcul du plus long chemin en un tps lineaire alors je ferais pareil pour le calcul du plus court chemin   ).
J'ai donc essaié de voir où son programme "merdait" pour qu'il ne puisse pas s'appliquer au pvc. C'est en fait a cause des cycles et les recherches de chemin plus long/court qui necessite un DAG (graphe orienté sans cycle) et c'est cela qui implique que le graphe DAG est peu dense et donc que l'algo se resout en un temps linéaire parce que en faisant le tri topologique, tu parcours tout tes noeuds et toutes tes aretes (tout le graphe sans cycle en fait)).
Pour synthétiser, en fait le tri topologique reste un parcours entier du graphe (avec backtracking) => chaque noeud et arete sont parcouru. Alors maintenant le fait qu'on est sur que le graphe n'a pas de cycles implique que la complexité temporelle est moindre, c'est cela qu'appelle mexx20 un parcours de graphe. Alors que le pvc peut très bien se résoudre avec un DFS aussi mais là ce n'est plus un parcours de graphe mais d'arbre de solution (donc graphe avec cycles surtout) d'ou l'explosion du DFS en temps.
J'ai trouvé une très belle illustration du tri topologique :
http://ids.korea.ac.kr/classes/551 [...] opological Sorting.pdf
 
Pour la résolution du pvc après, ben c'est autre chose, c'est pas ce qui m'interesse dans ce topic (j'ai vite vu que pour trouver le plus court/long chemin dans le pvc c'est du NP-Complet)

Et c'est repartit, Giz revient en force. Tu craches trois fois la même erreur. Petits extraits :
 

 
Rien avoir avec du backtracking, tu n'as encore rien compris.
 

 
Non, c'est linéaire parceque c'est un DFS, rien à voir avec la densité du graphe. Ici on s'intéresse aux comportements asymptotiques, la densité ne change strictement rien. Retourne à tes maths.
 
J'ai aussi relevé une absurdité sur ta définition d'un DAG mais tu l'as corigée, c'est très bien. Bravo Giz. Il ne te reste plus qu'a éditer tout le reste.
 

Quoi tu en doutes encore ? J'éspère que oui, pour rigoler.
 

 
Je n'ai jamais dis que ca résoudrais ton problème du PVC, je suis venu glisser une petite note sur la solution linéaire pour les DAG. Ta mauvaise foi est immense, je t'adore Giz, c'est un plaisir de te répondre.

Aaah, tu as édité pour le redire une quatrième fois.  
 

 
Non, encore raté. Un DFS reste un DFS que ce soit un DAG ou pas, ca restera toujours LINEAIRE. Tu confonds toujours DFS et backtracking, graphe et arbre de solution.
 
J'éspère que tu le comprendras avant que l'on ai perdu contact avec Voyager II.
 
Je vais en rester là. Moi ça ne m'amuse plus.

Effectivement, j'ai confondu graphe et arbre de solution.
Un graphe representé par un arbre a une profondeur de 2 max.
la profondeur 0 (racine) est un noeud factice
la profondeur 1 sont tous les noeuds
la profondeur 2 sont toutes les relations.
 
alors que dans le pvc, ca va beaucoup plus profond (c'est un arbre de solution)
 
Parcourir un graphe avec un backtracking se fait en un tps linéaire car ca depend directement du nombre de noeuds/relations.
Parcourir un arbre de solution avec backtracking explose vite.
 
Quand au DFS c'est abstrait, ce n'est pas un algo en lui meme. Le backtracking est un algo qui utilise la méthode DFS pour lire l'arbre.
En fait avec ton DAG tu m'as embrouillé énormément   . Moi je raisonnais toujours sur l'arbre de solution du pvc (chercher le plus long chemin) et toi tu raisonnais sur un graphe (noeuds+relations) pour trouver le plus long chemin. Bref grosse confusion.
 
EDIT: par contre toi tu es vraiment le roi de l'esbrouffe ! A part critiquer, tu sais rien expliquer dans tes propos. Tu sais juste dire qu'un DFS c'est du linéaire, que backtracking c'est exhaustif...Si tu aurais cherche a le montre, on aurait vite vu qu'on était pas sur la meme longueur d'onde !   . Toi tu tournes autour du pot, moi je cherche la ou ca merde   .

Pourquoi ne pas remplacer tous les poids p sur chaque arete par N-p ou N est un nombre arbitraire plus grand que le plus grand poids puis appliquer Dijkstra.

 
marche pas !  
 
Bon si on déroule à la main voilà ce que ça donne...allez c'est parti
 
exemple d'arbre :
 

 
légende :
 
# : poids de l'arête
(#) : = N-# , avec N = 30 dans cet exemple
... : branches non explorées
# (en gras) : noeud/branche à développer à la prochaine instruction.
 
Selon toi, si on applique Djisktra, alors on développe en permanence la valeur entre parenthèse la plus petite.
Par conséquent, l'ordre des noeuds (= #) développés sont :
1) 30
2) ...puis 20
 
Or on voudrait que le 2ème noeud développé soit 15 car la branche "30 - 15" est celle qui contient le chemin le plus long (= 45) à ce stade de développement de l'arbre. Et si 20 est un noeud qui n'a pas de fils alors l'algo retourne le chemin constitué du seul noeud 20; ce qui est faux. Donc ça chie
 
voilà  

Oui effectivement ca marche pas...