Coût optimal du voyageur de commerce

[raphiol]

Bonjour,

Je suis en train d'étudier le problème du voyageur de commerce.

Rappel :
On considère l'ensemble [0,1]² dans lequel on dispose aléatoirement N villes de manière uniforme.
On ne connait pas a priori la disposition des villes dans le domaine.
On cherche le cycle le plus court qui relie toute les villes.

Ma question est : peut-on estimer (asymptotiquement) la longueur du cycle optimal lorsque N tend vers l'infinie ?
Si oui, comment le justifier ?

Je suis partit du principe que le cycle optimal pourrait s'estimer par quelque chose du style : (N+1) d(ville i, ville j).
Mais il faut du coup estimer les distances entre les villes... 1/sqrt(N) peut-être.

Bref, j'ai une vague idée du résultat, mais je n'ai pas de justification précise.
Pouvez-vous m'aider ?

Merci

[raphiol]

Personne ne saurait m'aider ?

[Dlzlogic]

Personne ne saurait m'aider ?

Bonjour,
Ce qui m'étonne dans votre énoncé est que "on dispose aléatoirement N villes de manière uniforme." Donc les villes sont disposées suivant les sommets d'un maillage triangulaire uniforme, donc équilatéral ou carré. Ce n'est pas habituel, mais bon ...
En fait, ce que je ne comprend pas c'est l'adjonction des termes "aléatoirement" et "uniforme". Géométriquement, c'est contradictoire. Par contre, cela pourrait être "aléatoirement sur un maillage uniforme", cela signifierait que après avoir visité la ville N(i) il doit se rendre à la ville N(i+1). Je ne sais pas si c'est l'énoncé du voyageur de commerce.
Ce type de problème se résout à l'aide de la théorie des graphes.
Donc, je peux pas vous aider.

[Sylviel]

@Dlzlogic : la terme aléatoirement uniforme signifie (a priori, car il n'est pas complètement clair énoncé ainsi) que l'on place chaque ville selon une loi uniforme sur [0,1]^2. C'est à dire que la probabilité que la ville se trouve dans une certaine surface A du carré est proportionnelle à son aire. Donc non ce n'est certainement pas sur un maillage uniforme...

@raphiol : je trouve la question intéressante, mais je ne vois pas de manière simple d'y répondre.

[Dlzlogic]

@Dlzlogic : la terme aléatoirement uniforme signifie (a priori, car il n'est pas complètement clair énoncé ainsi) que l'on place chaque ville selon une loi uniforme sur [0,1]^2. C'est à dire que la probabilité que la ville se trouve dans une certaine surface A du carré est proportionnelle à son aire. Donc non ce n'est certainement pas sur un maillage uniforme...

Pas facile de réaliser cela. Je ne vois qu'une seule méthode, réaliser un maillage carré (par exemple) et positionner une ville par sommet, avec un décalage aléatoire par rapport au sommet. Y aurait-il une autre solution ?

[fatal_error]

slt,

peut-on estimer (asymptotiquement) la longueur du cycle optimal

ca veut dire quoi asymptotiquement, avoir un ordre d'idée?
Dans ce cas là tu peux looker les mots clés "lower bound tsp" et "upper bound tsp".

Pas facile de réaliser cela

Code: Tout sélectionner

for i = 1:nbVilles
villes[i].x=randf(1);//retourne un float entre 0 et 1
villes[i].y=randf(1);
end

bref c'est immédiat!

[nodjim]

Ce qui est certain, c'est ce que ce trajet optimal se réalise sans croisement.

[Dlzlogic]

slt,


ca veut dire quoi asymptotiquement, avoir un ordre d'idée?
Dans ce cas là tu peux looker les mots clés "lower bound tsp" et "upper bound tsp".

Code: Tout sélectionner

for i = 1:nbVilles
villes[i].x=randf(1);//retourne un float entre 0 et 1
villes[i].y=randf(1);
end

bref c'est immédiat!

Je ne suis pas du tout sûr que les villes soient uniformément réparties
sur un carré de 100km sur 100 km.

Etude des positions X
Nombre = 100 MoyenneX = 0.25 emqX=30.76 epX=20.51
Classe 1 nb= 0 0.00% théorique 0.35%
Classe 2 nb= 0 0.00% théorique 2%
Classe 3 nb= 14 14.00% théorique 7%
Classe 4 nb= 15 15.00% théorique 16%
Classe 5 nb= 23 23.00% théorique 25%
Classe 6 nb= 14 14.00% théorique 25%
Classe 7 nb= 21 21.00% théorique 16%
Classe 8 nb= 13 13.00% théorique 7%
Classe 9 nb= 0 0.00% théorique 2%
Classe 10 nb= 0 0.00% théorique 0.35%
Etude des positions Y
Nombre = 100 MoyenneY = 249.74 emqY=28.16 epY=18.77
Classe 1 nb= 0 0.00% théorique 0.35%
Classe 2 nb= 0 0.00% théorique 2%
Classe 3 nb= 13 13.00% théorique 7%
Classe 4 nb= 16 16.00% théorique 16%
Classe 5 nb= 17 17.00% théorique 25%
Classe 6 nb= 24 24.00% théorique 25%
Classe 7 nb= 21 21.00% théorique 16%
Classe 8 nb= 9 9.00% théorique 7%
Classe 9 nb= 0 0.00% théorique 2%
Classe 10 nb= 0 0.00% théorique 0.35%

Code: Tout sélectionner

int main()
{
  float Xville[100];
  float Yville[100];
  int Compte=100;
  randomize();
  FILE *ecr=fopen("Villes.txt","wt");
  for (int i=0; i<Compte; i++)
  {
    Xville[i]=random(100)-50.0;
    Yville[i]=random(100)+200.0;
  }
  double SommeX = 0;
  double SommeY = 0;
  for (int i=0; i<Compte; i++)
  {
    SommeX += Xville[i];
    SommeY += Yville[i];
  }
  double MoyX=SommeX/100.;
  double MoyY=SommeY/100.;
  double emqX=0;
  double emqY=0;
  for (int i=0; i<Compte; i++)
  {
    double val = Xville[i]-MoyX;
    emqX += (val * val);
    val = Yville[i]-MoyY;
    emqY += (val * val);
  }
  emqX=emqX / ((float)Compte-1.);
  emqY=emqY / ((float)Compte-1.);
  emqX=sqrt(emqX);
  emqY=sqrt(emqY);
  double epX= emqX*2/3;
  double epY= emqY*2/3;
  int Classe[10];
  for (int i=0; i<10; i++) Classe[i]=0;
  fprintf(ecr," Etude des positions X\n");
  double ep=epX;
  for (int i=0; i<100; i++)
  {
    float val = Xville[i]-MoyX;
    if (val < -ep*4) Classe[0]++;
    else if (val < -ep*3) Classe[1]++;
    else if (val < -ep*2) Classe[2]++;
    else if (val < -ep)   Classe[3]++;
    else if (val < 0)    Classe[4]++;
    else if (val < ep)   Classe[5]++;
    else if (val < ep*2) Classe[6]++;
    else if (val < ep*3) Classe[7]++;
    else if (val < ep*4) Classe[8]++;
    else                 Classe[9]++;
  }
  fprintf(ecr,"Nombre = %d  MoyenneX = %0.2f  emqX=%0.2f  epX=%0.2f\n",Compte,MoyX,emqX,ep);
  fprintf(ecr,"Classe 1  nb=%4d  %0.2f%  théorique 0.35%\n",Classe[0], 100.*Classe[0]/Compte);
  fprintf(ecr,"Classe 2  nb=%4d  %0.2f%  théorique 2%\n",Classe[1], 100.*Classe[1]/Compte);
  fprintf(ecr,"Classe 3  nb=%4d  %0.2f%  théorique 7%\n",Classe[2], 100.*Classe[2]/Compte);
  fprintf(ecr,"Classe 4  nb=%4d  %0.2f%  théorique 16%\n",Classe[3], 100.*Classe[3]/Compte);
  fprintf(ecr,"Classe 5  nb=%4d  %0.2f%  théorique 25%\n",Classe[4], 100.*Classe[4]/Compte);
  fprintf(ecr,"Classe 6  nb=%4d  %0.2f%  théorique 25%\n",Classe[5], 100.*Classe[5]/Compte);
  fprintf(ecr,"Classe 7  nb=%4d  %0.2f%  théorique 16%\n",Classe[6], 100.*Classe[6]/Compte);
  fprintf(ecr,"Classe 8  nb=%4d  %0.2f%  théorique 7%\n",Classe[7], 100.*Classe[7]/Compte);
  fprintf(ecr,"Classe 9  nb=%4d  %0.2f%  théorique 2%\n",Classe[8], 100.*Classe[8]/Compte);
  fprintf(ecr,"Classe 10 nb=%4d  %0.2f%  théorique 0.35%\n",Classe[9], 100.*Classe[9]/Compte);

  for (int i=0; i<10; i++) Classe[i]=0;
  fprintf(ecr," Etude des positions Y\n");
  ep=epY;
  for (int i=0; i<100; i++)
  {
    float val = Yville[i]-MoyY;
    if (val < -ep*4) Classe[0]++;
    else if (val < -ep*3) Classe[1]++;
    else if (val < -ep*2) Classe[2]++;
    else if (val < -ep)   Classe[3]++;
    else if (val < 0)    Classe[4]++;
    else if (val < ep)   Classe[5]++;
    else if (val < ep*2) Classe[6]++;
    else if (val < ep*3) Classe[7]++;
    else if (val < ep*4) Classe[8]++;
    else                 Classe[9]++;
  }
  fprintf(ecr,"Nombre = %d  MoyenneY = %0.2f  emqY=%0.2f  epY=%0.2f\n",Compte,MoyY,emqY,ep);
  fprintf(ecr,"Classe 1  nb=%4d  %0.2f%  théorique 0.35%\n",Classe[0], 100.*Classe[0]/Compte);
  fprintf(ecr,"Classe 2  nb=%4d  %0.2f%  théorique 2%\n",Classe[1], 100.*Classe[1]/Compte);
  fprintf(ecr,"Classe 3  nb=%4d  %0.2f%  théorique 7%\n",Classe[2], 100.*Classe[2]/Compte);
  fprintf(ecr,"Classe 4  nb=%4d  %0.2f%  théorique 16%\n",Classe[3], 100.*Classe[3]/Compte);
  fprintf(ecr,"Classe 5  nb=%4d  %0.2f%  théorique 25%\n",Classe[4], 100.*Classe[4]/Compte);
  fprintf(ecr,"Classe 6  nb=%4d  %0.2f%  théorique 25%\n",Classe[5], 100.*Classe[5]/Compte);
  fprintf(ecr,"Classe 7  nb=%4d  %0.2f%  théorique 16%\n",Classe[6], 100.*Classe[6]/Compte);
  fprintf(ecr,"Classe 8  nb=%4d  %0.2f%  théorique 7%\n",Classe[7], 100.*Classe[7]/Compte);
  fprintf(ecr,"Classe 9  nb=%4d  %0.2f%  théorique 2%\n",Classe[8], 100.*Classe[8]/Compte);
  fprintf(ecr,"Classe 10 nb=%4d  %0.2f%  théorique 0.35%\n",Classe[9], 100.*Classe[9]/Compte);

  fclose(ecr);
  system("pause");
  return 0;
}


[fatal_error]

Ce que tu remets en cause, c'est la fonction random censée donner des nombres de manière uniforme. Si tu préfères tu prends un dé à 100 faces et tu le lances.

Mais au final on s'en fout un peu du procédé qui t'as filé les nombres. Simplement, tu sais que v(i,j) a autant de chance de sortir que v(y,z), i,j,y,z compris entre 0 et 1.

[Dlzlogic]

Ce que tu remets en cause, c'est la fonction random censée donner des nombres de manière uniforme. Si tu préfères tu prends un dé à 100 faces et tu le lances.

Mais au final on s'en fout un peu du procédé qui t'as filé les nombres. Simplement, tu sais que v(i,j) a autant de chance de sortir que v(y,z), i,j,y,z compris entre 0 et 1.

Mais tu sais très bien que ce que tu dis n'est pas vrai.
Fais une répartition régulière sans faire un quadrillage comme je l'ai indiqué, et on en reparle.
Quel que soit le moyen, les fléchettes, les cacas d'oiseaux ou tout ce que tu veux. Tu peux essayer le générateur dont on a parlé il y a quelques mois.
Pour l'instant, je dis que c'est pas si simple, et c'est tout.

[raphiol]

Oui, désolé si c'est un peu mal formulé : les villes sont disposées selon une loi uniforme sur [0,1]².
Ce que j’entends pas "asymptotiquement" c'est pour un nombre de ville très grand.

J'aimerai (par exemple) arriver à un résultat du type : cout(circuit optimal) ~ sqrt(N) quand N -> inf

Pour trouver, je m'était interrogé sur le cas où les villes sont toutes alignées selon une grille avec un truc du type :

[X,Y] = meshgrid(linspace(0,1,N), linspace(0,1,N));
X = reshape(X, 1, N*N);
Y = reshape(Y, 1, N*N);
Nv = N*N; % nombre de villes

Dans ce cas, le chemin optimal parcourt les Nv villes, avec une distance inter-ville de 1/(sqrt(N)-1), pour faire simple.
Et puisque qu'il revient à son point de départ, il fait Nv petite distance, soit un coût total de Nv/(sqrt(Nv)-1).

Donc asymptotiquement équivalent à sqrt(Nv).

Mais c'est vraiment un cas particulier.
Dans un cas général de villes disposées aléatoirement, je ne sais pas si on peut dire que la distance entre les villes (sur le circuit optimal) est toujours de l'ordre de 1/(sqrt(N)-1).

[Sylviel]

@Fatal error : je voulais dire pas facile de trouver une estimation, pas pas facile de le simuler ^^

@Dlzlogic : on ne vas pas repartir sur une discussion comme cela ou tu décides à toit tout seul que l'ensemble des probabilistes de la planète ont tort. Ton code est incompréhensible sans y passer des heures à le décortiquer (non commenté...). que sont tes classes ? d'où vient ton % théorique ? M'est avis que tu as encore voulu utiliser du gaussien à la place de l'uniforme... (effectivement : c'est bien le cas. ça devient blasant à la fin de toujours te répéter la même chose...)

@raphiol : regarde les mots clés "bound tsp", comme indiqué par Fatal error, tu trouveras des infos. Je ne connais pas les résultats sur le TSP. Tu dois pouvoir estimer la distance moyenne avec les 2 villes les plus proches, mais je ne sais pas si cela suffit une estimation du TSP.

J'ai scindé le reste de la discussion, qui a dérivé sur une autre sujet.