tsp.java

a tsp problem for solving tsp with random cities

/** The Traveling Sales Person problem solution class
 * This program includes four TSP solution methods
 * @author Arnas Kainskas and modified by Softhut Group
 * @author [e-mail]
 * @version 2.0 
 */

//package com.softwarehut.lsl.algorithm.costalgorithm;

import java.awt.Dimension;

public class Tsp {

	//** public sector

	/** Maximal cities number */
	public static final int MAXCITIES = 500;
	/** Array of current cities x co-ordinates */
	public int xCities[] = new int[MAXCITIES];
	/** Array of current cities y co-ordinates */
	public int yCities[] = new int[MAXCITIES];
	/** Array of current route */
	public int route[] = new int[MAXCITIES + 1];

	//** private sector

	/** Current maximal cities number */
	private int citiesLimit;
	/** Current maximal x co-ordinate value */
	private int maxX;
	/** Current maximal y co-ordinate value */
	private int maxY;
	/** Current minimal x co-ordinate value */
	private int minX;
	/** Current minimal y co-ordinate value */
	private int minY;
	/** best=0 , worse=1 */
	private int best_or_worst_route_calculation;
	
	private double BIG_NUMBER_FOR_DISTANCE_MATRIX= 10000.0; //FIXME calculate the biggest number for distance matrix

	private int cities; // current cities number
	private int iterations; // number of iterations
	private double[][] d = new double[MAXCITIES][MAXCITIES]; // distances matrix
	private boolean[] visitedCities = new boolean[MAXCITIES]; // city is visited or not 

	private int[] sortedByY = new int[MAXCITIES];

	//** constructors

	/**  Constructs a TSP using users parameters. 
	 @param minx Initial start x co-ordinate of the map
	 @param miny Initial start y co-ordinate of the map
	 @param width Map width
	 @param height Map height
	 @param citiesNr Cities limit
	 */
	public Tsp(int minx, int miny, int width, int height, int citiesNr) {
		minX = minx;
		minY = miny;
		maxX = minx + width;
		maxY = miny + height;
		citiesLimit = citiesNr;
		cities = 0;
		iterations = 0;
	}

	/**  Constructs a TSP using users parameters. 
	 @param minx Initial start x co-ordinate of the map
	 @param miny Initial start y co-ordinate of the map
	 @param width Map width
	 @param height Map height
	 @param citiesNr Cities limit
	 @param best_or_worse   best_route = 0;  worse_route = 1;
	 **/
	public Tsp(int minx, int miny, int width, int height, int citiesNr, int best_or_worst) {
		minX = minx;
		minY = miny;
		maxX = minx + width;
		maxY = miny + height;
		citiesLimit = citiesNr;
		cities = 0;
		iterations = 0;
		this.best_or_worst_route_calculation= best_or_worst;
	}

	/**  Constructs a TSP using users parameters. 
	 @param width Map width
	 @param height Map height
	 @param citiesNr Cities limit
	 */
	public Tsp(int width, int height, int citiesNr) {
		this(0, 0, width, height, citiesNr);
	}

	/** Default constructor. Constructs a TSP with map, which is 200 width and 200 height. City limit is 100 */
	public Tsp() {
		this(0, 0, 200, 200, MAXCITIES);
	}

	//***   

	//** public methods sector

	/** Returns string, representing main parameters of Tsp
	 * @return Returns Tsp param string
	 */
	public String getTspParams() {
		return "Minx: " + minX + " Miny: " + minY + " Maxx: " + maxX + " Cities limit: "
						+ citiesLimit + " Map size: " + (maxX - minX) + "x" + (maxY - minY);
	}

	/** Generates random test data. Generates random cities number and random cities co-ordinates. */
	public void randomTestData() {
		int nr;
		cities = 0;
		nr = (int) (3 + Math.random() * (citiesLimit - 3));
		for (int i = 0; i < nr; i++) {
			xCities[i] = (int) (minX + Math.random() * (maxX - minX));
			yCities[i] = (int) (minY + Math.random() * (maxY - minY));
			cities++;
		}
	}

	/** Changes current maximal cities number 
	 * @param maxCities New maximal cities value.
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setCitiesLimit(int maxCities) {
		if (maxCities < MAXCITIES) {
			citiesLimit = maxCities;
			return true;
		}
		return false;
	}

	/** Changes cities number 
	 * @param citiesNr New cities value.
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setCitiesNr(int citiesNr) {
		if (citiesNr < MAXCITIES) {
			cities = citiesNr;
			return true;
		}
		return false;
	}

	/** Returns the value of current cities limit
	 * @return Returns the value of current cities limit
	 */

	public int getCitiesLimit() {
		return citiesLimit;
	}

	/** Changes minimal x co-ordinate value
	 * @param minx New minimal x co-ordinate value
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setMinX(int minx) {
		if (minx < maxX) {
			minX = minx;
			return true;
		}
		return false;
	}

	/** Changes minimal y co-ordinate value
	 * @param miny New minimal y co-ordinate value
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setMinY(int miny) {
		if (miny < maxY) {
			minY = miny;
			return true;
		}
		return false;
	}

	/** Changes maximal x co-ordinate value
	 * @param maxx New minimal x co-ordinate value
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setMaxX(int maxx) {
		if (maxx > minX) {
			maxX = maxx;
			return true;
		}
		return false;
	}

	/** Changes maximal y co-ordinate value
	 * @param maxy New minimal y co-ordinate value
	 * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
	 */
	public boolean setMaxY(int maxy) {
		if (maxy > minY) {
			maxY = maxy;
			return true;
		}
		return false;
	}

	/** Returns tsp map size
	 * @return Returns dimension of tsp map size.
	 */

	public Dimension getMapSize() {
		return new Dimension(maxX - minX, maxY - minY);
	}

	/** Removes the cities, which are out of map bounds 
	 * @return No return value
	 */
	public void removeOutOfBoundsCities() {

		int[] temp = new int[MAXCITIES];
		int j = 0;
		for (int i = 0; i < cities; i++) {
			if ((xCities[i] > maxX) || (yCities[i] > maxY) || (xCities[i] < minX)
							|| (yCities[i] < minY)) {
				temp[j] = i;
				j++;
			}
		}

		for (int i = j - 1; i > -1; i--) {
			removeCity(temp[i]);
		}
	}

	/** Removes defined city from the map 
	 * @param  cityNr City number in array.
	 * @return Returns <I> true </I> if city was removed and <I> false </I> if not.
	 */

	public boolean removeCity(int cityNr) {

		if (cityNr < cities) {
			while (cityNr < cities - 1) {

				if (cityNr < MAXCITIES - 1) {
					xCities[cityNr] = xCities[cityNr + 1];
					yCities[cityNr] = yCities[cityNr + 1];
					cityNr++;
				} else {
					xCities[cityNr] = 0;
					yCities[cityNr] = 0;
					cityNr++;
				}
			}
			cities--;
			return true;
		}
		return false;
	}

	// **************

	/** Adds a city to the map 
	 * @param x New city x co-ordinate
	 * @param y New city y co-ordinate
	 * @return Returns <I> true </I> if city was added and <I> false </I> if not.
	 */
	public boolean addCity(int x, int y) {
		if (cities < citiesLimit) {
			//if ((x <= maxX) && (y <= maxY) && (x >= minX) && (y >= minY)) {
				xCities[cities] = x;
				yCities[cities] = y;
				cities++;
				return true;
			//}
        }
		System.err.println("Can not add new city  x: " +x+ "  y: "+  y +" cityNr. " + cities);
		return false;
	}

	/** Returns current number of added cities 
	 * @return Returns current number of added cities 
	 */
	public int getCitiesNr() {
		return cities;
	}

	/** Returns current iterations number 
	 * @return Returns number of iterations, needed to calculate TSP distance and route
	 */
	public int getIterationsNumber() {
		return iterations;
	}

	/** Clears all cities from the map */
	public void clearCities() {
		cities = 0;
		iterations = 0;
	}

	/** Calculates the traveling sales person distance using Nearest Neighbour calculation method
	 * @return Returns TSP distance.
	 */
	public double nearestNeighbour() {
		initCalc();
		return nearest_n(0);
	}

	/** Calculates the traveling sales person distance using Repeatetive Nearest Neighbour calculation method
	 * @return Returns TSP distance.
	 */
	public double repeatetiveNearestNeighbour() {

		double min_dist = Double.MAX_VALUE;
		double nn_dist;
		int rep_route[] = new int[MAXCITIES + 1]; // a copy of route used for rnn method    	

		initCalc();
		for (int i = 0; i < cities; i++) {
			// clear visited cities values
			for (int k = 0; k < cities; k++)
				visitedCities[k] = false;

			// get the distance and route starting from the city i	
			nn_dist = nearest_n(i);
			if (nn_dist < min_dist) {
				min_dist = nn_dist;
				for (int j = 0; j < cities + 1; j++)
					rep_route[j] = route[j];
			}
		}
		for (int j = 0; j < cities + 1; j++)
			route[j] = rep_route[j];

		return min_dist;
	}

	/** Calculates the traveling sales person distance using Random Two Optimals Exchange calculation method 
	 * @return Returns TSP distance.
	 */
	public double randomTwoOptimals() {
		initCalc();
		return two_optimals(1);
	}

	/** Calculates the traveling sales person distance using Nearest Neighbour initial value Two Optimals Exchange calculation 
	 * @return Returns TSP distance.
	 */
	public double nnTwoOptimals() {
		initCalc();
		return two_optimals(0);
	}

	// two optimals exchange algorythm
	private double two_optimals(int which) {

		int[] ptr = new int[MAXCITIES];
		int ahead, i1, i2, index, j1, j2, last, limit, n1, n2, next, s1 = 0, s2 = 0, t1 = 0, t2 = 0;

		double max, max1, tweight = 0;
		int n = cities;
		if (which == 0) {
			tweight = nearest_n(0);
		} else {
			for (int i = 0; i < n; i++) {
				route[i] = i;
				iterations++;
				if (i != n - 1) {
					tweight = tweight + d[i + 1][i];
				}
			}
			route[n] = 0;
			tweight = tweight + d[0][n - 1];
			iterations++;
		}

		n1 = n - 1;
		n2 = n1 - 1;

		// ptr yra masyvas, kuris parodo i kuri miesta vaziuoja sekanciame zingsnyje   
		for (int i = 0; i < n1; i++)
			ptr[route[i]] = route[i + 1];
		ptr[route[n1]] = route[0];

		//lygina visas ne galimas poras (poros negali tureti bendru virsuniu)
		do {
			max = 0;
			i1 = 0;
			for (int i = 0; i < n2; i++) {
				limit = (i == 0) ? n1 : n;
				i2 = ptr[i1];
				j1 = ptr[i2];
				for (int j = i + 2; j < limit; j++) {
					iterations++;
					j2 = ptr[j1];
					max1 = d[i1][i2] + d[j1][j2] - (d[i1][j1] + d[i2][j2]);

					// Jei surasta pora, kurios virsunes sukeitus vietomis
					// gaunamas trumpesnis atstumas, tai virsunes reikia isaugoti

					if (max1 > max) {
						s1 = i1;
						s2 = i2;
						t1 = j1;
						t2 = j2;
						max = max1;
					}
					j1 = j2;
				}
				i1 = i2;
			}

			// Jei turime geresni marsruta , reikia pakeisti informacija.
			if (max > 0) {

				//  Sukeicia virsunes
				ptr[s1] = t1;
				next = s2;
				last = t2;

				do {
					ahead = ptr[next];
					ptr[next] = last;
					last = next;
					next = ahead;
				} while (next != t2);
				//  Sumazina marsruto ilgi
				tweight = tweight - max;
			}
		} while (max != 0);

		// Pakeicia marsruta.
		index = 0;
		for (int i = 0; i < n; i++) {
			route[i] = index;
			index = ptr[index];
		}
		return tweight;
	}

	// nearest neighbour method      
	private double nearest_n(int start) {

		int next_c = 0, i, n;
		double mindist, distance = 0;
		i = start;
		for (n = 0; n < cities; n++) {
			mindist = Double.MAX_VALUE; // let it be, primary minimal distance
			for (int j = 0; j < cities; j++) {
				iterations++;
				if (n != cities - 1) { // to the start city we return in the last step
					if ((mindist > d[i][j]) && (i != j) && (visitedCities[j] != true)
									&& (j != start)) {
						mindist = d[i][j];
						next_c = j;
					}
				} else {
					mindist = d[i][start];
					next_c = start;
				}
			}

			visitedCities[i] = true;
			distance = distance + mindist;
			route[n] = i; // add visited city to a route array
			i = next_c; // city to which we go
		}

		// return to the start city
		visitedCities[i] = true;
		route[n] = i;
		return distance;
	}

	// init the matrix of distances values      
	private void initDistances() {
//		Initializing distance matrix for best route calculation
		if (best_or_worst_route_calculation == 0) {
			for (int i = 0; i < cities; i++) {
				for (int j = 0; j < cities; j++) {
					if (i == j) {
						d[i][j] = 0;
					} else {
						d[i][j] = (Math.sqrt((double) ((xCities[i] - xCities[j])
										* (xCities[i] - xCities[j]) + (yCities[i] - yCities[j])
										* (yCities[i] - yCities[j]))));
					}
				}
				visitedCities[i] = false; // at the begining all cities are not visited
				iterations = 0; // at the beginning number of iterationss is zero
			}
		} else {
			//Initializing distance matrix for worst route calculation

			for (int i = 0; i < cities; i++) {
				for (int j = 0; j < cities; j++) {
					if (i == j) {
						d[i][j] = 0;
					} else {
						double distance = (Math.sqrt((double) ((xCities[i] - xCities[j])
										* (xCities[i] - xCities[j]) + (yCities[i] - yCities[j])
										* (yCities[i] - yCities[j]))));
						// Adding a big number to turn around the costs on the graph edges
						d[i][j] = BIG_NUMBER_FOR_DISTANCE_MATRIX - distance;
					}
				}
				visitedCities[i] = false; // at the begining all cities are not visited
				iterations = 0; // at the beginning number of iterationss is zero
			}
		}
	}

	// method used to initialize calculations 
	private void initCalc() {
		initDistances();
	}

} ///~