Traveling Salesman Solution

Question

The intended purpose for posting here is to have more experienced software developers review my code, test it, and improve it. Should it to hold up, my ultimate goal is to construct a proof that reinforces it to prove that it works across all cases.

The Theory

After some research, my theory most closely resembles the Nearest Neighbor Algorithm by Rosenkratz, Stearns and Lewis, detailed on page 242 of this paper. The concept I use is entirely original, but the performance is very similar to their take.

My first step was to think about the problem differently. The classic TSP (Traveling Salesman Problem) is stated along these lines:

Find the shortest possible route that visits every city exactly once and returns to the starting point.

The problem is defined as the shortest route that starts and ends at the same point, which is essentially the shortest circuit for the whole graph, making the start aribtrary. In other words, no matter where you start on the graph, there will only be one "shortest path." The question then becomes:

Find the shortest possible circuit that visits every city exactly once.

The easiest way to make this understandable for a computer is to make the whole graph into one line.

Thinking abstractly, we take all of the points in the graph and arrange them into one straight line along the y-axis, creating a path with the shortest distance between each point.

This would give us the shortest Hamiltonian, but we can't say that the shortest Hamiltonian always results in the shortest possible circuit. The length of the overall path must be considered when choosing each subpath.

Now the only time we run into problems when using my method is if any point shares the same y-value with another point.

I call these points collisions. To find the best place to put them into the graph, all we have to do is test the distance at each point and choose which index gives us the shortest distance.

This is the part of the algorithm that performs the worst, and has the most room for improvement.

The pseudocode for the whole algorithm is as follows:

solution = new list
collisions = new list

// init solution

// sort solution

// be sure we have the shortest path, and remove any collisions for future calculation

if we have collisions
// find the best places to put them

Results

Currently my implementation works for the following cases:

• a single point (length 0)
• simple to complex polygons
• lines (simple to complex functions implied)
• scatter plots (implied from polygons)

Every possible path would have to be either one or a mixture of these.

Reference.java

package T145.salesman;

import java.util.Random;

public class Reference {

    private Reference() {}

    public static final double[][] TRICKY_TRAPEZOID = { { 2, 4 }, { 4, 4 }, { 6, 4 }, { 3, 1 }, { 5, 1 } };
    public static final double[][] SIMPLE_GRAPH = { { 1, 1 }, { 2, 3 }, { 3, 5 }, { 4, 3 }, { 5, 5 }, { 6, 1 }, { 7, 6 } };
    public static final double[][] LINE = { { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }, { 5, 5 }, { 6, 6 }, { 7, 7 } };
    public static final double[][] FLAT_LINE = { { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 } };
    public static final double[][] SQUARE = { { 1, 1 }, { 5, 5 }, { 1, 5 }, { 5, 1 } };
    public static final double[][] SQUARE_WITH_CENTER = { { 1, 1 }, { 5, 5 }, { 1, 5 }, { 5, 1 }, { 3, 3 } };
    public static final double[][] RHOMBUS = { { 2, 2 }, { 3, 5 }, { 4, 3 }, { 5, 6 } };

    // user-created problems
    public static final double[][] OSCAR_DILEMA = { { 0, 0 }, { 1, 1000 }, { 2, 0 }, { 3, 1000 } };
    public static final double[][] GREYBEARD = { { 0, 0 }, { 1, 99 }, { 2, 98 }, { 3, 3 }, { 4, 4 }, { 5, 95 } };

    public static final double[][] getRandomIntegerGraph(int maxSize) {
        double[][] graph = new double[maxSize][maxSize];
        Random rand = new Random();

        for (int t = 0; t < maxSize; ++t) {
            for (int s = 0; s < maxSize; ++s) {
                graph[t][s] = rand.nextInt(maxSize);
            }
        }

        return graph;
    }

    public static final double[][] getRandomDoubleGraph(int maxSize) {
        double[][] graph = new double[maxSize][maxSize];
        Random rand = new Random();

        for (int t = 0; t < maxSize; ++t) {
            for (int s = 0; s < maxSize; ++s) {
                graph[t][s] = rand.nextDouble();
            }
        }

        return graph;
    }
}

Main.java

package T145.salesman;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Main {

    private static class Point implements Comparable<Point> {

        private final double x;
        private final double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double getX() {
            return x;
        }

        public double getY() {
            return y;
        }

        public double getDistance(Point dest) {
            double distX = dest.getX() - x;
            double distY = dest.getY() - y;
            distX *= distX;
            distY *= distY;
            return Math.sqrt(distX + distY);
        }

        @Override
        public String toString() {
            return "{ X: " + x + "; Y: " + y + " }";
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Point) {
                Point point = (Point) obj;
                return point.x == x && point.y == y;
            }

            return false;
        }

        @Override
        public int compareTo(Point other) {
            int result = Double.compare(x, other.getX());

            if (result == 0) {
                result = Double.compare(y, other.getY());
            }

            return result;
        }
    }

    private static Point getNextPoint(List<Point> points, int start) {
        return points.get(start == points.size() - 1 ? 0 : start + 1);
    }

    private static double getTotalDistance(List<Point> points) {
        double shortestDist = 0;

        for (int t = 0; t < points.size(); ++t) {
            shortestDist += points.get(t).getDistance(getNextPoint(points, t));
        }

        return shortestDist;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        double[][] graph = Reference.GREYBEARD;

        if (graph.length <= 1) {
            System.out.println("SOLUTION: 0");
            return;
        }

        LinkedList<Point> points = new LinkedList<>();
        ArrayDeque<Point> collisions = new ArrayDeque<>(graph.length);

        // O(n)
        System.out.println("Input Graph: ");
        for (int t = 0; t < graph.length; ++t) {
            Point point = new Point(graph[t][0], graph[t][1]);
            points.add(point);
            System.out.println(point);
        }

        // O(nlog(n))
        Collections.sort(points);

        List<Point> virtualSolution;

        // O(n^2)
        for (int t = 0; t < points.size(); ++t) {
            Point point = points.get(t);

            for (int s = t + 1; s < points.size(); ++s) {
                Point other = points.get(s);

                if (point.getY() == other.getY()) {
                    collisions.add(other);
                    points.remove(s);
                }
            }

            virtualSolution = new ArrayList<>(points);
            Collections.swap(virtualSolution, t, t == 0 ? points.size() - 1 : t - 1);

            double solutionDist = 0;
            double virtualDist = 0;

            for (int s = 0; s < points.size(); ++s) {
                solutionDist += points.get(s).getDistance(getNextPoint(points, s));
                virtualDist += virtualSolution.get(s).getDistance(getNextPoint(virtualSolution, s));
            }

            if (virtualDist < solutionDist) {
                points = new LinkedList<>(virtualSolution);
            }
        }

        if (!collisions.isEmpty()) {
            Map<Double, Integer> distances = new HashMap<>(points.size(), 1F);

            // O(n^3)
            while (!collisions.isEmpty()) {
                Point c = collisions.remove();

                for (int t = 0; t < points.size(); ++t) {
                    virtualSolution = new ArrayList<>(points);
                    virtualSolution.add(t, c);
                    distances.put(getTotalDistance(virtualSolution), t);
                }

                points.add(distances.get(Collections.min(distances.keySet())), c);
                distances.clear();
            }
        }

        System.out.println('\n' + " --- RESULT ---");

        for (Point point : points) {
            System.out.println(point);
        }

        System.out.println('\n' + " --- VERIFICATION ---");
        System.out.println("Graph Length:\t" + graph.length);
        System.out.println("Solution Size:\t" + points.size());
        System.out.println("VERIFIED: " + (points.size() == graph.length));
        System.out.println('\n' + " --- FINAL PHASE ---");
        System.out.println("SOLUTION: " + getTotalDistance(points));
        System.out.println("Runtime: " + (System.currentTimeMillis() - start) + " ms");
    }
}

GitHub

Copyright

Answer 1

review my code, test it, and improve it sums it up nicely - you might have been explicit about the dimensions of improvement, though.

The first thing to consider with non-throw-away code is readability/maintainability. Enough has been said about premature optimisation - I find instances of premature analysis with your code.
The very concept of (y-coordinate)collisions is flaky - just rotate so slightly that formerly identical y-coordinate values get separated while none separate before collide.

• state your approach/idea explicitly. With every "significant" piece of code, state what it is there for - don't think can be seen/deduced from the code.
  (Be sure to keep this up-to-date with non-trivial code changes!)
  (There has been the idea of literate programming - I rather think of intentional coding (intentional programming without language support).)
  • do not rely on "external" information to be accessible when the code is:
    put essential information(/=documentation) in the source file(s)
• do not rely on hierarchical naming to the extent of having the last component nothing but generic: not (xyz.salesperson.)Reference/Main (or Implementation, Solution,…), but ShortestCircle or similar
• program "against interfaces", not classes (you got that right with virtualSolution)
• do not put the basic operation of a class into main() (or run()) - give it a telling name like ShortestCircle.fromCoordinates()
• give test first serious thought
• for tinkering with ideas, there are languages I consider more suitable (some even similar to Java - have a look at python3)

(I'd rather not have a test-main() in a source file of its own: If concerned about jar size or the code loaded into the VM, use a nested class or similar.)

• The getRandomNumberGraph()s are just weird: They couple the number of entries and the range of values. I have no idea how the values returned relate to the concept graph. If they return Points (or coordinate tuples), they should have a dimensions parameter (default 2?) - returning a square array looks as wrong as does just using the magic indices 0 and 1.
• The result of Point.toString() is more verbose than I like it ((x, y) would be fine with me), and my IDE complains that a class defining equals() should define int hashCode(), too.
• getTotalDistance() is a candidate for an foreach-loop, if not for stream reduction.
• fromCoordinates()("salesman.Main.main()") is too long and needs decomposition.
• There are data structures faster to sort than LinkedLists - if interested, have a look at what Collections.sort(list) does.
• In "the if (t > 0)-block", virtualSolution and points differ in two distances, (or none at all): computing every distance twice seems to be uncalled for. Come to think of it, the distances stay the same but for the neighbours of the points swapped: just compute nothing but those.