Dynamic Programming

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 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;
}

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;
        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;
    }
}

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/