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