Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Traveling Salesman for java

Based on this pseudo code I am trying to implement a java fittness function for the Traveling Salesman problem but I am not sure if I am doing it right, can someone please help me out.

N   The number of cities to visit
T   A tour (list of integers of size N)
D   An N by N matrix containing each d(i,j)

Let s = 0
For i = 1 to (N-1)
Let a = ti
Let b = ti+1
Let s = s + d(a,b)
 End For
     Let end_city = tn
     Let start_city = t1
     Let s = s + d(end_city,start_city)
The tour length s

My attempt at writing this in java

public static ArrayList<Integer> Fitness(){
    int n = 10; // Number of cities to visit
    ArrayList<Integer> t = new ArrayList<Integer>();
    int[][] d = null;
    int s = 0, a, b;

    for (int i = 1; i<n; i++){
        for (int j = 1; j<n; j++){
            d = new int[i][j];
        }

        for( i = 1; i<n; i++){
            a = t.get(i);
            b = t.get(i+1);
            s = s + d[a][b];
        }
        int end_city = t.get(n);
        int start_city = t.get(1);
        s = s + d[end_city][start_city];
    }
    return t;

Can someone please help me out. Thanks.

like image 467
Mikey Avatar asked Feb 25 '15 20:02

Mikey


People also ask

What is TSP in Java?

In Java, Travelling Salesman Problem is a problem in which we need to find the shortest route that covers each city exactly once and returns to the starting point. Hamiltonian Cycle is another problem in Java that is mostly similar to Travelling Salesman Problem.

Which algorithm is used for Travelling Salesman Problem?

A: Travelling Salesman Problem uses Dynamic programming with masking algorithm. Q: What is the complexity of the Travelling salesman problem? A: The complexity of TSP using Greedy will be O(N^2LogN) and using DP will be O(N^22^N).

Is Travelling salesman dynamic programming?

The traveling salesman problem(TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited. Dynamic programming(DP) is the most powerful technique to solve a particular class of problems.

How does Dynamic Programming solve TSP?

Dynamic Programming Approach for Solving TSPIf the number of cities in the subset is two, then the recursive function returns their distance as a base case. , then we'll calculate the distance from the current city to the nearest city, and the minimum distance among the remaining cities is calculated recursively.


1 Answers

You should start be deciding what you have and what you want.


What you have

For a fitness function for Travelling Salesman Problem, according to your pseudo-code, you will have following input.

  • Number of cities
  • A tour whose fitness is to be calculated
  • Map with distances (in this case adjacency matrix).

This should be the formal parameters of your fitness function.


What you want

The purpose of a fitness function is to have a way to measure quality in terms of a single parameter.

In this case, the length is serving that purpose.

This should be the returning value of your fitness function.


This makes the prototype of your fitness function to be as following

public double fitness(List<Integer> tour,
                      int numberOfCities,
                      double[][] distanceBetween);

Now the pseudo-code for the body is easy to decode if you indent it correctly and have another look.

Let s = 0
For i = 1 to (N-1)
    Let a = ti
    Let b = ti+1
    Let s = s + d(a,b)
End For
Let end_city = tn
Let start_city = t1
Let s = s + d(end_city,start_city)
The tour length s

It should be fairly easy to work out the rest. It is pretty straightforward to translate it to Java.

Good luck.

like image 146
Tanmay Patil Avatar answered Oct 13 '22 12:10

Tanmay Patil