Traveling Salesman solution in c++ - dynamic programming solution with O(n^2 * 2^n).

traveling_salesman.cpp

#include <vector>
#include <iostream>

using namespace std;

/**
    \brief Given a complete, undirected, weighted graph in the form of an adjacency matrix,
           returns the smallest tour that visits all nodes and starts and ends at the same
           node. This dynamic programming solution runs in O(n^2 * 2^n).

    \return the minimum cost to complete the tour
*/
int tsp(const vector<vector<int>>& cities, int pos, int visited, vector<vector<int>>& state)
{
    if(visited == ((1 << cities.size()) - 1))
        return cities[pos][0]; // return to starting city

    if(state[pos][visited] != INT_MAX)
        return state[pos][visited];

    for(int i = 0; i < cities.size(); ++i)
    {
        // can't visit ourselves unless we're ending & skip if already visited
        if(i == pos || (visited & (1 << i)))
            continue;

        int distance = cities[pos][i] + tsp(cities, i, visited | (1 << i), state);
        if(distance < state[pos][visited])
            state[pos][visited] = distance;
    }

    return state[pos][visited];
}

int main()
{
    vector<vector<int>> cities = { { 0, 20, 42, 35 },
                                   { 20, 0, 30, 34 },
                                   { 42, 30, 0, 12 },
                                   { 35, 34, 12, 0 }
                                 };

    vector<vector<int>> state(cities.size());
    for(auto& neighbors : state)
        neighbors = vector<int>((1 << cities.size()) - 1, INT_MAX);

    cout << "minimum: " << tsp(cities, 0, 1, state) << endl;

    return 0;
}

You have not added header file for INT_MAX which is 'limits.h'.

How do I print out the Traveling Salesman path?

How do I print out the Traveling Salesman path?

for print them "state" must be <int , vector > first param is minimum cost and vector is path and recursively we add it to vector

I have been trying to see how can I get the path... but still no clue where it is stored. Could you write some code?

It's worth to notice that the visited in tsp means "dfs procedure visited this point", which is exactly opposite to "which point has been counted in the cost function" corresponding to this bitset.

@VictorRubia store/update the route in tsp function when distance < state[pos][visited] happens. You'd better find some code which print shortest path's route and adopt that here. It's the same technique.

It's also worth notice that this code runs at O(N^2 * 2^N). DFS need to process each state and the state count is `possibility_of(pos) * possibility_of(state) = n * 2^n. And inside each DFS you do a O(n) scan to find the next point to visit.

I have been trying to see how can I get the path... but still no clue where it is stored. Could you write some code?

So did u get how to find the path ?