Bonjour,

je travaille dans le cadre de mes TIPE sur les algorithmes génétiques et je me suis attaqué au problème du voyageur de commerce (TSP).

En cherchant sur internet j'ai trouvé que la meilleure solution connue vaut 7542, je pense en avoir trouvé une dont le score est 7513, si certains sont motivés pour mettre ma solution à l'épreuve et me dire s'ils la valident, ce serait super !

Liste des villes: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/berlin52.tsp

Norme euclidienne utilisée (N = sqrt(x**2 + y **2))

Code source: https://github.com/abocquet/agenetique

Je met une screenshot de la sortie ci-dessous

Bonjour,

le plus simple pour vérifier est de calculer la longueur de ton chemin à la main … si effectivement tu as un meilleur score : bravo

Lu'!

Pas d'erreur d'arrondi ? J'ai cherché un peu sur internet, mais je trouve personne avec une preuve d'optimalité.

Bonjour, merci pour vos réponses 

effectivement je cast un double en int, ce qui doit faire sauter 50 fois les décimales d'où un score meilleurs d'environ 50

je referais les calculs dès que je peux 

@Ksass: "l'intérêt" du pvc avec 52 villes c'est que tu ne peux pas en temps raisonnable trouver un minimum de façon certaine (determinist)

Ouais mais en fait ton problème n'est qu'un sous-ensemble du voyageur de commerce vu que l'approximation géométrique est correcte par hypothèse. Donc je suis assez surpris que personne n'ait implémenté une version parallèle d'une solution exacte pour la faire tourner sur un gros cluster.

Voilà un lien, me souvenait bien qu'il y avait un truc du genre :

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms

Si les gens peuvent bourrer sur plus de 15000 villes avec un bon super-calculateur (voir plus de 80000 qui est le record), je ne vois pas de raison qu'on puisse pas bourrer sur une cinquantaine avec un petit cluster voir même une machine assez balaise .