Dynamic Programming: Using tablulated space to avoid repeated recursive call.

Traveling Sales Man (TSP) problem Template: https://www.geeksforgeeks.org/bitmasking-dynamic-programming-set-2-tsp/

``````#include <bits/stdc++.h>
using namespace std;

#define INF 99999999
#define MAXR 12
#define MAXC 12
#define MAXHOUSE 12

// stores distance taking souce
// as every dirty tile
int dist[MAXR][MAXC][MAXHOUSE];

// memoization for dp states

// stores coordinates for
// dirty tiles
vector < pair < int, int > > dirty;

// Directions
int X[] = {-1, 0, 0, 1};
int Y[] = {0, 1, -1, 0};

char arr[21][21];

// len : number of dirty tiles + 1
// limit : 2 ^ len -1
// r, c : number of rows and columns
int len, limit, r, c;

// Returns true if current position
// is safe to visit
// else returns false
// Time Complexity : O(1)
bool safe(int x, int y)
{
if (x >= r or y>= c or x<0 or y<0)
return false;
if (arr[x][y] == '#')
return false;
return true;
}

// runs BFS traversal at tile idx
// calulates distance to every cell
// in the grid
// Time Complexity : O(r*c)
void getDist(int idx){

// visited array to track visited cells
bool vis[21][21];
memset(vis, false, sizeof(vis));

// getting current positon
int cx = dirty[idx].first;
int cy = dirty[idx].second;

// initializing queue for bfs
queue < pair < int, int > > pq;
pq.push({cx, cy});

// initializing the dist to max
// because some cells cannot be visited
// by taking source cell as idx
for (int i = 0;i<= r;i++)
for (int j = 0;j<= c;j++)
dist[i][j][idx] = INF;

// base conditions
vis[cx][cy] = true;
dist[cx][cy][idx] = 0;

while (! pq.empty())
{
auto x = pq.front();
pq.pop();
for (int i = 0;i<4;i++)
{
cx = x.first + X[i];
cy = x.second + Y[i];
if (safe(cx, cy))
{
if (vis[cx][cy])
continue;
vis[cx][cy] = true;
dist[cx][cy][idx] = dist[x.first][x.second][idx] + 1;
pq.push({cx, cy});
}
}
}
}

// Dynamic Programming state transition recursion
// with memoization. Time Complexity: O(n*n*2 ^ n)
{
// goal state
return dist[0][0][idx];

int ret = INT_MAX;

// state transiton relation
for (int i = 0;i<len;i++)
{
if ((mask & (1<<i)) == 0)
{
ret = min( ret, solve(i, newMask)
+ dist[dirty[i].first][dirty[i].second][idx]);
}
}

}

void init()
{
// initializing containers
memset(dp, -1, sizeof(dp));
dirty.clear();

// populating dirty tile positions
for (int i = 0;i<r;i++)
for (int j = 0;j<c;j++)
{
if (arr[i][j] == '*')
dirty.push_back({i, j});
}

// inserting ronot's location at the
// begining of the dirty tile
dirty.insert(dirty.begin(), {0, 0});

len = dirty.size();

limit = (1<<len) - 1;

// precalculating distances from all
// dirty tiles to each cell in the grid
for (int i = 0;i<len;i++)
getDist(i);
}

int main(int argc, char const *argv[])
{
// Test case #1:
//     .....*.
//     ...#...
//     .*.#.*.
//     .......

char A[4][7] = { {'.', '.', '.', '.', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'},
{'.', '*', '.', '#', '.', '*', '.'},
{'.', '.', '.', '.', '.', '.', '.'}
};

r = 4; c = 7;

cout << "The given grid : " << endl;

for (int i = 0;i<r;i++)
{
for (int j = 0;j<c;j++)
{
cout << A[i][j] << " ";
arr[i][j] = A[i][j];
}
cout << endl;
}

// - initializitiation
// - precalculations
init();

int ans = solve(0, 1);

cout << "Minimum distance for the given grid : ";
cout << ans << endl;

// Test Case #2
//     ...#...
//     ...#.*.
//     ...#...
//     .*.#.*.
//     ...#...

char Arr[5][7] = { {'.', '.', '.', '#', '.', '.', '.'},
{'.', '.', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'},
{'.', '*', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'}
};#include <bits/stdc++.h>
using namespace std;

#define INF 99999999
#define MAXR 12
#define MAXC 12
#define MAXHOUSE 12

// stores distance taking souce
// as every dirty tile
int dist[MAXR][MAXC][MAXHOUSE];

// memoization for dp states

// stores coordinates for
// dirty tiles
vector < pair < int, int > > dirty;

// Directions
int X[] = {-1, 0, 0, 1};
int Y[] = {0, 1, -1, 0};

char arr[21][21];

// len : number of dirty tiles + 1
// limit : 2 ^ len -1
// r, c : number of rows and columns
int len, limit, r, c;

// Returns true if current position
// is safe to visit
// else returns false
// Time Complexity : O(1)
bool safe(int x, int y)
{
if (x >= r or y>= c or x<0 or y<0)
return false;
if (arr[x][y] == '#')
return false;
return true;
}

// runs BFS traversal at tile idx
// calulates distance to every cell
// in the grid
// Time Complexity : O(r*c)
void getDist(int idx){

// visited array to track visited cells
bool vis[21][21];
memset(vis, false, sizeof(vis));

// getting current positon
int cx = dirty[idx].first;
int cy = dirty[idx].second;

// initializing queue for bfs
queue < pair < int, int > > pq;
pq.push({cx, cy});

// initializing the dist to max
// because some cells cannot be visited
// by taking source cell as idx
for (int i = 0;i<= r;i++)
for (int j = 0;j<= c;j++)
dist[i][j][idx] = INF;

// base conditions
vis[cx][cy] = true;
dist[cx][cy][idx] = 0;

while (! pq.empty())
{
auto x = pq.front();
pq.pop();
for (int i = 0;i<4;i++)
{
cx = x.first + X[i];
cy = x.second + Y[i];
if (safe(cx, cy))
{
if (vis[cx][cy])
continue;
vis[cx][cy] = true;
dist[cx][cy][idx] = dist[x.first][x.second][idx] + 1;
pq.push({cx, cy});
}
}
}
}

// Dynamic Programming state transition recursion
// with memoization. Time Complexity: O(n*n*2 ^ n)
{
// goal state
return dist[0][0][idx];

int ret = INT_MAX;

// state transiton relation
for (int i = 0;i<len;i++)
{
if ((mask & (1<<i)) == 0)
{
ret = min( ret, solve(i, newMask)
+ dist[dirty[i].first][dirty[i].second][idx]);
}
}

}

void init()
{
// initializing containers
memset(dp, -1, sizeof(dp));
dirty.clear();

// populating dirty tile positions
for (int i = 0;i<r;i++)
for (int j = 0;j<c;j++)
{
if (arr[i][j] == '*')
dirty.push_back({i, j});
}

// inserting ronot's location at the
// begining of the dirty tile
dirty.insert(dirty.begin(), {0, 0});

len = dirty.size();

limit = (1<<len) - 1;

// precalculating distances from all
// dirty tiles to each cell in the grid
for (int i = 0;i<len;i++)
getDist(i);
}

int main(int argc, char const *argv[])
{
// Test case #1:
//     .....*.
//     ...#...
//     .*.#.*.
//     .......

char A[4][7] = { {'.', '.', '.', '.', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'},
{'.', '*', '.', '#', '.', '*', '.'},
{'.', '.', '.', '.', '.', '.', '.'}
};

r = 4; c = 7;

cout << "The given grid : " << endl;

for (int i = 0;i<r;i++)
{
for (int j = 0;j<c;j++)
{
cout << A[i][j] << " ";
arr[i][j] = A[i][j];
}
cout << endl;
}

// - initializitiation
// - precalculations
init();

int ans = solve(0, 1);

cout << "Minimum distance for the given grid : ";
cout << ans << endl;

// Test Case #2
//     ...#...
//     ...#.*.
//     ...#...
//     .*.#.*.
//     ...#...

char Arr[5][7] = { {'.', '.', '.', '#', '.', '.', '.'},
{'.', '.', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'},
{'.', '*', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'}
};

r = 5; c = 7;

cout << "The given grid : " << endl;

for (int i = 0;i<r;i++)
{
for (int j = 0;j<c;j++)
{
cout << Arr[i][j] << " ";
arr[i][j] = Arr[i][j];
}
cout << endl;
}

// - initializitiation
// - precalculations
init();
ans = solve(0, 1);
cout << "Minimum distance for the given grid : ";
if (ans >= INF)
cout << "not possible" << endl;
else
cout << ans << endl;

return 0;
}

r = 5; c = 7;

cout << "The given grid : " << endl;

for (int i = 0;i<r;i++)
{
for (int j = 0;j<c;j++)
{
cout << Arr[i][j] << " ";
arr[i][j] = Arr[i][j];
}
cout << endl;
}

// - initializitiation
// - precalculations
init();
ans = solve(0, 1);
cout << "Minimum distance for the given grid : ";
if (ans >= INF)
cout << "not possible" << endl;
else
cout << ans << endl;

return 0;
}
``````

From engmonsh/gist:5231428

``````/**
* Returns the order to visit predefined products of certain store in minimal distance
* which returns the sequence number to visit these products
*
* @author Ayman Mahgoub
*
*/
public class TravellingSalesMan {
private double[][] distances;
private short minDistances[][], paths[][];
private ArrayList<Integer> products_visit_order;
private int products_number_power, products_number;

public HashMap<Product, Integer> getOrderForVisitingProducts(
ArrayList<Product> products) {
distances = calculateDistanceBetweenProducts(products);

products_number = products.size();
/*
* you represent a subset with a bitmask, which is just an integer. If
* location i is in the subset, bit number i is set in the integer. For
* instance, the subset where location 3 and 4 are visited, is
* represented by the number 24, because bit number 3 (2^3) + bit number
* 4 (2^4) are set.
*
* suppose if i take 4 vertices 1,2,3,4 then if i visit 1->2->3 then
* (2^2)+(2^3) =12 d[1][12] will be the distance from 1->2->3
*
* for 1->3->4 (2^3)+(2^4) =24 d[1][24] will be the distance from
* 1->3->4
*
* SO the matrix length is 2 ^ (product_number)
*/
products_number_power = (int) Math.pow(2, products_number);
minDistances = new short[products_number][products_number_power];
paths = new short[products_number][products_number_power];

for (int i = 0; i < products_number; i++) {
for (int j = 0; j < products_number_power; j++) {
minDistances[i][j] = -1;
paths[i][j] = -1;
}
}

// initialize based on distance matrix
for (int i = 0; i < products_number; i++) {
minDistances[i][0] = 0;
}

// get value of item[0][products_number_power - 2] which indicates that
// we took all the other nodes
getMinTraversingDistance(0, products_number_power - 2, 1);
products_visit_order = new ArrayList<Integer>();

getMinTraversingDistancePath(0, products_number_power - 2);

HashMap<Product, Integer> productsOrder = new HashMap<Product, Integer>();

int i;
for (i = 1; i < products_number - checkout_points_numbers; i++) {
productsOrder.put(products.get(products_visit_order.get(i - 1)), i);
}

minDistances = null;
paths = null;

return productsOrder;
}

private double getMinTraversingDistance(int start, int set, int level) {
double temp = 0, result = -1;
if (minDistances[start][set] != -1) {
return minDistances[start][set];
} else {
for (int x = 0; x < products_number; x++) {
// minus Math.pow(2, x), means you removed this node 'x' from
// my set to try other possibility
mask = products_number_power - 1 - (int) Math.pow(2, x);

temp = distances[start][x]
+ getMinTraversingDistance(x, masked, level + 1);
if (result == -1 || result > temp) {
result = temp;
paths[start][set] = (short) x;
}
}
}
minDistances[start][set] = (short) result;
return result;
}
}

/**
* Gets Visiting sequence by moving backwards from source node '0'
* to destination node
*
* @param start
* @param set
*/
private void getMinTraversingDistancePath(int start, int set) {
if (paths[start][set] == -1) {
return;
}
int x = paths[start][set];
int mask = products_number_power - 1 - (int) Math.pow(2, x);
}

/**
* Calculates all the distances (sum of horizontal and vertical distances)
* between all nodes
*
* @param products
* @return
*/
private double[][] calculateDistanceBetweenProducts(List<Product> products) {
double[][] distances = new double[products.size()][products.size()];
for (int i = 0; i < products.size(); i++) {
for (int j = 0; j < products.size(); j++) {
if (i != j) {
double distance = Math.abs(products.get(i)
.getAverageLocation().x
- products.get(j).getAverageLocation().x)
+ Math.abs(products.get(i).getAverageLocation().y
- products.get(j).getAverageLocation().y);
distances[i][j] = distance;
}
}
}
return distances;
}
}
``````

In C and C++ (by Neeraj Mishra):

``````
#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;

void takeInput()
{
int i,j;

printf("Enter the number of villages: ");
scanf("%d",&n);

printf("\nEnter the Cost Matrix\n");

for(i=0;i < n;i++)
{
printf("\nEnter Elements of Row: %d\n",i+1);

for( j=0;j < n;j++)
scanf("%d",&ary[i][j]);

completed[i]=0;
}

printf("\n\nThe cost list is:");

for( i=0;i < n;i++)
{
printf("\n");

for(j=0;j < n;j++)
printf("\t%d",ary[i][j]);
}
}

void mincost(int city)
{
int i,ncity;

completed[city]=1;

printf("%d--->",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=ary[city][ncity];

return;
}

mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;

for(i=0;i < n;i++)
{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}

if(min!=999)
cost+=kmin;

return nc;
}

int main()
{
takeInput();

printf("\n\nThe Path is:\n");
mincost(0); //passing 0 because starting vertex

printf("\n\nMinimum cost is %d\n ",cost);

return 0;
}
``````

Branch And Bound | Set 6 (Traveling Salesman Problem): https://www.geeksforgeeks.org/branch-bound-set-5-traveling-salesman-problem/