function [v,dist] = initialise(nv)
//     Tire les coordonnees de nb villes au hasard dans 
//     le carre unite. Calcule la matrice des distances. 

v = rand(nv,2);          // coordonnees
                         // matrice des distances
dist = (v(:,1)*ones(1,nv)-ones(nv,1)*(v(:,1))').^2;
dist = dist + (v(:,2)*ones(1,nv)-ones(nv,1)*(v(:,2))').^2;
dist = sqrt(dist);

function trace_parcours(villes)
//      Represente les villes et le circuit dans le 
//      carre unite.

v = [villes;villes(1,:)];
xbasc(); square(0,0,1,1);
plotframe([0,0,1,1],[0,1,0,1],[%f,%f]);
plot2d(v(:,1),v(:,2),1,"000");
xset("mark",-9,4);
plot2d(villes(:,1),villes(:,2),-9,"000");

function e=f(ordre)
//     fonction d'energie : somme des distances du
//     circuit dans l'ordre donne en entree.

e = sum(diag(distances(ordre,..
        [ordre($),ordre([1:size(ordre,"*")])])));

function o=permuter(ordre)
//     Permute 5 indices consecutifs d'un vecteur d'ordre

v = grand(1,1,"uin",1,nv);            // indice de depart
o = ordre;                            // ordre initial
if v>1 then,                          // decalage
  o = o([[v:nv],[1:v-1]]);
end;
o5=grand(1,"prm",[1:5]');             // permutation
o([1:5])=o(o5');                      // ordre modifie 


function [o,e] = recuit(ordre,h,unsurT)
//     Simule nbre pas de l'algorithme de recuit simule
//     pour le probleme du voyageur de commerce.
//     Retourne le nouvel ordre et le vecteur des valeurs
//     successives de la fonction f.

o = ordre;
f1 = f(o);
e=[f1];
n = 0;
for ut = 1:unsurT,
  palier = int(exp(ut*h));
  while n<palier,
     o2 = permuter(o);
     f2 = f(o2);
     if f2<f1 then,
       o = o2;
       f1 = f2;
     else
       p = exp((f1-f2)*ut);
       if rand(1,1)<p then,
          o = o2;
          f1 = f2;
       end; 
     end;
     e = [e,f1];
     n = n+1;
  end;
end;       




