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

Version imprimable

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:

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

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:

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) {
    [...]
}

28/12/2014, 11h49
Mus54Ep

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
17/12/2015, 03h27
marwa-mareghni

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 :)
17/12/2015, 10h46
bacelar

Citation:

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. :ptdr:
Problème NP-Complet, si tu veux te renseigner sur les bases mathématique du bidule.
17/12/2015, 11h11
Iradrille

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

Bin, si tu le trouves et tu prouves que c'est le meilleur algorithme, t'aura au moins la médaille Fields, au minimum. :ptdr:
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 ?
17/12/2015, 17h42
darkman19320

Citation:

Envoyé par Iradrille

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...