using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.IO;
using System.Windows.Forms;

namespace zonizzazione
{  
   public class TSP : IDisposable
   {
      public double[,] d;      // n x n
      public int n;         // numero dei nodi
      public int[] sol;     // DIM: UNO PIU' DEI NODI, per chiudere il tour
      StreamWriter flog;
      
      public  double NearNeigh(bool demo)
      {  int i,j,jmin;
         double dmin,z;
         bool[] visitata=new bool[sol.Length];

         for(i=0;i<n;i++) 
         {  sol[i]=0;
            visitata[i]=false;
         }

         sol[0]=jmin=0;     // parto da 0, tanto per partire da qualche parte
         z = 0;
         for(i=0;i<n-1;i++)   // indice POSIZIONE da cui uscire
         {  visitata[sol[i]]=true;
            dmin=int.MaxValue;
            for(j=0;j<n;j++)  // NODO in cui andare (i e j SONO DIVERSI)
            {  if(!(visitata[j]))
               {  if(d[sol[i],j]<dmin)
                  {  dmin=d[sol[i],j];
                     jmin=j;
                  }
               }
            }     
            sol[i+1]=jmin;       
            z += d[sol[i],sol[i+1]];
         }
         z += d[sol[0],sol[n-1]];
         sol[n] = sol[0];  // serve al 3opt
         return(z);
      }

      // 3OPT. Precondizione: sol ha n+1 elementi, l'ultimo e' uguale al primo
      public double Loc3optASIM(int[] sol, double[,] d)
      {      
         int[] solnew = new int[sol.Length], soltemp = new int[sol.Length];
         double[] zorario = new double[sol.Length];   // costi incrementali tour in senso orario
         double[] zantior = new double[sol.Length];   // costi incrementali tour in senso antiorario
         int end1a,end2a,end3a,end1b,end2b,end3b;
         double z,znew=int.MaxValue, zorg=0, z2opt, zold,cost1,cost2;
         int i,k,n,n1,n2,cnt,nk;
      
         int nsol = n = sol.Length;  // con l'ultimo uguale al primo
         
         if(nsol <= 5) 
            return(-1);
         
         flog = new StreamWriter("log.txt", false);      // serve per vuotare ad ogni nuova esecuzione
         flog.Close();

         n2=nsol-2;
         n1=nsol-1;
      
         // Inizio di una nuova ricerca
         cnt = 0;
labStart:zold = 0;
         zorario[0] = 0;
         zantior[nsol-1] = 0;
         for(int js=0;js<nsol-1;js++)
         {  zold += d[sol[js],sol[js+1]];
            zorario[js+1] = zold;
            zantior[nsol-js-2] = zantior[nsol-js-1] + d[sol[nsol-js-1],sol[nsol-js-2]];
         }
         
         if(cnt == 0)      // soluzione originale da ottimizzare
            zorg = zold;
         cnt++;
            
         sol.CopyTo(soltemp,0);
         z2opt = Loc2optASIM(soltemp, d);
         if(z2opt < znew)   // nel caso un 2opt migliori un 3opt precedente
         {  znew = z2opt;
            soltemp.CopyTo(sol,0);
            goto labStart;
         }
         zold = ( zold < z2opt ? zold : z2opt);

         for(int ind1=1;ind1<n2;ind1++)                   // 0 ... ind1-1
         {  end1a=sol[ind1-1];
            end1b=sol[ind1];

            for(int ind2=ind1+1;ind2<n1;ind2++)       // ind1 ... ind2-1
            {  end2a=sol[ind2-1];
               end2b=sol[ind2];

               for(int ind3=ind2+1;ind3<nsol;ind3++)  // ind2 ... nsol
               {  end3a=sol[ind3-1];
                  end3b=sol[ind3];

                  // ------------------------------- primo riattacco:   1a-2a, 1b-3a, 2b-3b
                  #region primo riattacco
                  if(end1b==end2a) goto labSecondo;
                  if(end2b==end3a) goto labSecondo;

                  cost1 = zorario[nsol-1];
                  cost2 = zorario[ind1-1]                 + d[end1a,end2a]+
                          (zantior[ind1]-zantior[ind2-1]) + d[end1b,end3a]+
                          (zantior[ind2]-zantior[ind3-1]) + d[end2b,end3b]+
                          (zorario[nsol-1] - zorario[ind3]);
                  
                  if (cost2 < cost1)
                  {
                     // Qui ho migliorato
                     for(k=0;k<ind1;k++)
                        solnew[k]=sol[k];

                     k=ind1;
                     for(int lk=ind2-1;lk>=ind1;lk--)
                     {  solnew[k]=sol[lk];
                        k++;
                     }
                     for(int lk=ind3-1;lk>=ind2;lk--)
                     {  solnew[k]=sol[lk];
                        k++;
                     }
                     for(k=ind3;k<nsol;k++)
                        solnew[k]=sol[k];
            
                     znew = valutaSol(solnew,sol,nsol);

                     if(znew != cost2)
                        Trace.WriteLine("3opt (1a): qualcosa tragia");
                     zold=znew;
                     goto labStart;
                  }
               
                  // provo a riattaccare in senso antiorario
                  cost1 =  (cost1 < zantior[0] ? cost1 : zantior[0]);
                  cost2 =  zantior[ind3]                     + d[end3b,end2b] +
                           (zorario[ind3-1] - zorario[ind2]) + d[end3a,end1b] + 
                           (zorario[ind2-1] - zorario[ind1]) + d[end2a,end1a] +
                           (zantior[0] - zantior[ind1-1]);
                  
                  if( cost2 < cost1 ) 
                  {
                     nk=0;
                     for(int lk=nsol-1;lk>=ind3;lk--) // n ... ind3 (reversed)
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
                     for(int lk=ind2;lk<ind3;lk++)    // ind2 ... ind3-1
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
                     for(int lk=ind1;lk<ind2;lk++)    // ind1 ... ind2-1
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
                     for(int lk=ind1-1;lk>=0;lk--)    // 0 ... ind1-1
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
            
                     znew = valutaSol(solnew,sol,nsol);

                     if(znew != cost2)
                        Trace.WriteLine("3opt (1b): qualcosa tragia");
                     zold=znew;
                     goto labStart;
                  }
                  #endregion
                  
                  // ------------------------------- secondo riattacco: 1a-3a, 2b-1b, 2a-3b
                  #region secondo riattacco
labSecondo:       if(end1b == end2a) goto labTerzo;
                  if(end3b == end1a) goto labTerzo;
                  if(end2b == end3a) goto labTerzo;

                  cost1 = zorario[nsol-1];
                  cost2 = zorario[ind1-1]                +d[end1a,end3a]+
                          (zantior[ind2]-zantior[ind3-1])+d[end2b,end1b]+
                          (zorario[ind2-1]-zorario[ind1])+d[end2a,end3b]+
                          (zorario[nsol-1]-zorario[ind3]);

                  if (cost2 < cost1)
                  {
                     // Qui ho migliorato
                     for(k=0;k<ind1;k++)
                        solnew[k]=sol[k];

                     nk=ind1;
                     for(int lk=ind3-1;lk>=ind2;lk--)
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
                     for(int lk=ind1;lk<=ind2-1;lk++)
                     {  solnew[nk]=sol[lk];
                        nk++;
                     }
                     for(k=ind3;k<nsol;k++)
                     {  solnew[nk]=sol[k];
                        nk++;
                     }

                     znew = valutaSol(solnew,sol,nsol);

                     if(znew != cost2)
                        Trace.WriteLine("3opt (2a): qualcosa tragia");
                     zold=znew;
                     goto labStart;
                  }

                  // provo a riattaccare in senso antiorario
                  cost1 = (cost1 < zantior[0] ? cost1 : zantior[0]);
                  cost2 = zantior[ind3]                       + d[end3b, end2a] +
                          (zantior[ind1] - zantior[ind2 - 1]) + d[end1b, end2b] +
                          (zorario[ind3 - 1] - zorario[ind2]) + d[end3a, end1a] +
                          (zantior[0] - zantior[ind1 - 1]);

                  if (cost2 < cost1)
                  {
                     nk = 0;
                     for (int lk = nsol - 1; lk >= ind3; lk--) // n ... ind3 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind2-1; lk >= ind1; lk--)    // ind1 ... ind2-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind2; lk < ind3; lk++)    // ind2 ... ind3-1 
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind1 - 1; lk >= 0; lk--)    // 0 ... ind1-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }

                     znew = valutaSol(solnew,sol,nsol);

                     if (znew != cost2)
                        Trace.WriteLine("3opt (2b): qualcosa tragia");
                     zold = znew;
                     goto labStart;
                  }
                                    
                  #endregion

                  // ---------------------------------- terzo riattacco:   1a-2b, 3a-2a, 1b-3b
                  #region terzo riattacco
labTerzo:         if(end2b == end3a) goto labQuarto;
                  if(end1a == end3b) goto labQuarto;
                  if(end1b == end2a) goto labQuarto;

                  cost1 = zorario[nsol-1];
                  cost2 = zorario[ind1-1]                +d[end1a,end2b]+
                          (zorario[ind3-1]-zorario[ind2])+d[end3a,end2a]+
                          (zantior[ind1]-zantior[ind2-1])+d[end1b,end3b]+
                          (zorario[nsol-1]-zorario[ind3]);

                  if (cost2 < cost1)
                  {
                     // Qui ho migliorato
                     for (k = 0; k <= ind1-1; k++)
                        solnew[k] = sol[k];

                     nk=ind1;
                     for (int lk = ind2; lk <= ind3 - 1; lk++)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind2 - 1; lk >= ind1; lk--)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (k = ind3; k < nsol; k++)
                     {  solnew[nk] = sol[k];
                        nk++;
                     }
            
                     znew = valutaSol(solnew,sol,nsol);

                     if (znew != cost2)
                        Trace.WriteLine("3opt (3a): qualcosa tragia");
                     zold = znew;
                     goto labStart;
                  }

                  // provo a riattaccare in senso antiorario
                  cost1 = (cost1 < zantior[0] ? cost1 : zantior[0]);
                  cost2 = zantior[ind3]                        + d[end3b, end1b] +
                           (zorario[ind2 - 1] - zorario[ind1]) + d[end2a, end3a] +
                           (zantior[ind2] - zantior[ind3 - 1]) + d[end2b, end1a] +
                           (zantior[0] - zantior[ind1 - 1]);

                  if (cost2 < cost1)
                  {
                     nk = 0;
                     for (int lk = nsol - 1; lk >= ind3; lk--) // n ... ind3 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind1; lk < ind2; lk++)    // ind1 ... ind2-1 
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind3-1; lk >= ind2; lk--)    // ind3-1 ... ind2 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind1 - 1; lk >= 0; lk--)    // 0 ... ind1-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }

                     znew = valutaSol(solnew,sol,nsol);

                     if (znew != cost2)
                        Trace.WriteLine("3opt (3b): qualcosa tragia");
                     zold = znew;
                     goto labStart;
                  }
                  #endregion

                  // ------------------------------- quarto riattacco: 1a-2b, 3a-1b, 2a-3b
                  #region quarto riattacco
labQuarto:        if(end1a == end3b) continue;
                  if(end1b == end2a) continue;
                  if(end2b == end3a) continue;

                  cost1 = zorario[nsol-1];
                  cost2 = zorario[ind1-1]                +d[end1a,end2b]+
                          (zorario[ind3-1]-zorario[ind2])+d[end3a,end1b]+
                          (zorario[ind2-1]-zorario[ind1])+d[end2a,end3b]+
                          (zorario[nsol-1]-zorario[ind3]);

                  if (cost2 < cost1)
                  {
                     // Qui ho migliorato
                     for (k = 0; k <= ind1-1; k++)
                        solnew[k] = sol[k];

                     nk=ind1;
                     for (int lk = ind2; lk <= ind3 - 1; lk++)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind1; lk <= ind2-1; lk++)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (k = ind3; k < nsol; k++)
                     {  solnew[nk] = sol[k];
                        nk++;
                     }

                     znew = valutaSol(solnew,sol,nsol);

                     if (znew != cost2)
                        Trace.WriteLine("3opt (4a): qualcosa tragia");
                     zold = znew;
                     goto labStart;
                  }

                  // provo a riattaccare in senso antiorario
                  cost1 = (cost1 < zantior[0] ? cost1 : zantior[0]);
                  cost2 = zantior[ind3]                      + d[end3b, end2a] +
                           (zantior[ind1] - zantior[ind2-1]) + d[end1b, end3a] +
                           (zantior[ind2] - zantior[ind3-1]) + d[end2b, end1a] +
                           (zantior[0] - zantior[ind1 - 1]);

                  if (cost2 < cost1)
                  {
                     nk = 0;
                     for (int lk = nsol - 1; lk >= ind3; lk--) // n ... ind3 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind2-1; lk >= ind1; lk--)    // ind1 ... ind2-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind3-1; lk >= ind2; lk--)    // ind2 ... ind3-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }
                     for (int lk = ind1 - 1; lk >= 0; lk--)    // 0 ... ind1-1 (reversed)
                     {
                        solnew[nk] = sol[lk];
                        nk++;
                     }

                     znew = valutaSol(solnew,sol,nsol);

                     if (znew != cost2)
                        Trace.WriteLine("3opt (4b): qualcosa tragia");
                     zold = znew;
                     goto labStart;
                  }
                  #endregion
            
               }  // for l3 (inizio)
            }  // for l2 (inizio)
         }  // for l1 (inizio) 
         // write(*,*) ' fine opt3: ldold',ldold

         if(zorg>znew)
         {  //MessageBox.Show("Zorg = "+zorg+" znew = "+znew);
            zorg = znew;
            goto labStart;
         }

         z=0;
         sol[n-1]=sol[0];
         for(i=0;i<n-1;i++)
            z+=d[sol[i],sol[i+1]];

         // Trace.WriteLine("Fine 3 opt! z= "+z.ToString());

         return(znew);
      }
      
      // restituisce il costo della nuova soluzione e riassegna solnew a sol
      private double valutaSol(int[] solnew, int[] sol, int nsol)
      {  double znew = 0;
         //flog = new StreamWriter("log.txt", true);
         for (int js = 0; js < nsol; js++)
         {
            sol[js] = solnew[js];
            if (js < nsol - 1)
            {
               znew += d[solnew[js], solnew[js + 1]];
               //flog.WriteLine(String.Format("i {0} sol {1} d {2} znew {3}", js, sol[js], d[solnew[js], solnew[js + 1]], znew));
            }
         }
         //flog.Close();
         
         return(znew);
      }
      
      // 3opt simmetrico, precondizione: sol ha n+1 elementi, l'ultimo e' uguale al primo
      public  double Loc3optSIMM(int[] sol, double[,] d)
      {      
         int[] solnew = new int[sol.Length], soltemp = new int[sol.Length];
         double[] zorario = new double[sol.Length];   // costi incrementali tour in senso orario
         double[] zantior = new double[sol.Length];   // costi incrementali tour in senso antiorario
         int end1a,end2a,end3a,end1b,end2b,end3b;
         double z,znew=int.MaxValue, zorg=-1, z2opt, zprev, zold, l_old;
         int i,k,n,n1,n2,ind1, cnt;
      
         int nsol = n = sol.Length;  // con l'ultimo uguale al primo
         
         if(nsol <= 5) 
            return(-1);

         n2=nsol-2;
         n1=nsol-1;
      
         // Inizio di una nuova ricerca
         cnt = 0;
lab900:  zold = 0;
         zorario[0] = 0;
         zantior[nsol-1] = 0;
         for(int js=0;js<nsol-1;js++)
         {  zold += d[sol[js],sol[js+1]];
            zorario[js+1] = zold;
            zantior[nsol-js-2] = zantior[nsol-js-1] + d[sol[nsol-js-1],sol[nsol-js-2]];
         }
         
         if(cnt == 0)      // soluzione originale da ottimizzare
            zorg = zold;
         cnt++;
            
         sol.CopyTo(soltemp,0);
         z2opt = Loc2optASIM(soltemp, d);
         if(z2opt < znew)   // nel caso un 2opt migliori un 3opt precedente
         {  znew = z2opt;
            soltemp.CopyTo(sol,0);
         }
         zold = ( zold < z2opt ? zold : z2opt);

         for(ind1=1;ind1<n2;ind1++)                   // 0 ... ind1-1
         {  end1a=sol[ind1-1];
            end1b=sol[ind1];

            int ind1meno1=ind1-1;

            for(int ind2=ind1+1;ind2<n1;ind2++)       // ind1 ... ind2-1
            {  end2a=sol[ind2-1];
               end2b=sol[ind2];

               for(int ind3=ind2+1;ind3<nsol;ind3++)  // ind2 ... nsol
               {  end3a=sol[ind3-1];
                  end3b=sol[ind3];

                  l_old=zold-d[end1a,end1b]-d[end2a,end2b]-d[end3a,end3b];

                  // ------------------------------- primo riattacco
                  if(end1b==end2a) goto lab600;
                  if(end2b==end3a) goto lab600;

                  // provo a riattaccare 1a-2a, 1b-3a, 2b-3b
                  zprev = l_old+d[end1a,end2a]+d[end1b,end3a]+d[end2b,end3b];
                  if (zprev >= zold) goto lab600;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2-1;lk>=ind1;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind3-1;lk>=ind2;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  //flog = new StreamWriter("log.txt",true);
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                     {  znew += d[solnew[js],solnew[js+1]];
                        //flog.WriteLine(String.Format("i {0} sol {1} d {2} znew {3}",js,sol[js],d[solnew[js],solnew[js+1]],znew));
                     }
                  }
                  //flog.Close();            
                  if(znew != zprev)
                     MessageBox.Show("3opt (1): qualcosa tragia");
                  zold=znew;
                  goto lab900;
                  
                  // ------------------------------- secondo riattacco
lab600:           if(end1b == end2a) goto lab700;
                  if(end3b == end1a) goto lab700;

                  // provo a riattaccare 1a-3a, 2b-1b, 2a-3b
                  zprev = l_old+d[end1a,end3a]+d[end2b,end1b]+d[end2a,end3b];
                  if(zprev >= zold) goto lab700;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind3-1;lk>=ind2;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind1;lk<=ind2-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];

                  znew = 0;
                  //flog = new StreamWriter("log.txt",true);
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                     {  znew += d[solnew[js],solnew[js+1]];
                        //flog.WriteLine(String.Format("i {0} sol {1} d {2} znew {3}",js,sol[js],d[solnew[js],solnew[js+1]],znew));
                     }
                  }
                  //flog.Close();            
                  if(znew != zprev)
                     MessageBox.Show("3opt (2): qualcosa tragia");
                  zold=znew;
                  goto lab900;

                  // ------------------------------- terzo riattacco
lab700:           if(end2b == end3a) goto lab800;
                  if(end1a == end3b) goto lab800;

                  // provo a riattaccare 1a-2b, 3a-2a, 1b-3b
                  zprev = l_old+d[end1a,end2b]+d[end3a,end2a]+d[end1b,end3b];
                  if(zprev >= zold) goto lab800;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2;lk<=ind3-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind2-1;lk>=ind1;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                        znew += d[solnew[js],solnew[js+1]];
                  }            
                  if(znew != zprev)
                     MessageBox.Show("3opt (3): qualcosa tragia");
                  zold=znew;
                  goto lab900;

                  // ------------------------------- quarto riattacco
lab800:           if(end1a == end3b) continue;
                  if(end1b == end2a) continue;
                  if(end2b == end3a) continue;

                  // provo a riattaccare 1a-2b, 3a-1b, 2a-3b
                  zprev = l_old+d[end1a,end2b]+d[end3a,end1b]+d[end2a,end3b];
                  if(zprev >= zold) continue;
        
                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2;lk<=ind3-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind1;lk<=ind2-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                        znew += d[solnew[js],solnew[js+1]];
                  }            
                  if(znew != zprev)
                     MessageBox.Show("3opt (4): qualcosa tragia");
                  zold=znew;
                  goto lab900;
         
               }  // for l3 (inizio)
            }  // for l2 (inizio)
         }  // for l1 (inizio) 
         // write(*,*) ' fine opt3: ldold',ldold

         if(zorg>znew)
         {  //MessageBox.Show("Zorg = "+zorg+" znew = "+znew);
            zorg = znew;
            goto lab900;
         }

         z=0;
         sol[n-1]=sol[0];
         for(i=0;i<n-1;i++)
            z+=d[sol[i],sol[i+1]];

         // Trace.WriteLine("Fine 3 opt! z= "+z.ToString());

         return(znew);
      }
      
      // opt2. Precondizione: sol ha n+1 elementi, l'ultimo e' uguale al primo
      public double Loc2optASIM(int[] sol, double[,] d)
      {
         double znew=-1,zold,cost1,cost2;
         int[] solnew = new int[sol.Length];
         double[] zorario = new double[sol.Length];   // costi incrementali tour in senso orario
         double[] zantior = new double[sol.Length];   // costi incrementali tour in senso antiorario
         int end1a,end2a,end1b,end2b;
         int nk;
         int i;

         int nsol = sol.Length;  // con l'ultimo uguale al primo

         if(nsol <= 3) 
            goto end;

lab100:  zold = 0;  // qui si inizia una uova ricerca
         zorario[0] = 0;
         zantior[nsol-1] = 0;
         for(int js=0;js<nsol-1;js++)
         {  zold += d[sol[js],sol[js+1]];
            zorario[js+1] = zold;
            zantior[nsol-js-2] = zantior[nsol-js-1] + d[sol[nsol-js-1],sol[nsol-js-2]];
         }
         znew = zold;
         
         for(int ind1=1;ind1<nsol-1;ind1++)
         {  end1a=sol[ind1-1];   // taglio in posizione ind1-1
            end1b=sol[ind1];

            for(int ind2=ind1+2;ind2<nsol;ind2++)
            {  end2a=sol[ind2-1];      // taglio in posizione ind2-1
               end2b=sol[ind2];

               // provo a riattaccare gli end1 fra loro e gli end2 fra loro, senso orario
               cost1 =  zorario[nsol-1];
               cost2 =  zorario[ind1-1] + d[end1a,end2a] + (zantior[ind1] - zantior[ind2-1])+
                        d[end1b,end2b] + (zorario[nsol - 1] - zorario[ind2]);
               if( cost2 < cost1 && zorario[nsol-1] <= zantior[0]) 
               {
                  for(int lk=0;lk<ind1;lk++) // 0 ... ind1-1
                     solnew[lk]=sol[lk];

                  nk=ind1-1;
                  for(int lk=ind2-1;lk>=ind1;lk--) // ind1 ... ind2-1 (reversed)
                  {  nk++;
                     solnew[nk]=sol[lk];
                  }

                  for(nk=ind2;nk<nsol;nk++)  // ind2 ... n
                     solnew[nk]=sol[nk];

                  znew = 0;
                  for(i=0;i<nsol-1;i++)
                     znew += d[solnew[i],solnew[i+1]];

                  if(znew != cost2)
                     MessageBox.Show("2opt (1): qualcosa tragia");
                     
                  zold=znew;
                  for(int k=0;k<nsol;k++)
                     sol[k]=solnew[k];

                  goto lab100;   // ricomincia dalla nuova soluzione
               }
               
               // provo a riattaccare gli end1 fra loro e gli end2 fra loro, senso antiorario
               cost1 =  (cost1 < zantior[0] ? cost1 : zantior[0]);
               cost2 =  zantior[ind2] + d[end2b,end1b] + (zorario[ind2-1] - zorario[ind1])+
                        d[end2a,end1a] + (zantior[0] - zantior[ind1 - 1]);
               if( cost2 < cost1 ) 
               {
                  nk=0;
                  for(int lk=nsol-1;lk>=ind2;lk--) // n ... ind2 (reversed)
                  {  solnew[nsol -lk -1]=sol[lk];
                     nk++;
                  }

                  for(int lk=ind1;lk<ind2;lk++) // ind1 ... ind2-1
                  {  solnew[nk]=sol[lk];
                     nk++;
                  }

                  for(int lk=ind1-1;lk>=0;lk--)  // 0 ... ind1-1 (reversed)
                  {  solnew[nsol -lk -1]=sol[lk];
                     nk++;
                  }

                  znew = 0;
                  for(i=0;i<nsol-1;i++)
                     znew += d[solnew[i],solnew[i+1]];

                  if(znew != cost2)
                     MessageBox.Show("2opt (2): qualcosa tragia");
                     
                  zold=znew;
                  for(int k=0;k<nsol;k++)
                     sol[k]=solnew[k];

                  goto lab100;   // ricomincia dalla nuova soluzione
               }
            }  // for l2
         }  // for l1

end:     return(znew);
      }
      
      public double Loc2optASIM(int[] sol, int[] cli, int[,] d)
      {
         int znew=-1,zold;
         int[] solnew = new int[sol.Length];
         int[] zorario = new int[sol.Length];   // costi incrementali tour in senso orario
         int[] zantior = new int[sol.Length];   // costi incrementali tour in senso antiorario
         int end1a,end2a,end1b,end2b,cost1,cost2;
         int nk;
         int i;

         int nsol = sol.Length;  // con l'ultimo uguale al primo

         if(nsol <= 3) 
            goto end;

lab100:  zold = 0;  // qui si inizia una uova ricerca
         zorario[0] = 0;
         zantior[nsol-1] = 0;
         for(int js=0;js<nsol-1;js++)
         {  zold += d[cli[sol[js]],cli[sol[js+1]]];
            zorario[js+1] = zold;
            zantior[nsol-js-2] = zantior[nsol-js-1] + d[cli[sol[nsol-js-1]],cli[sol[nsol-js-2]]];
         }
         znew = zold;
         
         for(int ind1=1;ind1<nsol-1;ind1++)
         {  end1a=sol[ind1-1];   // taglio in posizione ind1-1
            end1b=sol[ind1];

            for(int ind2=ind1+2;ind2<nsol;ind2++)
            {  end2a=sol[ind2-1];      // taglio in posizione ind2-1
               end2b=sol[ind2];

               // provo a riattaccare gli end1 fra loro e gli end2 fra loro, senso orario
               cost1 =  zorario[nsol-1];
               cost2 =  zorario[ind1-1] + d[end1a,end2a] + (zantior[ind1] - zantior[ind2-1])+
                        d[end1b,end2b] + (zorario[nsol - 1] - zorario[ind2]);
               if( cost2 < cost1 && zorario[nsol-1] <= zantior[0]) 
               {
                  for(int lk=0;lk<ind1;lk++) // 0 ... ind1-1
                     solnew[lk]=sol[lk];

                  nk=ind1-1;
                  for(int lk=ind2-1;lk>=ind1;lk--) // ind1 ... ind2-1 (reversed)
                  {  nk++;
                     solnew[nk]=sol[lk];
                  }

                  for(nk=ind2;nk<nsol;nk++)  // ind2 ... n
                     solnew[nk]=sol[nk];

                  znew = 0;
                  for(i=0;i<nsol-1;i++)
                     znew += d[solnew[i],solnew[i+1]];

                  if(znew != cost2)
                     MessageBox.Show("2opt (1): qualcosa tragia");
                     
                  zold=znew;
                  for(int k=0;k<nsol;k++)
                     sol[k]=solnew[k];

                  goto lab100;   // ricomincia dalla nuova soluzione
               }
               
               // provo a riattaccare gli end1 fra loro e gli end2 fra loro, senso antiorario
               cost1 =  (cost1 < zantior[0] ? cost1 : zantior[0]);
               cost2 =  zantior[ind2] + d[end2b,end1b] + (zorario[ind2-1] - zorario[ind1])+
                        d[end2a,end1a] + (zantior[0] - zantior[ind1 - 1]);
               if( cost2 < cost1 ) 
               {
                  nk=0;
                  for(int lk=nsol-1;lk>=ind2;lk--) // n ... ind2 (reversed)
                  {  solnew[nsol -lk -1]=sol[lk];
                     nk++;
                  }

                  for(int lk=ind1;lk<ind2;lk++) // ind1 ... ind2-1
                  {  solnew[nk]=sol[lk];
                     nk++;
                  }

                  for(int lk=ind1-1;lk>=0;lk--)  // 0 ... ind1-1 (reversed)
                  {  solnew[nsol -lk -1]=sol[lk];
                     nk++;
                  }

                  znew = 0;
                  for(i=0;i<nsol-1;i++)
                     znew += d[solnew[i],solnew[i+1]];

                  if(znew != cost2)
                     MessageBox.Show("2opt (2): qualcosa tragia");
                     
                  zold=znew;
                  for(int k=0;k<nsol;k++)
                     sol[k]=solnew[k];

                  goto lab100;   // ricomincia dalla nuova soluzione
               }
            }  // for l2
         }  // for l1

end:     return(znew);
      }
      
      public void Dispose()
      {  this.Dispose();
      }
   }
}