program a_maxosni; (* Max-OSN-Insert. mit Startpunktwahl, Thomas Klein  1999 *)
uses graph,tsp;
var anfang:stadtnr;

procedure maxosni(anfang:stadtnr;var w:weg);
 (* Maximum-OSN-Insertion mit Startpunkt anfang *)
 var m,n,i,j:stadtnr;
     mm,l:real;
 begin
  w:=chr(anfang)+chr(anfang);
  while length(w)<=stadtanzahl do begin
   mm:=-maxentfernung;
   for i:=2 to length(w) do begin
    m:=ord(w[i]);
    for j:=1 to stadtanzahl do
     if pos(chr(j),w)=0 then begin
      if length(w)=2 then
       l:=entftab[m,j]
      else
       l:=entftab[m,j]/entftab[j,anfang];
      if l>mm then begin mm:=l; n:=j; end;
     end;
   end;
   mm:=maxentfernung;
   for i:=2 to length(w) do begin
    l:=entftab[ord(w[i-1]),n]+entftab[n,ord(w[i])]
       -entftab[ord(w[i-1]),ord(w[i])];
    if l<mm then begin mm:=l; m:=i; end;
   end;
   insert(chr(n),w,m);
  end;
 end;

function auto_maxosni(var mweg:weg):stadtnr;
 (* automatische Bestimmung des besten Startpunktes *)
 var i,anfang:stadtnr;
     m,l:entfernung;
     w:weg;
 begin
  m:=maxentfernung;
  for i:=1 to stadtanzahl do begin
   maxosni(i,w); l:=weglaenge(w);
   if l<m then begin m:=l; mweg:=w; anfang:=i; end;
  end;
  auto_maxosni:=anfang;
 end;

begin
 if tspinit('TSP: Maximum-OSN-Insertion mit Startpunktwahl','Berechnen') then
  while tspmenue([0..255]) do begin
   start; anfang:=auto_maxosni(aktuell); stop;
   wegkarte(aktuell,true,brown,yellow); farbstadt(anfang,white);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.