-
-
Save jgcoded/d7ecba7aa3e210419471 to your computer and use it in GitHub Desktop.
#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; | |
} |
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 ?
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?