void anneal(float x[], float y[], int iorder[], int ncity)
This algorithm finds the shortest round-trip path to ncity cities whose coordinates are in the
arrays x[1..ncity],y[1..ncity]. The array iorder[1..ncity] specifies the order in
which the cities are visited. On input, the elements of iorder may be set to any permutation
of the numbers 1 to ncity. This routine will return the best alternative path it can find.
{
int irbit1(unsigned long *iseed);
int metrop(float de, float t);
float ran3(long *idum);
float revcst(float x[], float y[], int iorder[], int ncity, int n[]);
void reverse(int iorder[], int ncity, int n[]);
float trncst(float x[], float y[], int iorder[], int ncity, int n[]);
void trnspt(int iorder[], int ncity, int n[]);
int ans,nover,nlimit,i1,i2;
int i,j,k,nsucc,nn,idec;
static int n[7];
long idum;
unsigned long iseed;
float path,de,t;
nover=100*ncity; Maximum number of paths tried at any temperature.
nlimit=10*ncity; Maximum number of successful path changes before con-
path=0.0; tinuing.
t=0.5;
for (i=1;i<ncity;i++) { Calculate initial path length.
i1=iorder[i];
i2=iorder[i+1];
path += ALEN(x[i1],x[i2],y[i1],y[i2]);
}
i1=iorder[ncity]; Close the loop by tying path ends together.
i2=iorder[1];
path += ALEN(x[i1],x[i2],y[i1],y[i2]);
idum = -1;
iseed=111;
for (j=1;j<=100;j++) { Try up to 100 temperature steps.
nsucc=0;
for (k=1;k<=nover;k++) {
do {
n[1]=1+(int) (ncity*ran3(&idum)); Choose beginning of segment
n[2]=1+(int) ((ncity-1)*ran3(&idum)); ..and end of segment. ..
if (n[2] >= n[1]) ++n[2];
nn=1+((n[1]-n[2]+ncity-1) % ncity); nn is the number of cities
} while (nn<3); not on the segment.
idec=irbit1(&iseed);
Decide whether to do a segment reversal or transport.
if (idec == 0) { Do a transport.
n[3]=n[2]+(int) (abs(nn-2)*ran3(&idum))+1;
n[3]=1+((n[3]-1) % ncity);
Transport to a location not on the path.
de=trncst(x,y,iorder,ncity,n); Calculate cost.
ans=metrop(de,t); Consult the oracle.
if (ans) {
++nsucc;
path += de;
trnspt(iorder,ncity,n); Carry out the transport.
}
} else { Do a path reversal.
de=revcst(x,y,iorder,ncity,n); Calculate cost.
ans=metrop(de,t);
if (ans) {
++nsucc;
path += de;
reverse(iorder,ncity,n); Carry out the reversal.
}
}
if (nsucc >= nlimit) break; Finish early if we have enough suc-
} cessful changes.
printf("\n %s %10.6f %s %12.6f \n","T =",t,
" Path Length =",path);
printf("Successful Moves: %6d\n",nsucc);
t *= TFACTR; Annealing schedule.
if (nsucc == 0) return; If no success, we are done.
}
}