Tsp.rar_TSP JAVA_tsp

/** The Traveling Sales Person problem solution class * This program includes four TSP solution methods * @author Arnas Kainskas and modified by Softhut Group * @author i5arka@vaidila.vdu.lt * @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 clearCiti