The Traveling Salesman Problem (TSP) is a classic optimization problem that aims to find the shortest possible path that visits all given cities and returns to the starting city. The problem is considered as NP-hard and there is no known exact algorithm that solves it efficiently for all instances. However, dynamic programming can be used to solve TSP for relatively small instances.
The basic idea of using dynamic programming for TSP is to break down the problem into sub-problems and solve them recursively. Specifically, we can frame TSP as a problem of finding the shortest path that visits a subset of cities and ends at a specific city. Let’s consider the following example,
City A is the starting city, and we want to find the shortest route that visits all six cities and returns to A. To apply dynamic programming to this problem, we can define the sub-problems and use their solutions to solve the original problem. The sub-problems can be defined as follows:
For each city i and subset S of cities that includes city A and i,
let dist(i, S) be the length of the shortest path that starts at A, visits each city in S exactly once, and ends at i.
Using this definition, we can write a recursive formula for dist(i, S) in terms of smaller sub-problems:
dist(i, {A, i}) = distance(A, i)
dist(i, S) = min { distance(j, i) + dist(j, S - {i}) } for all j in S except A and i.
Here, distance(j, i) is the distance between cities j and i, and S - i denotes the set obtained by removing city i from the set S.
Intuitively, the recursive formula computes the length of the shortest path that starts at A, visits each city in S exactly once, and ends at i, by considering all possible ways of arriving at i from some city j in S, visiting the remaining cities in S - i in the shortest possible way, and then continuing to i.
Once we have computed all dist(i, S) for all i and all subsets S that include A and i, we can find the optimal TSP path of length L* by finding the minimum of (distance(i, A) + dist(i, S - i)) for each i, where S is the set of all cities except A and i.
Here is the code to solve TSP problem using dynamic programming:
public class TravelingSalesmanProblem {
private static final int INF = 9999999;
private int n;
private int[][] distance;
private int[][] memo;
public TravelingSalesmanProblem(int[][] distance) {
this.distance = distance;
this.n = distance.length;
memo = new int[n][1 << n];
}
public int solve() {
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return tsp(0, 1);
}
private int tsp(int current, int visited) {
if (visited == (1 << n) - 1) {
return distance[current][0];
}
if (memo[current][visited] != -1) {
return memo[current][visited];
}
int minDistance = INF;
for (int i = 0; i < n; i++) {
if (i != current && ((visited & (1 << i)) == 0)) {
int newDistance = distance[current][i] + tsp(i, visited | (1 << i));
minDistance = Math.min(minDistance, newDistance);
}
}
memo[current][visited] = minDistance;
return minDistance;
}
}In this implementation, ‘distance‘ is a 2D array that stores the distances between all pairs of cities, and ‘n‘ is the number of cities. The ‘memo‘ array is used to store the solutions of sub-problems to avoid recomputation. The ‘solve‘ method initializes the ‘memo‘ array and calls the recursive ‘tsp‘ method with the starting city (0) and the bit representation of the set of visited cities (initially only the starting city is visited). The ‘tsp‘ method recursively computes the length of the shortest path that starts at the current city, visits all unvisited cities and returns to the starting city. The computation is based on the recursive formula described above. Finally, the method returns the computed length.
Overall, dynamic programming allows us to solve TSP in O(n2 * 2n) time complexity, where n is the number of cities. Although this is not an efficient solution for large values of n, it helps us understand the problem and provides a baseline for developing more efficient algorithms.