(*                                         2-Opt TSP Algorithm

        INPUT   :      The associated datafile is "TwooptDatafile".
                         1st number represents # of nodes in teh given network.\

                         2nd set of  numbers represents an NxN mweight matrix o\
f the given 
                         network.
                         3rd set of numbers represents the initial TS route.  T\
his may obtain from
                         the FITSP algorithm.  (See fitsp.p program)

        Output   :       Outputs of  2-Opt TSP Algorithm are
                         1. The final route of TSP.
                         2. Total weight of the final route.
        Algorithm   :   The 2-opt TSP algorithm finds an approximate solution o\
f the "symmetric"
                          traveling salesman problem with N nodes, given as an \
NxN weight
                          matrix W of integers.  The algorithm starts with the \
initial route which 
                          is provided by users.  One may obtain the initial rou\
te from  FITSP 
                          algorithm.  Then the algorithm improves the tour repe\
atedly by 
                          exchange two edges at a time.  The edges exchange con\
tinues until no better.
                          solution      can be found.
        Note :             The choice of the route (Hamiltonian cycle) can have\
 the most dramatic
                           impact on the final solution.  Therefore, a good ini\
tial route is preferred than
                           a random initial route.

							                 *)



program Two_Opt_Approx (input,output,TwooptDatafile,TwooptOutfile);

const maxvar = 50;

type	CHARFILE = file of char;
	ARRN = array [1..maxvar] of integer;
	ARRNN = array [1..maxvar,1..maxvar] of integer;

var	N : integer;
	W : ARRNN;
	ROUTE : ARRN;
	Nextint : integer;
	TwooptDatafile : CHARFILE;
	TwooptOutfile  : CHARFILE;


procedure Infile (var N : integer;
		  var W : ARRNN;
		  var ROUTE : ARRN;
		  var Nextint : integer);

var row, column : integer;

begin
  reset (TwooptDatafile);
  readln (TwooptDatafile, Nextint);
  N := Nextint;
  for row := 1 to N do
  begin
    for column := 1 to N do
    begin
      read (TwooptDatafile,Nextint);
      W[row,column] := Nextint;
    end;
    readln(TwooptDatafile);
  end;
  for row := 1 to N do
  begin
    read (TwooptDatafile,Nextint);
    ROUTE[row] := Nextint;
  end;
  readln(TwooptDatafile);
end;



procedure TWOOPT(
       N      :integer;
   var W      :ARRNN;
   var ROUTE  :ARRN);

   var AHEAD,I,I1,I2,INDEX,J,J1,J2,
       LAST,LIMIT,MAX,MAX1,NEXT,S1,S2,T1,T2:integer;
       PTR                                 :ARRN;
begin
   for I:=1 to N-1 do PTR[ROUTE[I]]:=ROUTE[I+1];
   PTR[ROUTE[N]]:=ROUTE[1];
   repeat  { until MAX = 0 }
      MAX:=0;  I1:=1;
      for I:=1 to N-2 do begin
         if I = 1 then LIMIT:=N-1
         else LIMIT:=N;
         I2:=PTR[I1];  J1:=PTR[I2];
         for J:=I+2 to LIMIT do begin
            J2:=PTR[J1];
            MAX1:=W[I1,I2]+W[J1,J2]-(W[I1,J1]+W[I2,J2]);
            if MAX1 > MAX then begin   { BETTER PAIR HAS BEEN FOUND }
               S1:=I1;  S2:=I2;
               T1:=J1;  T2:=J2;
               MAX:=MAX1
            end;
            J1:=J2
         end;  { for J }
         I1:=I2
      end;  { for I }
      if MAX > 0 then begin                    { SWAP PAIR OF EDGES }
         PTR[S1]:=T1;
         NEXT:=S2;  LAST:=T2;
         repeat
            AHEAD:=PTR[NEXT];  PTR[NEXT]:=LAST;
            LAST:=NEXT;  NEXT:=AHEAD
         until NEXT = T2;
      end  { if MAX > 0 }
   until MAX = 0;
   INDEX:=1;
   for I:=1 to N do begin
      ROUTE[I]:=INDEX;  INDEX:=PTR[INDEX]
   end
end;  { TWOOPT }



procedure Outfile (ROUTE : ARRN);		 

var count : integer;

begin
  rewrite(TwooptOutfile);
  writeln (TwooptOutfile,'The route for tsp using Two_Opt_Approx is path');
  for count := 1 to N do
  begin
    write (TwooptOutfile,ROUTE[count]:5);
  end;
  writeln(TwooptOutfile);
end;



begin (* main *)
  Infile (N,W,ROUTE,Nextint);
  TWOOPT (N,W,ROUTE);
  Outfile (ROUTE);
end.