program nm;                           (* Nearest Merger, Thomas Klein  1999 *)
{$M 65520,0,655360}                         (* max. Stackgroesse *)
uses graph,tsp,maus;

procedure nmerge(var w:weg);
 (* Nearest Merger *)
 var i,j,k,l,n,i1,j1,i2,j2,k2,l2:stadtnr;
     m,min:entfernung;
     subweg:array[1..maxstadt] of weg;
 begin
  for i:=1 to stadtanzahl do subweg[i]:=chr(i)+chr(i);
  n:=stadtanzahl;
  while n>1 do begin
   (* zusammenzulegende Wege(i1,j1) bestimmen *)
   min:=maxentfernung;
   for i:=1 to stadtanzahl do
    for j:=1 to stadtanzahl do
     if i<>j then
      for k:=2 to length(subweg[i]) do
       for l:=2 to length(subweg[j]) do begin
        m:=entftab[ord(subweg[i][k]),ord(subweg[j][l])];
        if m<min then begin min:=m; i1:=i; j1:=j; end;
       end;
   (* zu aendernde Kanten ermitteln *)
   min:=maxentfernung;
   for i:=2 to length(subweg[i1]) do
    for j:=2 to length(subweg[j1]) do begin
     i2:=ord(subweg[i1][i-1]); j2:=ord(subweg[i1][i]);
     k2:=ord(subweg[j1][j-1]); l2:=ord(subweg[j1][j]);
     m:=entftab[i2,l2]+entftab[k2,j2]-entftab[i2,j2]-entftab[k2,l2];
     if m<min then begin min:=m; k:=i; l:=j; end;
    end;
   (* Wege zusammenlegen *)
   insert(copy(subweg[j1],l,length(subweg[j1])-l)+copy(subweg[j1],1,l-1)
          ,subweg[i1],k);
   subweg[j1]:=''; dec(n);
  end;
  w:=subweg[i1];
 end;

begin
 if tspinit('TSP: Nearest Merger','Berechnen') then
  while tspmenue([0..255]) do begin
   start; nmerge(aktuell); stop;
   wegkarte(aktuell,true,brown,yellow);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.