Travelling Salesman - How to find permutations that are not equivalent

Question

We are trying to optimize our brute force method for TSP. It currently runs at (n-1)! but we can reduce it to (n-1)!/2 by ignoring paths which are equivalent.

What we can't figure out is how to stop going down branches that will lead to an equivalent path as our recursive function develops the path from start to finish.

e.g. let A be the start and end node and let G be a graph with 4 nodes, A,B,C,D. The intermediate path B->C->D is the same as C->D->B and D->B->C

Our current solution is:

private static int minPathFast(int[][] graph, String sequence, int[] nodesLeft, int start) {
    int min;
    if (nodesLeft.length == 0)
    {
        return 0;
    }
    if (nodesLeft.length == 1) {
        probes++;
        return calcDist(graph, sequence + " " + nodesLeft[0], start);
    } else {
        min = minPath(graph, sequence + " " + nodesLeft[0], remove(nodesLeft, nodesLeft[0]), start);
        for (int i = 1; i < nodesLeft.length; i++) {

            int[] newNodesLeft = remove(nodesLeft, nodesLeft[i]);

            int minPath = minPath(graph, sequence + " " + nodesLeft[i], newNodesLeft, start);
            if (minPath < min)
            {
                min = minPath;
            }

        }
    }
    return min;
}

Is there a reason for even finding a solution in O(n!) time at all when there's a perfectly good O(2^n * n^2) algorithm? — Jordi Vermeulen, May 13 '15 at 15:09
I don't think the [Held-Karp algorithm](http://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm) is *that* hard. Is your problem size particularly small? A factorial algorithm isn't going to work for more than about 15 vertices, unless you don't mind waiting for days and/or have access to a massive cluster. — Jordi Vermeulen, May 13 '15 at 15:16

score 0 · Answer 1 · edited May 23 '17 at 11:58

0

Can you not save already explored paths and use them without recalculating each time?

Write a comparator function for your paths. Each time you compute a path, save it in a Hashmap or similar that is accessible everywhere, and each time you're computing a path, make sure it isn't already in the Hashmap.

Mark nodes as already checked when you've explored all their connections, so you don't waste time recalculating subpaths. This will probably require you to replace your String path with some kind of List<Node> where Node is a class you write that represents any node on the graph.

Look into memoization

Stackoverflow on memoizing

Also, be sure to look at existing pathfinders, like A* which has a wealth of information online, and you can probably scavenge ideas from that.

edited May 23 '17 at 11:58

Community

1
1

answered May 13 '15 at 14:55

Jeremy Barnes

657
4
15

the problem is we have to travel all the way to the end of the branch to find the path and then compare it, to see if we've solved it already. But of course this means we're still calculating all the branches of the decision tree. – fosho May 13 '15 at 14:59
See my edit. Representing your path as a String is probably not the best. Or keep an array of "exhaustively checked" nodes. If Node B connects only to A and C, and you've tested both those subpaths, theres no reason to recalculate from B ever again. If currentNode is in exhaustedNodes, skip it. – Jeremy Barnes May 13 '15 at 15:01

score 0 · Accepted Answer · answered May 13 '15 at 15:36

Sure, though this isn't a brilliant algorithm to begin with. If you don't mind, I'll introduce a small change..

First of all a general tip, get rid of that string. Strings are terrible for anything that isn't a string, and you're using it to store an array of integers. Just use an array of integers. Also stop "removing" items from arrays. Just put permute it a bit and remember how many you've "removed" (so there would be two regions in the array, one for the items that are logically in it and one for items that have logically been removed).

But more importantly, you're exploring all of the search space, and you usually don't have to (except in annoying cases). If you calculate how much distance you've created in the partial circuit so far, you can prune entire sub-trees that can only lead to "worse than the best solution so far". That can be improved by starting out with a reasonable upper bound for example obtained using a greedy nearest-neighbour path and/or local search (2-OPT is the simplest, isn't too bad).

When you're doing that anyway, you can improve the pruning. The incomplete circuit has to be completed somehow, so you can add an underestimation of the required distance to complete it. A pretty basic one is to loop the partial circuit back to its beginning with the shortest path to it. But you can make a much better underestimation with linear programming; introduce a variable for every road, constrained to the range 0 .. 1. Add a constraint for every city that the sum of the variables corresponding to roads adjacent to that city is exactly 2. Constrain the roads that you've already chosen (implicitly by creating a partial permutation) to be 1. Set the weight of the variables to the length of their corresponding roads. Minimize using linear programming (get a library, it's hard to code it well). That actually gives an underestimation of the distance for the entire tour, not of the "part to finish it", so don't add it to the distance so far but just use it directly.

That will tend to create small subtours with 3 cities each, a bunch of triangles all over the map. That's sort of a shitty estimation, you can make it much better by banning the subtrours: take a subtour, create a constraint that the sum of the roads adjacent to that subtour be at least 2 (not exactly, you're allowed to go in and out multiple times, but you must go in an out at least once each so the sum of those roads is at least 2). Minimize again, if there are more subtours eliminate those as well. You'll probably get a solution that has roads "partially used" (ie assigned a value that is not either 0 or 1), so this doesn't give you the actual tour, just an underestimation of the distance it will be, given the choices made so far.

That's a half decent underestimation. Good enough to use for small problems, you can maybe handle 100 cities this way (much more than you can currently hope to handle). And this is just the beginning, there is so much more that you can do to improve the estimation, whole books have been written about it.

Thanks a lot Harold. Unfortuantely this is for a university project so we can't use outside libraries. We will take your other points into consideration though. — fosho, May 14 '15 at 09:17

Travelling Salesman - How to find permutations that are not equivalent

2 Answers2