3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This is not an optimal solution for all points, is it attempting to be? \$\endgroup\$ – Oscar Smith Dec 8 '17 at 18:43
  • \$\begingroup\$ @OscarSmith I wouldn't say it's trying to be optimal for all points, just trying to be a solution in polynomial time. I haven't found a case it doesn't solve for yet; if you find one please let me know! \$\endgroup\$ – T145 Dec 8 '17 at 21:50
  • \$\begingroup\$ If I understand the algorithm correctly, for these points [(0,0), (1,1000), (2,0)], it will give that as the path which is nearly twice as long as optimal. If you are only trying to produce a solution with no bounds on how big it is, the traveling salesman problem is trivial. \$\endgroup\$ – Oscar Smith Dec 8 '17 at 21:57
  • 2
    \$\begingroup\$ And what do you want out of the copyright link? Code posted on any Stack Exchange site (including Code Review) are published under a Creative Commons Attribution Share Alike license, whether you like it or not. \$\endgroup\$ – Simon Forsberg Dec 9 '17 at 12:11
  • 1
    \$\begingroup\$ I see that you've edited your question several times now, I just wanted to add a note that continuously editing your question may lead to making it harder for reviewers, as they might read your code once, then wait a few hours, and then it has changed. It also summons the question on how more edits you plan on doing? \$\endgroup\$ – Simon Forsberg Dec 16 '17 at 11:12
1
\$\begingroup\$

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 )

(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.
\$\endgroup\$
  • \$\begingroup\$ I'm interested in your last, 2nd to last and 4th to last points; can you expound on those? As for the naming convention things, yes I can improve there, but they don't really effect the functionality. To reference your first point, I'm caring more about the algorithm itself than proper Java etiquette, b/c as you said there are better languages. I just did Java as it's very well known and can hopefully reach a wider audience. \$\endgroup\$ – T145 Dec 20 '17 at 7:25
  • \$\begingroup\$ For the 4th to last point, please ask more specific questions left after perusing both links. You can get the source code of most every JRE, sunsoft/oracle's Collections.sort(list) calls list.sort(null), which in turn uses this.toArray(); Arrays.sort(a, null). For the last point, I consider adding code to my answer. \$\endgroup\$ – greybeard Dec 20 '17 at 8:11
  • \$\begingroup\$ I've looked at the Collections.sort method even before your post. It takes a List data structure, and the only ones I could use for what I believe to be the best performance I have. If there's a way to improve it I'd love to know the specifics. Also, this should solve one of your qualms: github.com/T145/traveling-salesman/blob/master/src/T145/… \$\endgroup\$ – T145 Dec 21 '17 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.