Problema del vendedor ambulante | Set 1 (Programación Ingenua y Dinámica)

Problema del viajante de comercio (TSP): 

Dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema del ciclo hamiltoniano es encontrar si existe un recorrido que visite cada ciudad exactamente una vez. Aquí sabemos que existe el recorrido hamiltoniano (porque el gráfico está completo) y, de hecho, existen muchos recorridos de este tipo, el problema es encontrar un ciclo hamiltoniano de peso mínimo. 

n = 4  # there are four nodes in example graph (graph is 1-based)
  
# 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
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
memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]
  
  
def fun(i, mask):
    # base case
    # if only ith bit and 1st bit is set in our mask,
    # it implies we have visited all other nodes already
    if mask == ((1 << i) | 3):
        return dist[1][i]
  
    # memoization
    if memo[i][mask] != -1:
        return memo[i][mask]
  
    res = 10**9  # result of this sub-problem
  
    # we have to travel all nodes j in mask and end the path at ith node
    # so for every node j in mask, recursively calculate cost of 
    # travelling all nodes in mask
    # except i and then travel back from node j to node i taking 
    # the shortest path take the minimum of all possible j nodes
    for j in range(1, n+1):
        if (mask & (1 << j)) != 0 and j != i and j != 1:
            res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i])
    memo[i][mask] = res  # storing the minimum value
    return res
  
  
# Driver program to test above logic
ans = 10**9
for i in range(1, n+1):
    # try to go from node 1 visiting all nodes in between to i
    # then return from i taking the shortest route to 1
    ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])
  
print("The cost of most efficient tour = " + str(ans))
  
# This code is contributed by Serjeel Ranjan

#include <iostream>
  
using namespace std;
  
// there are four nodes in example graph (graph is 1-based)
const int n = 4;
// give appropriate maximum to avoid overflow
const 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
int dist[n + 1][n + 1] = {
    { 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
int memo[n + 1][1 << (n + 1)];
  
int fun(int i, int mask)
{
    // base case
    // if only ith bit and 1st bit is set in our mask,
    // it implies we have visited all other nodes already
    if (mask == ((1 << i) | 3))
        return dist[1][i];
    // memoization
    if (memo[i][mask] != 0)
        return memo[i][mask];
  
    int res = MAX; // result of this sub-problem
  
    // we have to travel all nodes j in mask and end the
    // path at ith node so for every node j in mask,
    // recursively calculate cost of travelling all nodes in
    // mask except i and then travel back from node j to
    // node i taking the shortest path take the minimum of
    // all possible j nodes
  
    for (int j = 1; j <= n; j++)
        if ((mask & (1 << j)) && j != i && j != 1)
            res = std::min(res, fun(j, mask & (~(1 << i)))
                                    + dist[j][i]);
    return memo[i][mask] = res;
}
// Driver program to test above logic
int main()
{
    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 = std::min(ans, fun(i, (1 << (n + 1)) - 1)
                                + dist[i][1]);
  
    printf("The cost of most efficient tour = %d", ans);
  
    return 0;
}
  
// This code is contributed by Serjeel Ranjan

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)
    {
        // base case
        // if only ith bit and 1st bit is set in our mask,
        // it implies we have visited all other nodes
        // already
        if (mask == ((1 << i) | 3))
            return dist[1][i];
        // memoization
        if (memo[i][mask] != 0)
            return memo[i][mask];
  
        int res = MAX; // result of this sub-problem
  
        // we have to travel all nodes j in mask and end the
        // path at ith node so for every node j in mask,
        // recursively calculate cost of travelling all
        // nodes in mask
        // except i and then travel back from node j to node
        // i taking the shortest path take the minimum of
        // all possible j nodes
  
        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);
    }
}
  
// This code is contributed by Serjeel Ranjan