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

C++ Discussion :

Implémenter l'algorithme glouton (voyageur de commerce)


Sujet :

C++

  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2014
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Décembre 2014
    Messages : 21
    Par défaut Implémenter l'algorithme glouton (voyageur de commerce)
    Bonjour,
    Et bien je vais expliquer brièvement ce problème:
    Un commerçant doit livrer sa marchandise à n villes. Il ne doit passer par une ville qu'une seule fois et finit par revenir à la ville de départ.
    L'algorithme glouton doit respecter la philosophie suivante:
    A chaque fois qu'il veut passer à une ville, il doit choisir la ville la plus proche de la ville courante.
    Cet algorithme ne donne pas forcément une solution optimale. Mais bien tant qu'on m'a précisé cette méthode.
    Voilà donc la procédure que j'ai définie afin de concrétiser le principe de cette méthode.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     
    void VoyageurDeCommerce(double **x, int vd, int n, vector<int> &chemin, double &pp)
    {
     bool *estVisite= new bool[n]; 
     for (int i = 0; i < n; i++)
      estVisite[i] = false;
     estVisite[vd] = true;
     double meilleur = x[i][0];
     int mc=0;
     for (int k = 0; k < n; k++)
     if ((x[vd][k] < meilleur) && (i != k) && (estVisite[k] == false))
     {
      mc = k;
      pp = pp + x[vd][k];
      chemin.push_back(mc);
     }
     VoyageurDeCommerce(x, mc, n, chemin, pp);
     
    }
     
    //estVisite[i]: indique si une ville i est visitée ou pas
    double**x: La matrice des poids
    int vd: la ville de départ
    int n: Le nombre de villes
    chemin: un tableau qui contient (à la fin) toutes les villes à visiter en ordre
    pp: le poid (la distance) du chemin
    Je sais que cette procédure ne marche pas. Donc j'attends que quelqu'un puisse m'aider à l'améliorer.
    Merci beaucoup

  2. #2
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2012
    Messages
    538
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2012
    Messages : 538
    Par défaut
    1. Le voyageur de commerce est un pb connu, donc pas la peine de l'expliquer ici.
    2. Glouton n'est pas un algorithme.
    3. Tu essayes de coder l'algorithme de plus proche voisin.

    Voila pour t'aider un début d'algo :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    n // Nombre de villes
    d // Matrice des distances ou d[i][j] correspond à la distance entre les villes i et j
    bool visit[n] = { false; } // True si une ville fait partie de la solution
     
    std::vector<int> plus_proche_voisin() {
        std::vector<int> res;    // résultat
        res.push_back(0); visit[0]= true;
        while(res.size() != n)
            res.push_back(best_neighbor(res.last()));
        return res;
    }
     
    // Retourne le voisin non visité le plus proche de v
    int best_neighbor(int v) {
        [...]
    }

  3. #3
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2014
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Décembre 2014
    Messages : 21
    Par défaut
    Bonjour,
    Monsieur, je n'ai pas expliqué le problème de voyageur de commerce. J'ai plutôt expliqué la méthode que je dois utiliser pour le résoudre (car il existe plusieurs méthodes).
    Sinon, votre proposition m'a beaucoup aidé. Donc, je voudrais vous remercier infiniment pour votre aide.
    Salut

  4. #4
    Invité de passage
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 30
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Décembre 2015
    Messages : 1
    Par défaut
    bonsoir j ai un projet sur le voyageur de commerce je veux savoir c 'est quoi le meilleur algorithme et le plus simple pour l utiliser a résoudre ce problème avec l implémentation merci d avance

  5. #5
    Expert confirmé
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 479
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 479
    Par défaut
    bonsoir j ai un projet sur le voyageur de commerce je veux savoir c 'est quoi le meilleur algorithme et le plus simple pour l utiliser a résoudre ce problème avec l implémentation merci d avance
    Bin, si tu le trouves et tu prouves que c'est le meilleur algorithme, t'aura au moins la médaille Fields, au minimum.
    Problème NP-Complet, si tu veux te renseigner sur les bases mathématique du bidule.

  6. #6
    Membre Expert
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Par défaut
    J'avais eu un projet similaire en cours (pas exactement de voyageur de commerce, mais un problème NP-complet proche).

    On nous à très fortement orienté vers des algos tabou / génétique (au choix). Bien sympa comme projet.

    J'ai personnellement utilisé un algo tabou, mais les 2 algos donnent de bons résultats.

    Citation Envoyé par bacelar Voir le message
    Bin, si tu le trouves et tu prouves que c'est le meilleur algorithme, t'aura au moins la médaille Fields, au minimum.
    Problème NP-Complet, si tu veux te renseigner sur les bases mathématique du bidule.
    Ce n'est pas prouvé qu'une recherche exhaustive (i.e. bruteforce) est la seule façon de trouver LA meilleure solution ?

  7. #7
    Membre éclairé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2010
    Messages
    517
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Santé

    Informations forums :
    Inscription : Avril 2010
    Messages : 517
    Par défaut
    Citation Envoyé par Iradrille Voir le message
    Ce n'est pas prouvé qu'une recherche exhaustive (i.e. bruteforce) est la seule façon de trouver LA meilleure solution ?
    Il y a d'autres méthodes pour trouver "la" meilleur solution d'un problème NP-complet: c'est le but de tous les mathématiciens qui bossent dans la recherche opérationnelle (optimisation combinatoire...). Tu peux chercher quelques algo style Branch and Bound, Branch and Cut etc...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme du voyageur de commerce
    Par Invité dans le forum R
    Réponses: 3
    Dernier message: 02/04/2014, 18h21
  2. Algorithme du Voyageur de Commerce ou TSP en FORTRAN
    Par MINOTE dans le forum Fortran
    Réponses: 0
    Dernier message: 20/12/2009, 10h30
  3. 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
  4. Réponses: 2
    Dernier message: 03/02/2009, 20h21
  5. Voyageur de commerce
    Par senke dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 27/09/2002, 12h51

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