Dynamic Programming
Last updated
Was this helpful?
Last updated
Was this helpful?
Dynamic Programming: Using tablulated space to avoid repeated recursive call.
Traveling Sales Man (TSP) problem Template:
#include <bits/stdc++.h>
using namespace std;
#define INF 99999999
#define MAXR 12
#define MAXC 12
#define MAXMASK 2048
#define MAXHOUSE 12
// stores distance taking souce
// as every dirty tile
int dist[MAXR][MAXC][MAXHOUSE];
// memoization for dp states
int dp[MAXHOUSE][MAXMASK];
// 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)
int solve(int idx, int mask)
{
// goal state
if (mask == limit)
return dist[0][0][idx];
// if already visited state
if (dp[idx][mask] != -1)
return dp[idx][mask];
int ret = INT_MAX;
// state transiton relation
for (int i = 0;i<len;i++)
{
if ((mask & (1<<i)) == 0)
{
int newMask = mask | (1<<i);
ret = min( ret, solve(i, newMask)
+ dist[dirty[i].first][dirty[i].second][idx]);
}
}
// adding memoization and returning
return dp[idx][mask] = ret;
}
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();
// calculating LIMIT_MASK
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 MAXMASK 2048
#define MAXHOUSE 12
// stores distance taking souce
// as every dirty tile
int dist[MAXR][MAXC][MAXHOUSE];
// memoization for dp states
int dp[MAXHOUSE][MAXMASK];
// 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)
int solve(int idx, int mask)
{
// goal state
if (mask == limit)
return dist[0][0][idx];
// if already visited state
if (dp[idx][mask] != -1)
return dp[idx][mask];
int ret = INT_MAX;
// state transiton relation
for (int i = 0;i<len;i++)
{
if ((mask & (1<<i)) == 0)
{
int newMask = mask | (1<<i);
ret = min( ret, solve(i, newMask)
+ dist[dirty[i].first][dirty[i].second][idx]);
}
}
// adding memoization and returning
return dp[idx][mask] = ret;
}
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();
// calculating LIMIT_MASK
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;
}/**
* 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;
int masked, mask;
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);
masked = set & mask;
if (masked != set) {
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);
int masked = set & mask;
products_visit_order.add(x);
getMinTraversingDistancePath(x, masked);
}
/**
* 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;
}
}#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;
}From /
(by Neeraj Mishra):
Branch And Bound | Set 6 (Traveling Salesman Problem):