|
Page : 1 2 Page Précédente | |
Auteur | Sujet : [algo] Recherche du plus long chemin |
Giz | 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 Message édité par Giz le 02-06-2004 à 19:51:13 |
Publicité | Posté le 02-06-2004 à 19:44:09 |
Ace17 | La recherche du plus long chemin??? Est-ce que t'es sur qu'il existe? |
R3g fonctionnaire certifié ITIL | A priori, le chemin le plus long est infiniment long... ca va être dur à calculer... --------------- Au royaume des sourds, les borgnes sont sourds. |
Ace17 | Le chemin le plus long d'un point a un autre....
|
black_lord Truth speaks from peacefulness |
|
Ace17 |
Giz |
|
christophe_d13 L'efficacité à tout prix. | Pour le plus long chemin...
|
Publicité | Posté le 03-06-2004 à 11:31:17 |
Ace17 |
|
Giz |
Message édité par Giz le 03-06-2004 à 13:25:18 |
Giz |
Ace17 |
|
KneXtasY | Algorithme de Bellman modifié ? ( mais bon si ya un cycle c'est mort. )
Message édité par KneXtasY le 23-07-2004 à 09:06:58 |
Taz bisounours-codeur | 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 ? |
Ace17 |
Ben de toutes facons si y'a un cycle le plus long chemin n'existe pas... |
Giz | 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 |
Ace17 | Ca revient au meme que si ton graphe est complet... je me trompe? Message édité par Ace17 le 23-07-2004 à 16:39:04 |
Giz |
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 |
bobuse | 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 ? |
Giz |
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 |
mexx20 | Hello,
|
Giz |
--------------- 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 |
mexx20 | 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.
|
mexx20 | 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
|
mexx20 | 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. |
Giz | 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)).
--------------- 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 |
mexx20 | Bon apparement tu n'as pas bien compris.
|
mexx20 | 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. |
mexx20 | En fait c'est meme tres réducteur
|
Giz |
--------------- 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 |
mexx20 | Heu... pas efficace ? V^2 ou V+E ... :-|
|
mexx20 | 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.
|
mexx20 | C'est pas efficace, d'accord, c'est optimal |
Giz |
--------------- 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 |
mexx20 | "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 ... "
|
mexx20 | Pour la complexité du DFS, je maintient ce que j'ai dis. Elle est moindre que celle d'un backtracking (recherche exhaustive). |
Giz | 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.
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 |
mexx20 | Non, je ne parcours pas tout l'arbre, je ne fais qu'un tri topologique avec un DFS.
Message édité par mexx20 le 11-08-2004 à 15:10:47 |
Publicité | Posté le |
Page : 1 2 Page Précédente |
Sujets relatifs | |
---|---|
[c]Code format d'un double %f ou %lf ? Ou avoir + d'info sur long? | Recherche correpondance SQL Server / Oracle |
Recherche d'un outil de reporting | [Algo] Formulaire HTML ou intégré à l'appli ? |
[ALGO] Afficher un arbre de manière optimale | Algo cycle de graph |
comportement bizzare avec complilo gcc, chemin relatif/absolu | recherche info sur les styles pour netscape 4 |
Recherche info sur les lecteurs de code barre | recherche et remplacement dans le fichier meme |
Plus de sujets relatifs à : [algo] Recherche du plus long chemin |