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.
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.
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).
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.
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.
You should start be deciding what you have and what you want.
For a fitness function for Travelling Salesman Problem, according to your pseudo-code, you will have following input.
This should be the formal parameters of your fitness function.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With