Voyageur de commerce : comparatif de différents algorithmes

Bonjour,

Dans le cadre d'un projet étudiant, j'ai codé en Python un petit script pour résoudre le problème du voyageur de commerce avec la méthode du recuit simulé.
Cependant, pour pouvoir conclure quand à l'efficacité de mon implémentation, j'aurais aimé comparer mes résultats à d'autres méthodes (par exemple Lin Kernighan). Je n'ai pas le temps d'implémenter d'autre méthode, l'échéance du projet étant assez proche.

C'est pourquoi j'aurais besoin d'une petite aide.

J'ai pour l'instant utilisé http://labo.algo.free.fr/defi250/def...50_villes.html qui donne un fichier de 250 villes à traiter, avec le score optimal (la longueur minimale du parcours).

Pour faire un comparatif pertinent, il faudrait que je fasse tourner plusieurs algorithmes sur la même machine et avec le même langage (Python).

- Avez vous déjà implémenté un algorithme pour résoudre le problème du voyageur de commerce ? Si c'est le cas, j'aimerais bien comparer ma méthode à la votre avec la liste du lien précédent. Pour que ce soit un vrai comparatif, j'aurais besoin de le lancer sur ma machine (pour comparer à puissance égale) ; donc si vous avez la possibilité de me partager votre programme avec déjà "le défi des 250 villes" de chargé, ça serait super.

Sinon, peut-être que vous avez d'autres idées pour que je puisse mener à bien mon comparatif ?

Je vous remercie par avance !

(J'ai hésité à poster dans Python, dites moi si ici ce n'était pas adapté)

:salut:

Tu pourrais reprendre des implémentations existantes, genre Concorde http://www.math.uwaterloo.ca/tsp/concorde.html (de mémoire, ça implémente une variante de Lin-Kernighan). Sinon, OR-Tools a des trucs pour le TSP, mais je n'ai aucune idée de ce qui se cache derrière (leur propre solveur MIP ?) https://developers.google.com/optimization/routing/tsp.

Merci pour votre réponse !

C'est une bonne idée !
Cependant, j'ai une petite question. Sachant que ce n'est surement pas codé en python, et que c'est sûrement optimisé un maximum, c'est peut être un peu inégal pour comparer l'algorithme en lui même, non ?
Est-ce qu'il y a un facteur par lequel je pourrais multiplier le temps de mon algorithme pour obtenir un temps qui correspondrait à un "produit fini" comme Concorde ? (un temps par exemple qui correspondrait plus à ce que donnerait l'algo implémenté en C et compilé par exemple ?)

Mais déjà c'est pas mal, ça me fait déjà un point de comparaison !

Citation:

---

Envoyé par Lupa99

Est-ce qu'il y a un facteur par lequel je pourrais multiplier le temps de mon algorithme pour obtenir un temps qui correspondrait à un "produit fini" comme Concorde ? (un temps par exemple qui correspondrait plus à ce que donnerait l'algo implémenté en C et compilé par exemple ?)

---

Pas vraiment : ça dépend fortement du type de code implémenté… Et un code Python bien réfléchi peut atteindre la même performance qu'un code C ou C++ bien réfléchi aussi (par exemple, pour l'implémentation des arbres de décision dans scikit-learn). Maintenant, le plus intéressant, c'est de voir comment les temps d'exécution évoluent quand ton instance change : là, tu pourras voir les augmentations de temps de calcul (qui, elles, seront comparables).