Discussion :

[Mus54Ep]

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

[CliffeCSTL]

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

[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

[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

[bacelar]

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.

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

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 ?

[darkman19320]

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