/*----------------------------------------------------------------------  File    : TSP.java  Contents: a traveling salesman problem  Author  : Christian Borgelt  History : 19.11.2005 file created----------------------------------------------------------------------*/package acopt;import java.io.IOException;import java.io.InputStream;import java.io.File;import java.io.Reader;import java.util.Random;import util.Scanner;/*--------------------------------------------------------------------*/public class TSP {/*--------------------------------------------------------------------*/  /* --- constants --- */  private static final int BLKSIZE = 16;  /* --- instance variables --- */  protected int        size;    /* current number of vertices */  protected double[]   xs, ys;  /* coordinates of vertices */  protected double[][] dists;   /* distances between vertices */  protected boolean    sym;     /* flag for symmetric distances */  protected boolean    euclid;  /* flag for euclidean distances */  protected int[]      tour;    /* best (known) tour */  private   double     bbx, bby;/* bounding box of vertices */  private   double     bbw, bbh;/* (position and width and height) */  private   boolean    valid;   /* flag for valid bounding box */  /*------------------------------------------------------------------*/  public TSP () { this(BLKSIZE); }  public TSP (int size)  {                             /* --- create a traveling salesman p. */    this.size   = 0;            /* initialize the variables */    this.xs     = new double[size];    this.ys     = new double[size];    this.dists  = null;         /* do not create distance matrix yet */    this.euclid = true;         /* default: Euclidean distances */    this.sym    = true;         /* default: symmetric distances */    this.tour   = null;         /* there is no known (best) tour */    this.valid  = false;        /* the bounding box is not valid */  }  /* TSP() */  /*------------------------------------------------------------------*/  public TSP (int size, Random rand)  {                             /* --- create a traveling salesman p. */    this(size);                 /* initialize the variables, */    this.randomize(rand);       /* create random vertices, and */    this.makeDists(true);       /* calculate the distances */  }  /* TSP() */  /*------------------------------------------------------------------*/  private void resize (int size)  {                             /* --- resize coord. vectors */    int    k;                   /* current/new vector size */    double v[];                 /* buffer for reallocation */    k = this.size;              /* get the number of nodes to copy */    if (size < 0) size = k +((k < BLKSIZE) ? BLKSIZE : (k >> 1));    if (size < k) k = this.size = size;    System.arraycopy(this.xs, 0, v = new double[size], 0, k);    this.xs = v;                /* enlarge the x-coordinates vector */    System.arraycopy(this.ys, 0, v = new double[size], 0, k);    this.ys = v;                /* enlarge the y-coordinates vector */  }  /* resize() */  /*------------------------------------------------------------------*/  public int add (double x, double y)  {                             /* --- add a vertex */    if (this.size >= this.xs.length)      this.resize(-1);          /* resize the coord. vectors if nec. */    this.valid = false;         /* bounding box is no longer valid */    this.xs[this.size] = x;     /* set the coordinates */    this.ys[this.size] = y;     /* of the new vertex */    return this.size++;         /* and return its index */  }  /* add() */  /*------------------------------------------------------------------*/  public void randomize (Random rand)  {                             /* --- create random vertices */    for (int i = this.size = this.xs.length; --i >= 0; ) {      this.xs[i] = rand.nextDouble();      this.ys[i] = rand.nextDouble();    }                           /* set random coordinates */    this.valid = false;         /* bounding box is no longer valid */  }  /* randomize() */  /*------------------------------------------------------------------*/  public int    size   ()      { return this.size; }  public double getX   (int i) { return this.xs[i]; }  public double getY   (int i) { return this.ys[i]; }  public void   setPos (int i, double x, double y)  { this.xs[i] = x; this.ys[i] = y; }  /*------------------------------------------------------------------*/  public void transform (double scale, double xoff, double yoff)  {                             /* --- transform vertex coordinates */    for (int i = this.size; --i >= 0; ) {      this.xs[i] = this.xs[i] *scale +xoff;      this.ys[i] = this.ys[i] *scale +yoff;    }                           /* traverse and transform vertices */    this.valid = false;         /* bounding box is no longer valid */  }  /* transform() */  /*------------------------------------------------------------------*/  private void bbox ()  {                             /* --- compute bounding box */    int    i;                   /* loop variable */    double x, y;                /* coordinates of a vertex */    double xmax, ymax;          /* maximal x- and y-coordinates */    this.bbx = Double.MAX_VALUE; xmax = -Double.MAX_VALUE;    this.bby = Double.MAX_VALUE; ymax = -Double.MAX_VALUE;    for (i = this.xs.length; --i >= 0; ) {      x = this.xs[i];          /* traverse the vertices */      y = this.ys[i];          /* of the problem */      if (x < this.bbx) this.bbx = x;      if (x > xmax)     xmax     = x;      if (y < this.bby) this.bby = y;      if (y > ymax)     ymax     = y;    }                           /* find minimum and maximum coords. */    this.bbw = xmax -this.bbx;  /* compute the width and height */    this.bbh = ymax -this.bby;  /* of the bounding box */    this.valid = true;          /* the bounding box is now valid */  }  /* bbox() */  /*------------------------------------------------------------------*/  public double getX ()  { if (!this.valid) this.bbox(); return this.bbx; }  public double getY ()  { if (!this.valid) this.bbox(); return this.bby; }  public double getWidth ()  { if (!this.valid) this.bbox(); return this.bbw; }  public double getHeight ()  { if (!this.valid) this.bbox(); return this.bbh; }  /*------------------------------------------------------------------*/  public void makeDists (boolean calc)  {                             /* --- calculate distance matrix */    int    i, k;                /* loop variables */    double dx, dy;              /* coordinate-wise distances */    double v[];                 /* buffer for reallocation */    if (this.size < this.xs.length)      this.resize(this.size);   /* shrink the coord. vectors if poss. */    this.dists = new double[this.size][this.size];    if (!calc) return;          /* create the distance matrix */    for (i = this.size; --i >= 0; ) {      this.dists[i][i] = 0;     /* set diagonal elements to zero */      for (k = i; --k >= 0; ) { /* traverse the off-diagonal elements */        dx = this.xs[i] -this.xs[k];        dy = this.ys[i] -this.ys[k];        this.dists[i][k] = this.dists[k][i] = Math.sqrt(dx*dx +dy*dy);      }                         /* compute pairwise vertex distances */    }                           /* (Euclidian distances, symmetric) */    this.euclid = this.sym = true;  }  /* makeDists() */  /*------------------------------------------------------------------*/  public boolean isSymmetric ()