Discussion :

[souviron34]

et ca revient au même que l'algo que tu dis je pense

Non, car ton point de référence est pris au hasard, et donc tu n'as aucun moyen de savoir comment parcourir les autres. La seule chose que tu auras c'est un classement en distance.

L'algo dont je parlais les arrange par angle par rapport à un point extrême (voir figure), et donc tu as un vrai parcours direct.

Par contre, ce n'est pas forcément le parcours le plus court... ( Si le 3ième point par exemple est très proche du point de référence, c'est un peu comme si tu faisais un AR vers le point de référence.)

Mais on a toujours pas l'information de savoir si tu veux passer par tous les points tout court, ou si en plus c'est par le chemin le plus court....

Et la réference de pseudocode est bonne également, pour le chemin le plus court...

[hugobosscool26]

Non, car ton point de référence est pris au hasard, et donc tu n'as aucun moyen de savoir comment parcourir les autres. La seule chose que tu auras c'est un classement en distance.

Mais on a toujours pas l'information de savoir si tu veux passer par tous les points tout court, ou si en plus c'est par le chemin le plus court....

Alors pour la 1ère partie oui je viens de m'en rendre compte et en faite j'applique d'abord la seconde méthode puis la 1ére que j'ai énoncé! enfin je vais tester.



Pour la seconde chose, je voudrais les 2 bien sur

[jobherzt]

jobherzt:

Le problème du voyageur de commerce consiste, étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les villes.




Ca correspond tout à fait à ce que je veux !

merci, je sais ce que c'est que le probleme du voyageur de commerce seulement c'etait tres loin d'etre clair dans ton premier post.

sache que dans le cas particulier ou le graphe est euclidien (cad, en appelant d la distance, si pour tout point A,B,C, d(A,C) <= d(A,B)+d(B,C) ), il existe un algorithme assez "naif" qui te donne un resultat inferieur a 2 fois la distance la plus courte.

sinon, l'idee generale est d'utiliser une grosse heuristique (comme un algorithme genetique) qui fait le travail "de fond", couplé a une optimisation locale (comme une 2-optimisation) qui accelere le boulot.
Dans le cas general (ie pas forcement euclidien), mefie toi du plus proche voisin et de la strategie gloutonne : on peut construire des graphes tels qu'ils retournent le chemin le plus long !! donc il existe des cas ou le resultat qu'ils donnent est vraiment mauvais.

[hugobosscool26]

Oki doki

je vais tester ca pr l'instant:

http://labo.algo.free.fr/pvc/algorit...s_voisins.html

[tomtom7]

Salut,
J'avais fait ça avec l'algo de Mole&Jameson (qui est une sorte d'algo de meilleure insertion). Ensuite je passais un algo 2-Opt pour améliorer la solution. Ca peut être rapide avec 2-3 modifs de bon sens et les résultats étaient très bons.