#include "Problem.h"#include "Solution.h"/*  farthestInsertion.cpp  Program with the implementation of the function farthestInsertion(), which   generates a vrpsd solution  according to the farthest insertion heuristic.  The solution to be built must be given in input.*/#include <fstream.h>#include <iostream.h>#include <vector>using namespace std;#include <cstdlib>#ifndef DBLMAX    #define DBLMAX 1E37#endifvoid farthestInsertion( Solution& solution ){  //Read problem pointer from input solution.  Problem* pp = solution.getProblem();  int n = pp->numberOfCustomers;  int s = 0; //The starting city MUST be 0, that is, the depot!  int end1=0, end2=0, farthest=0, i, index, j;  int  nextindex;  double  maxdist, inscost, newcost;    /* initialization */  vector<int> cycle(n);  vector<double> dist(n);  for (i=0; i<n; i++)    cycle[i] = -1;  cycle[s] = 0; //the depot is the starting customer.  /*	printf("\n");	for (i=0; i<n; i++)	for (j=0; j<n; j++) {		printf(" %i %i %4.0f  ",i,j,w[i,j]);	}  */    /* calcolo le distanze tra il nodo di partenza e tutti gli altri      in dist[i] c'e' sempre la distanza massima tra tra i nodi appartenenti al ciclo     e il nodi i  */  double* ptr;  double* w=(double *) malloc(n * n*sizeof(double));  for(int i=0; i<n; i++)    for (int j=0; j<n; j++)      w[n*i+j] = pp->distanceMatrix[i][j];  for (i=0, ptr=w+n*s ; i<n; i++, ptr++){    dist[i] = *ptr;    //cout << s << " " << i << " " << dist[i] << " " << w[s*n+i] << endl;// equivale al w /////////  }      /* main loop */    for (i=0; i<n-1; i++) {    maxdist = -DBLMAX;    for (j=0; j<n; j++)      if (cycle[j] == -1 && dist[j] > maxdist) {	maxdist = dist[j];	farthest = j;	/*				printf("max %f %i \n",maxdist,j);*/      }    inscost = DBLMAX;    index = s;    for (j=0; j<=i; j++) {      nextindex = cycle[index];      newcost = *(w+index*n+farthest) +	*(w+farthest*n+nextindex) - 	*(w+index*n+nextindex);      if (newcost < inscost) {	inscost = newcost;	end1 = index;	end2 = nextindex;      }      index = nextindex;    }    cycle[farthest] = end2;    cycle[end1] = farthest;        /* printf("%i %i %i \n",farthest,end1,end2);       printf("%f %f %f %f\n",inf,inscost,newcost,*tweight); */    for (j=0, ptr=w+farthest*n; j<n; j++, ptr++)      if (cycle[j] == -1 && *ptr < dist[j])	{	  /*			printf(" %i %i %4.10f  %4.10f  %4.10f\n",farthest,j,dist[j],*ptr);				inserisco le nuove distanza tra il nodo e gli altri nodi 				in modo da sapere quelli che si sono avvicinati (saranno sfavoriti				dopo per  > maxdist */	  dist[j] = *ptr;	}  }  index = s;  for (i=0; i<n; i++) {    solution[i] = index;	    index = cycle[index];  }  free(w);  }void randomizedFarthestInsertion(Random* rnd, Solution& solution ){  //Read problem pointer from input solution.  Problem* pp = solution.getProblem();  int n = pp->numberOfCustomers;  int s = (int)(rnd->next() * n);   int end1=0, end2=0, farthest=0, i, index, j;  int  nextindex;  double  maxdist, inscost, newcost;    /* initialization */  vector<int> cycle(n);  vector<double> dist(n);  for (i=0; i<n; i++)    cycle[i] = -1;  cycle[s] = s; //the initial cycle is the trivial one.  /*	printf("\n");	for (i=0; i<n; i++)	for (j=0; j<n; j++) {		printf(" %i %i %4.0f  ",i,j,w[i,j]);	}  */    /* calcolo le distanze tra il nodo di partenza e tutti gli altri      in dist[i] c'e' sempre la distanza massima tra tra i nodi appartenenti al ciclo     e il nodi i  */  double* ptr;  double* w=(double *) malloc(n * n*sizeof(double));  for(int i=0; i<n; i++)    for (int j=0; j<n; j++)      w[n*i+j] = pp->distanceMatrix[i][j];  for (i=0, ptr=w+n*s ; i<n; i++, ptr++){    dist[i] = *ptr;    //cout << s << " " << i << " " << dist[i] << " " << w[s*n+i] << endl;// equivale al w /////////  }      /* main loop */    for (i=0; i<n-1; i++) {    maxdist = -DBLMAX;    for (j=0; j<n; j++)      if (cycle[j] == -1 && dist[j] > maxdist) {	maxdist = dist[j];	farthest = j;	/*				printf("max %f %i \n",maxdist,j);*/      }    inscost = DBLMAX;    index = s;    for (j=0; j<=i; j++) {      nextindex = cycle[index];      newcost = *(w+index*n+farthest) +	*(w+farthest*n+nextindex) - 	*(w+index*n+nextindex);      if (newcost < inscost) {	inscost = newcost;	end1 = index;	end2 = nextindex;      }      index = nextindex;    }    cycle[farthest] = end2;    cycle[end1] = farthest;        /* printf("%i %i %i \n",farthest,end1,end2);       printf("%f %f %f %f\n",inf,inscost,newcost,*tweight); */    for (j=0, ptr=w+farthest*n; j<n; j++, ptr++)      if (cycle[j] == -1 && *ptr < dist[j])	{	  /*			printf(" %i %i %4.10f  %4.10f  %4.10f\n",farthest,j,dist[j],*ptr);				inserisco le nuove distanza tra il nodo e gli altri nodi 				in modo da sapere quelli che si sono avvicinati (saranno sfavoriti				dopo per  > maxdist */	  dist[j] = *ptr;	}  }  index = 0; //The starting city MUST be 0, that is, the depot!  for (i=0; i<n; i++) {    solution[i] = index;	    index = cycle[index];  }  free(w);  }