program p_simann;                  (* Simulated Annealing, Thomas Klein 1999 *)
 (* Grundlage: T. Otto: Reiselust, c't 1/94, Verlag Heinz Heise, 1993 *)
uses graph,tsp;

function ktausch(i,j:stadtnr;w:weg):weg;
 (* Zweikantentausch mit Schnitten nach i,j *)
 var k,k1,l1:stadtnr;
     hilf:char;
 begin
  for k:=1 to ((j-i+stadtanzahl) mod stadtanzahl) div 2 do begin
   k1:=1+(i+k-1+stadtanzahl) mod stadtanzahl;
   l1:=1+(j-k+stadtanzahl) mod stadtanzahl;
   hilf:=w[k1]; w[k1]:=w[l1]; w[l1]:=hilf;
  end;
  w[stadtanzahl+1]:=w[1];
  ktausch:=w;
 end;

procedure simann(var mweg:weg);
 (* Postoptimierung mit Zweikantentausch/Simulated Annealing *)
 var i,j,abstand:stadtnr;
     m,l:entfernung;
     w:weg;
     temp:real;
     versuche,tausche:word;
 function e(r:real):real;
  (* modifizierte exp-Funktion *)
  begin
   if r<-88 then e:=0 else   (* underflow abfangen *)
    if r>0 then e:=2 else    (* wg. vgl. mit [0..1] ausreichend *)
     e:=exp(r);
  end;
 begin
  temp:=1;
  for i:=1 to stadtanzahl do
   for j:=1 to stadtanzahl do
    if entftab[i,j]>temp then temp:=entftab[i,j];
  m:=weglaenge(mweg);
  repeat
   versuche:=0; tausche:=0;
   repeat
    inc(versuche);
    repeat
     i:=random(stadtanzahl)+1; j:=random(stadtanzahl)+1;
     abstand:=(j-i+stadtanzahl) mod stadtanzahl;
    until (abstand>=2) and (abstand<stadtanzahl-2);
    (* mind. 2 Staedte aendern/nicht aendern *)
    w:=ktausch(i,j,mweg); l:=weglaenge(w);
    if (l<m) or (random<e((m-l)/1000/temp)) then begin
     m:=l; mweg:=w; inc(tausche);
    end;
   until (versuche=stadtanzahl*100) or (tausche=stadtanzahl*10);
   temp:=temp*0.9;
  until tausche=0;
 end;

begin
 if tspinit('TSP: Simulated Annealing','Berechnen') then
  while tspmenue([113]) do begin
   start; simann(aktuell); stop;
   wegkarte(aktuell,true,brown,yellow);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.