IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Voyageur de commerce : comparatif de différents algorithmes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2017
    Messages : 7
    Par défaut 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é)

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2008
    Messages
    26 772
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Août 2008
    Messages : 26 772
    Par défaut


    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.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2017
    Messages : 7
    Par défaut
    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 !

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2008
    Messages
    26 772
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Août 2008
    Messages : 26 772
    Par défaut
    Citation Envoyé par Lupa99 Voir le message
    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).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. Algorithme du Voyageur de Commerce ou TSP en FORTRAN
    Par MINOTE dans le forum Fortran
    Réponses: 0
    Dernier message: 20/12/2009, 10h30
  2. Voyageur de commerce & algorithme glouton
    Par tagsOf dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 27/11/2009, 22h15
  3. Algorithme génétique et probleme de voyageur de commerce avec graphe non complet
    Par marmarnassouf dans le forum Intelligence artificielle
    Réponses: 2
    Dernier message: 30/04/2009, 16h51
  4. Réponses: 2
    Dernier message: 03/02/2009, 20h21
  5. Application d'un algorithme génétique au voyageur de commerce
    Par khayyam90 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 11/12/2008, 14h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo