Salesman Problem in Java
The Traveling Salesman Problem determines the shortest path that visits each city approximately once and loops back to the starting location. Another Java problem that is most like the Traveling Salesman's Problem is the Hamiltonian Cycle.
The fundamental contrast between TSP and the Hamiltonian cycle is that within the other, we must determine whether such a tour that stops in each city precisely once already exists. A Hamiltonian cycle is always present in the Traveling Salesman Problem since the graph is complete. The goal is to identify a Hamiltonian cycle with the least weight.
Solution
The most well-known computing problem is the traveling salesman problem. We can apply a brute-force strategy to compare every trip and choose the best one. A graph has (n - 1) vertices for every n vertices. A multitude of potential outcomes.
Although no polynomial time algorithm exists, dynamic programming can achieve the solution in less time.
Consider the graph G = (V, E), which consists of a collection of cities as nodes and a set of weighted edges as edges. The connection between vertices u and v is shown by the edge e(u, v). Vertex u and v are separated by a distance called d(u, v), which must not be negative.
Consider that after visiting a few cities, we are now in city j, having started at city 1. So, this is only a portion of the tour. Since j will determine which towns are the most convenient to visit next, we must unquestionably know it. To avoid repetition, we must also be aware of every city we have visited. As a result, this is the right sub-problem.
Let C(S, j) be the lengths of the Shortest Distance traversing each node in S exactly once, beginning at 1, and ending at j, for a subgroup of cities S 1, 2, 3,..., n that contains 1, and j in S.
Considering that the path cannot continue and terminate at 1, we define C(S, 1) = when |S| > 1.
Let's break C(S, j) into more manageable subproblems. Starting at 1 and ending at j is what we need to do. The city should choose in the following way.
C(S,j)=minC(S-{j},i)+d(i,j) where i∈Sandi≠j
c(S,j)=minC(s-{j},i)+d(i,j) where I∈Sandi≠j
Algorithm
C ({1}, 1) = 0
for s = 2 to N, do
for all the subsets of Sub Є {1, 2, 3, … , N} of size S and containing 1
C (Sub, 1) = ∞
for all j Є S and j ≠ 1
C (Sub, j) = min {C (Sub– {j}, i) + d(i, j) for i Є Sub and i ≠ j}
return minj C ({1, 2, 3, …, N}, j) + d(j, i)
Implementing the Traveling Salesman Problem
We employ the subsequent stages to implement the TSP program in Java:
- We look at a city as the beginning and the end. Because the route is circular, we can start in any city.
- According to the DFS method, we begin by traversing from the source to its nearby nodes.
- Determine the price of each traversal, maintain a note of the lowest price, and continually update the value of the minimum price stored value.
- Return the permutation with the lowest cost in the end.
Filename: SalesmanProblem.java
// Java program for salesman problem
//importing required packages
import java.util.*;
import java.io.*;
import java.util.Scanner;
// A class is created to implement code
class SalesmanProblem
{
// the method findHamiltonianCycles() for finding the cycles of all cities
static int findHamiltonianCycles(int[][] distances, boolean[] visitCities, int currPosition, int city, int counts, int costs, int hamiltonianCycles)
{
if (counts == city && distances[currPosition][0] > 0)
{
hamiltonianCycles = Math.min(hamiltonianCycles, costs + distances[currPosition][0]);
return hamiltonianCycles;
}
// the step for interacting over the paths
for (int i = 0; i < city; i++)
{
if (visitCities[i] == false && distances[currPosition][i] > 0)
{
// stores if it is visited
visitCities[i] = true;
hamiltonianCycles = findHamiltonianCycles(distances, visitCities, i, city, counts + 1, costs + distances[currPosition][i],
hamiltonianCycles);
// The node which is not visited is marked
visitCities[i] = false;
}
}
return hamiltonianCycles;
}
// main section of the program
public static void main(String[] args)
{
int city;
// The Scanner class object is created for gettig the input from the user as distance
Scanner sca = new Scanner(System.in);
// Entering the number of cities
System.out.println("Enter the total number of cities:");
city = sca.nextInt();
// reading the cities’ distances
int distances[][] = new int[city][city];
for( int i = 0; i < city; i++){
for( int j = 0; j < city; j++){
System.out.println("The Distance between the cities "+ (i+1) +" to cities"+ (j+1) +": ");
distances[i][j] = sca.nextInt();
}
}
// A boolean array is created for storing the boolean values for storing the cities visited or unvisited
boolean[] visitCities = new boolean[city];
// The first city is marked as visited
visitCities[0] = true;
int hamiltonianCycles = Integer.MAX_VALUE;
// call findHamiltonianCycles() method that returns the path, which consists of minimal path
hamiltonianCycles = findHamiltonianCycles(distances, visitCities, 0, city, 1, 0, hamiltonianCycles);
// displays the cycle which contains minimum distance
System. out.println(“The minimum distance is: ”+hamiltonianCycles);
}
}
Output
Enter the total number of cities:
5
The Distance between the cities 1 to cities1:
23
The Distance between the cities 1 to cities2:
18
1The Distance between the cities 1 to cities3:
5
The Distance between the cities 1 to cities4:
35
The Distance between the cities 1 to cities5:
12
The Distance between the cities 2 to cities1:
45
The Distance between the cities 2 to cities2:
124
The Distance between the cities 2 to cities3:
34
1The Distance between the cities 2 to cities4:
8
2The Distance between the cities 2 to cities5:
9
The Distance between the cities 3 to cities1:
34
The Distance between the cities 3 to cities2:
56
The Distance between the cities 3 to cities3:
3
The Distance between the cities 3 to cities4:
23
The Distance between the cities 3 to cities5:
23
The Distance between the cities 4 to cities1:
6
The Distance between the cities 4 to cities2:
34
The Distance between the cities 4 to cities3:
89
The Distance between the cities 4 to cities4:
35
The Distance between the cities 4 to cities5:
64
The Distance between the cities 5 to cities1:
91
The Distance between the cities 5 to cities2:
25
The Distance between the cities 5 to cities3:
39
The Distance between the cities 5 to cities4:
54
The Distance between the cities 5 to cities5:
49
The minimum distance is:67
Time complexity: O(N!)
The node will contain the n possibilities; the second will contain n-1 possibilities, and so on.
Space Complexity: O(N)