TSP via Nearest Neighbour

Question

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"));
    }
}

Answer 1

High level design

Let me look at main

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");
}

I have many questions:

• What are the input cities?
• How can I change the programme to input my own dataset of cities?
• Why can't I use the solution elsewhere in my program? In other words, why does solveMe print the solution and not return it?
• Why is the timing code inside the TSP class? Why don't you remove it and just call it with time java TSP.java?

I would much rather see the following:

public static void main(String[] args) throws Exception {
    System.out.println(
        TravellingSalesMan.readFromFile(FILE_INPUT).solveByNearest() );
}

• TravellingSalesMan is a better name. The class name should describe the situation, the algorithm name can be a method.

• I can clearly see that the input comes from FILE_INPUT, a constant declared atop the code for easy of changing.

• Or I may want to pass in an array directly like:

TravellingSalesMan([ (1,2), (4,5) ...]).solveByNearest()

• The method returns a solution, that means that I can reuse it in another part of my program to make further calculation on it.

• If I want to solve the problem by any other heuristic I can just change the final method:

....    .solveByBruteForce()

Hardcoding the solution strategy in the class name and naming the solving as generally as solveMe would have made it impossible to expand this class.