Problème de voyageur de commerce (méthode gloutonne)

-
Bonjour,
Voilà donc mon problème:
Le problème du voyageur de commerce (Traveling Salesman Problem) qui doit visiter toutes les villes, en passant par chaque ville exactement une fois, où résident ses clients et retourner à son point de départ en minimisant la distance parcourue.
Supposons qu'il y ait n villes et que le problème soit symétrique (c est à-dire que le coût pour aller de la ville A à la ville B est égal a celui pour aller de la ville B à la ville A).
Le problème consiste donc à trouver un cycle que peut traverser un commerçant pour livrer sa marchandise à tous les clients situés à n villes différentes, de longueur totale minimale qui passe exactement une fois par chaque point et revenir au point de départ, en un temps réalisable.

Le critère glouton que j'ai défini, c'est de choisir, à chaque fois la ville la plus proche de la ville courante.
J'ai écrit le code source comme suit :
Un matrice de poids M[i][j] (contient le poids entre la ville i et la ville j)
J'ai développé la fonction suivante:
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

Cette fonction ne marche pas pour le moment, c'est pour cela que je me demande si quelqu'un peut m'aider à détecter les erreurs et à les corriger.
Cordialement
Afficher la suite