[FEATURE REQUEST] Travelling Salesman Dynamic Programming

[harshithsaiv]

What would you like to Propose?

Feat: Implementing Travelling Salesman dynamic programming approach

Issue details

The TravelingSalesman function calculates the minimum cost to complete a round-trip through all cities, starting and ending at the first city, using dynamic programming with bitmasking to track visited cities.

Additional Information

No response

[Rutujaj24]

import java.io.;
import java.util.;

public class TSE {
// there are four nodes in example graph (graph is
// 1-based)

static int n = 4;
// give appropriate maximum to avoid overflow

static int MAX = 1000000;

// dist[i][j] represents shortest distance to go from i
// to j this matrix can be calculated for any given
// graph using all-pair shortest path algorithms
static int[][] dist = {
	{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
	{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
	{ 0, 20, 25, 30, 0 },
};

// memoization for top down recursion

static int[][] memo = new int[n + 1][1 << (n + 1)];

static int fun(int i, int mask)
{
	
	if (mask == ((1 << i) | 3))
		return dist[1][i];
	
	if (memo[i][mask] != 0)
		return memo[i][mask];

	int res = MAX;

	for (int j = 1; j <= n; j++)
		if ((mask & (1 << j)) != 0 && j != i && j != 1)
			res = Math.min(res,
						fun(j, mask & (~(1 << i)))
							+ dist[j][i]);
	return memo[i][mask] = res;
}

// Driver program to test above logic
public static void main(String[] args)
{
	int ans = MAX;
	for (int i = 1; i <= n; i++)
		// try to go from node 1 visiting all nodes in
		// between to i then return from i taking the
		// shortest route to 1
		ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
								+ dist[i][1]);

	System.out.println(
		"The cost of most efficient tour = " + ans);
}

}

[harshithsaiv]

import java.io.*;

import java.util.*;

public class TSE {

// there are four nodes in example graph (graph is

// 1-based)

static int n = 4;

// give appropriate maximum to avoid overflow

static int MAX = 1000000;

// dist[i][j] represents shortest distance to go from i

// to j this matrix can be calculated for any given

// graph using all-pair shortest path algorithms

static int[][] dist = {

  { 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },

  { 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },

  { 0, 20, 25, 30, 0 },

};

// memoization for top down recursion

static int[][] memo = new int[n + 1][1 << (n + 1)];

static int fun(int i, int mask)

{

  if (mask == ((1 << i) | 3))

  	return dist[1][i];

  

  if (memo[i][mask] != 0)

  	return memo[i][mask];



  int res = MAX;



  for (int j = 1; j <= n; j++)

  	if ((mask & (1 << j)) != 0 && j != i && j != 1)

  		res = Math.min(res,

  					fun(j, mask & (~(1 << i)))

  						+ dist[j][i]);

  return memo[i][mask] = res;

}

// Driver program to test above logic

public static void main(String[] args)

{

  int ans = MAX;

  for (int i = 1; i <= n; i++)

  	// try to go from node 1 visiting all nodes in

  	// between to i then return from i taking the

  	// shortest route to 1

  	ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)

  							+ dist[i][1]);



  System.out.println(

  	"The cost of most efficient tour = " + ans);

}

}

In the fun function, the base case condition mask == ((1 << i) | 3) is incorrect. It should be mask == (1 << (n + 1)) - 1