Bonsoir a tous,

je suis actuellement sur le probleme du voyageur de commerce (en c++).
En resolution exacte, donc pas de colonie de fourmis, ni d'algo genetique....
Et mon prog ne depasse pas les 50 villes. J'aurais voulu savoir ce que je peut ameliorer :

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
27
28
29
30
31
 
Recurs (Solution Partial, int Minorant)
// Calcul du minorant de la matrice de coup
int Min = M.Normalize();
  Min += Minorant;
  if (Min > this->_best.GetCost())
    return ;
// Si dernier couple de ville
  if (Partial.GetStep() == M.GetSize())
    {
      Partial.SetCost(Min);
      if (this->_best.GetCost() > Partial.GetCost())
              this->_best = Partial;
    }
  else
    {
      Matrix M1(M);
      unsigned int X;
      unsigned int Y;
      Solution_Base Bis = Partial;
    // On prend le zero maximisant le minorant afin d'elaguer le plus tot possible
      if (M.GetEdgeMZ(&X, &Y) == false)
        return;
      M1.Left(X, Y);
      Partial.AddListItem(X, Y, M(X, Y));
      if (!Partial.IsCurrentGoodCycle(M.GetSize()))
        return ;
      this->Recurs(Partial, Min, M1);
      M.Right(X, Y);
      this->Recurs(Bis, Min, M);
    }
Avec ce code j'arrive a faire 50 villes en une seconde mais pas plus apres ca monte trop rapidement le temps...

Du coup quels ameliorations pourrais-je faire pour augmenter ce seuil ??

Merci d'avance.
Cordialement,
NeoKript