Travel Sales Man Problem (TSP) and Solution using Dynamic Programming

Given a graph of n vertices, determine the minimum cost path to start at a given vertex and travel
to each other vertex exactly once, returning to the starting vertex. In some versions, the starting and ending points are different and fixed, and all other points have to be visited exactly once from start to end.

A standard way to solve these problems is to try all possible orders of visiting the n points, which
results in a run-time of O(n!).

To calculate cost using Dynamic Programming, we need to establish recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i. We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset. So the algorithm is like below -

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i)
else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

According to the above dynamic programming based solution. There are at most O(n*2n) sub-problems, and each one takes linear time to solve. So, the total running time is in order of O(n2*2n).
which is less than O(n!), but still exponential. Space required here is also exponential.

Below is the program in java -

package com.refermynotes;
import java.util.ArrayList;

public class TSPEngine {
 private ArrayList outputArray = new ArrayList();
 private int g[][], p[][], npow, N, d[][];
 public ArrayList computeTSP(int[][] inputArray, int n) {
  N = n;
  npow = (int) Math.pow(2, n);
  g = new int[n][npow];
  p = new int[n][npow];
  d = inputArray;
  int i, j;
  // initialize all graph and path subset matrix to -1
  for (i = 0; i < n; i++) {
   for (j = 0; j < npow; j++) {
    g[i][j] = -1;
    p[i][j] = -1;
   }
  }
  // initialize based on distance matrix
  for (i = 0; i < n; i++) {
   g[i][0] = inputArray[i][0];
  }
  int result = tsp(0, npow - 2);
  outputArray.add(0);
  getPath(0, npow - 2);
  outputArray.add(result);
  return outputArray;
 }

  private int tsp(int start, int set) {
  int masked, mask, result = -1, temp;
  if (g[start][set] != -1) {
   return g[start][set];
  } else {
   for (int x = 0; x < N; x++) {
    mask = npow - 1 - (int) Math.pow(2, x);
    masked = set & mask;
    if (masked != set) {
     temp = d[start][x] + tsp(x, masked);
     if (result == -1 || result > temp) {
      result = temp;
      p[start][set] = x;
     }
    }
   }
   g[start][set] = result;
   return result;
  }
 }

  private void getPath(int start, int set) {
  if (p[start][set] == -1) {
   return;
  }
  int x = p[start][set];
  int mask = npow - 1 - (int) Math.pow(2, x);
  int masked = set & mask;
  outputArray.add(x);
  getPath(x, masked);
 }

  public static void main(String[] args) {
 int[][] matrix = new int[][] { { 0, 10, 15, 20 }, { 5, 0, 9, 10 },
    { 6, 13, 0, 12 }, { 8, 8, 9, 0 } };
  TSPEngine t = new TSPEngine();
  ArrayList res = t.computeTSP(matrix, 4);
  for (Integer i : res) {
   System.out.print(i + "\t");
  }
 }
}