[FEATURE REQUEST] Travelling Salesman Dynamic Programming
harshithsaiv opened this issue · 4 comments
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
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);
}
}
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