[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

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!