CODEWITHSUNDEEP
javapermutationpointstraveling-salesman
lorenzo
lorenzo

Reputation: 534

Java TSP Permute Points

Doing a project for school where we implement the Nearest Neighbor heuristic (which I have already done), and the Traveling Salesperson Problem where we do an exhaustive search (we then analyze the algorithms, their time complexity, etc). Our teacher said to look around for code to use (or modify) for the exhaustive search part instead of programming the whole thing as in the Nearest Neighbor portion. I have looked around, put only found stuff that does not pertain to how we were instructed to do our program. As opposed to the typical problem where you use integers, we are using points (x, y). My goal would be to calculate the shortest permutation and be able to know what that permutation was. So I'm thinking to have an array of array's (which contains the permutations).

If someone could help me out with the exhaustive search that would be nice.

Here is some excerpts from my code (member variables, function to calculate distance between two points, and where all the points are stored):

private int x;
private int y;
private boolean visited;

public double dist( point pt ){
    int xdist = this.getX() - pt.getX();
    int ydist = this.getY() - pt.getY();
    double xsr = xdist*xdist;
    double ysr = ydist*ydist;
    return Math.sqrt( xsr + ysr );
}

point[] points = new point[n];

Any help is greatly appreciated.

Upvotes: 0

Views: 1336

Answers (2)

elkrari
elkrari

Reputation: 19

You don't need (extra) memory for generating all permutations/solutions for a given instance. You can just write them on the screen...

Take a look at this implementation https://github.com/stardog-union/pellet/blob/master/core/src/main/java/org/mindswap/pellet/utils/PermutationGenerator.java.
It generates at each call of getNext() a new solution.

public void PermGen() {
    int[] tour;
    PermutationGenerator x = new PermutationGenerator(N);
    System.out.println(x.getTotal());
    while (x.hasMore()) {
        tour = x.getNext();
        System.out.println(Arrays.toString(tour));
    }
}

The Java code above prints all TSP instance solutions...
But You can of course save them (in file(s) for example) but you'll need hundred of Terabytes to do it.

Upvotes: 0

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27357

A single TSP possible solution is essentially just an array of cities which represents the order in which to visit them, without the starting city.

So, presume n (the number of cities) = 5. Then a single possible solution is represented as an array of length 4. Now, how many ways can you order the cities [B, C, D, E]? BCDE, BCED, BDCE, BDEC, ... That's 4! or 24 combinations. So for n cities you got (n-1)! combinations. For 10 cities that makes 362880 combinations. For 20 cities or 10^17 combinations you 'll run out of memory if you want to keep them all into memory.

An additional problem is that you 'll need n nested for loops, but it's impossible to just write those for loops, because there are n. (You can just start writing for() for() for() .... So, your implementation will probably need some sort of walker approach, where you have a single loop that ticks through all combinations, much like a digital clock with each digit representing 1 index in the array.

Upvotes: 1

Related Questions