How to track path in Travelling Salesman Problem solved using DP and bitmasking

Question

I wrote code to solve TSP (Travelling Salesman Problem) using DP, but I can't figure out how can I track the path that gives the solution.

That's code:

static int tsp(std::vector<std::vector<int>> const& dist, size_t current, uint64_t mask, std::vector<std::vector<int>>& dp) {
    if (mask == ((size_t)1 << dist.size()) - 1)
        return dist[current][0];

    if (dp[mask][current] != -1)
        return dp[mask][current];

    int result = INT_MAX;
    for (uint64_t i = 0; i < dist.size(); ++i) {
        uint64_t val = (uint64_t)1 << i;
        if (mask & val)
            continue;

        int sub = dist[current][i] + tsp(dist, i, mask | val, dp);
        result = std::min(result, sub);
    }

    dp[mask][current] = result;
    return result;
}

int main()
{
    std::vector<std::vector<int>> dist{
        {0, 10, 41, 31},
        {10, 0, 30, 19},
        {41, 30, 0, 20},
        {31, 19, 20, 0}
    };

    std::vector<std::vector<int>> dp(1 << dist.size(), std::vector<int>(dist.size(), -1));
    std::cout << (tsp(dist, 0, 1, dp) == 90);
}

I tried to pass std::vector<int>& path as tsp parameter and working with it by path[i] = current when I have better result than current for i node, but it doesn't work. I think it doesn't because the best result for some moment is not the best for whole solution (e.g. whole solution may visit nodes in different order and they can not be revisited).

You may wonder how this code check if node is visited. I do it by bitmasking, the process may look like this (for 4 nodes A,B,C,D):

The graph from main:

The expected path is: 0-1-3-2-0 (cost equal to 90)

So how can I track the path that gives optimal solution in TSP problem?

Answer 1

You could add a parameter (let's call it link) for collecting the best neighbor for a given mask and node. So it would have the same type as dp.

Then after tsp has run, you can use this data structure to reconstruct the path.

Here is your code with the necessary additions:

static int tsp(std::vector<std::vector<int>> const& dist, 
                size_t current, uint64_t mask, 
                std::vector<std::vector<int>>& dp,
                std::vector<std::vector<int>>& link) { // new parameter
    if (mask == ((size_t)1 << dist.size()) - 1)
        return dist[current][0];
    if (dp[mask][current] != -1)
        return dp[mask][current];

    int result = INT_MAX;
    for (uint64_t i = 0; i < dist.size(); ++i) {
        uint64_t val = (uint64_t)1 << i;
        if (mask & val)
            continue;

        // Pass extra argument in recursive call
        int sub = dist[current][i] + tsp(dist, i, mask | val, dp, link);
        if (sub < result) {
            result = sub;
            link[mask][current] = i; // Register which neighbor was best
        }
    }

    dp[mask][current] = result;
    return result;
}

// Function to translate `link` into a path, assuming 0 is starting node
static std::vector<int> getpath(std::vector<std::vector<int>>& link) {
    size_t current = 0;
    uint64_t mask = 0;
    std::vector<int> path;
    for (int i = 0; i < link[0].size(); i++) {
        path.push_back(current);
        mask |= 1 << current;
        current = link[mask][current];
    }
    return path;
}

int main() {
    std::vector<std::vector<int>> dist{
        {0, 10, 41, 31},
        {10, 0, 30, 19},
        {41, 30, 0, 20},
        {31, 19, 20, 0}
    };

    std::vector<std::vector<int>> dp(1 << dist.size(), std::vector<int>(dist.size(), -1));
   std::vector<std::vector<int>> link(1 << dist.size(), std::vector<int>(dist.size(), 0));

    int res  = tsp(dist, 0, 1, dp, link);
    std::vector<int> path = getpath(link);
    std::cout << "result " << res << "\n";
    for (auto i : path)
        std::cout << i << " ";
    std::cout << "\n";
}

Note that your code assumes that 0 is the starting node (see base case), so I used the same assumption in getpath.