I have written code to implement the nearest neighbour algorithm to produce a solution for the TSP problem
On my machine, the code takes roughly 10 seconds. Since this is so short, a lot of the profilers I have tried don't get a chance to record it properly. How do I profile this code effectively?
When I define the distance matrix and the size globally, the code takes around 6 seconds, what could cause this difference?
The Code:
import static java.lang.Math.asin;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import static java.lang.Math.sqrt;
import static java.lang.Math.toRadians;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
public class TSPNearestNeighbour {
final static int size = 1000;
static double[][] distances = new double[size][size]; // cost matrix
public static void main(String[] args) throws Exception {
long start = System.nanoTime();
TSPNearestNeighbour instance = new TSPNearestNeighbour();
instance.solveMe();
System.out.println("Total time: " + (System.nanoTime() - start) / 1000000 + "ms");
}
public void solveMe() throws Exception {
String[] inputs = load("src/1000airports.txt"); //Towns are numbered from 1 to n in the file
double[][] coords = new double[size][size];
for (int i = 0; i < size; i++) {
String[] tokens = inputs[i].split(",");
for (int j = 0; j < tokens.length - 2; j++) {
coords[i][j] = Double.parseDouble(tokens[j + 2]);
}
}
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
distances[i][j] = haversin(coords[i][0], coords[j][0], coords[i][1], coords[j][1]);
distances[j][i] = distances[i][j];
}
}
long start = System.nanoTime();
int[] shortestPath = nearestNeighbour(distances);
System.out.println("Nearest took: " + (System.nanoTime() - start) / 1000000 + "ms");
//printPath(shortestPath);
double bestShort = 0;
for (int i = 0; i < size - 1; ++i) {
bestShort += distances[shortestPath[i] - 1][shortestPath[i + 1] - 1];
}
bestShort += distances[shortestPath[size - 1]][shortestPath[0]];
System.out.println("DONE w/ a distance of: " + bestShort);
printPath(shortestPath);
}
/* for each town in the graph,
start there, and find the closest town not yet visited.
set current location to that town, and add the distance
When all towns have been visited go home.
If the total distance is shorter than the previous best, update it
return the path with the shortest distance found
*/
public int[] nearestNeighbour(double[][] distances) {
boolean[] copy = new boolean[size];
int[] shortestPath = new int[size];
int current = 0;
double bestDistance = Double.MAX_VALUE;
// nearest neighbour thingy
int town = current;
for (int a = 0; a < size; a++) {
// reset distance array
Arrays.fill(copy, true);
double shortest = 0, dist = 0;
int[] temp = new int[size];
int index = 0;
temp[index++] = a + 1;
current = a;
for (int c = 0; c < size - 1; c++) {
shortest = Double.MAX_VALUE; // reset closest
for (int i = 0; i < size; i++) {
if(i == current) continue;
if (copy[i] && (distances[current][i] < shortest)) {
town = i;
shortest = distances[current][i];
}
}
copy[current] = false;
temp[index++] = town + 1;
current = town;
dist += shortest;
}
dist += distances[temp[index - 1] - 1][temp[0] - 1];
if (dist < bestDistance) {
shortestPath = Arrays.copyOf(temp, temp.length);
bestDistance = dist;
}
}
return shortestPath;
}
public double haversin(double x1, double x2, double y1, double y2) {
// difference between x and y co-ords
double differenceInX = toRadians(x2 - x1);
double differenceInY = toRadians(y2 - y1);
// convert to radians
// angle / 180.0 * PI
x1 = toRadians(x1);
x2 = toRadians(x2);
// 2r is a constant, and presuming the radius is 6371lm
return 12742.0 * asin(sqrt(sin(differenceInX / 2) * sin(differenceInX / 2) + sin(differenceInY / 2) * sin(differenceInY / 2) * cos(x1) * cos(x2)));
}
public void printPath(int[] path) {
for (int i = 0; i < size - 1; ++i) {
System.out.print(path[i] + ".");
}
System.out.println(path[size - 1]);
}
public String[] load(String path) throws Exception {
BufferedReader in = new BufferedReader(new FileReader(path));
StringBuilder contents = new StringBuilder();
String line;
while ((line = in.readLine()) != null) {
contents.append(line).append(System.getProperty("line.separator"));
}
in.close();
return contents.toString().split(System.getProperty("line.separator"));
}
}
java.awt.geom.Point2D
. In general, try not to write code whenever possible, most likely, someone else has done some work you can use. \$\endgroup\$ – Abhijit Sarkar Jan 13 '19 at 22:45