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.
Je sais que cette procédure ne marche pas. Donc j'attends que quelqu'un puisse m'aider à l'améliorer.
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
Merci beaucoup
Partager