program p_ktausch1; (* Zweikantentausch 1(steilster Abstieg), T. Klein 1999 *)
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 ktausch1(var mweg:weg);
 (* Postoptimierung mit Zweikantentausch/steilster Abstieg *)
 var i,j:stadtnr;
     m,l:entfernung;
     w,t:weg;
     tausch:boolean;
 begin
  m:=weglaenge(mweg);
  repeat
   tausch:=false;
   for i:=1 to stadtanzahl do
    for j:=1 to stadtanzahl do begin
     w:=ktausch(i,j,mweg);
     l:=weglaenge(w);
     if l<m then begin m:=l; t:=w; tausch:=true; end;
    end;
   if tausch then mweg:=t;
  until not tausch;
 end;

begin
 if tspinit('TSP: Zweikantentausch 1(steilster Abstieg)','Berechnen') then
  while tspmenue([113]) do begin
   start; ktausch1(aktuell); stop;
   wegkarte(aktuell,true,brown,yellow);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.