# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 1 |
2022-10-01 00:37
|
An \(O(n^2 2^n)\) dynamic programming solution that uses \(O(n 2^n)\) memory. It's basically implementation of the Held-Karp algorithm.
#include<vector>
#include<tuple>
#include<algorithm>
#include<limits>
struct TravellingSalesmanGraph {
int num_vertices_;
std::vector<std::vector<int> > edges_;
std::vector<std::vector<int> > min_path_last_vertex_;
std::vector<std::vector<int> > min_path_;
// Format: min_path_[vertex_set_explored][last_vertex]
// State giving the cost of the minimum path/cycle that has explored a certain set of vertices and reached a
// certain end vertex. Start is at nothing explored and at vertex 0.
// vertex_set_explored - Bit field of the vertices we have already traversed. No. of possible values: 2^n
// last_vertex - The current vertex we are on. No. of possible values: n
TravellingSalesmanGraph(int num_vertices) {
num_vertices_ = num_vertices;
// Initialize edges with very large weights to denote that they are impassable
edges_.resize(num_vertices, std::vector<int>(num_vertices, std::numeric_limits<int>::max()));
}
void add_edge(int a, int b, int w) {
// Adds an undirected edge between a and b of weight w. Assumes vertixes are numbered from 0
edges_[a][b] = w;
edges_[b][a] = w;
}
std::pair<int, std::vector<int> > find_travelling_salesman_cycle() {
min_path_.resize(1 << num_vertices_, std::vector<int>(num_vertices_, std::numeric_limits<int>::max()));
min_path_last_vertex_.resize(1 << num_vertices_, std::vector<int>(num_vertices_, -1));
min_path_[0][0] = 0; // Our starting point
// Iterating over sets this way guarantees we explore smaller sets first
for(unsigned int explored_set = 0; explored_set < (1U << num_vertices_); explored_set++) {
for(int last_vertex = 0; last_vertex < num_vertices_; last_vertex++)
if(min_path_[explored_set][last_vertex] != std::numeric_limits<int>::max()) { // Valid state?
for(int next_vertex = 0; next_vertex < num_vertices_; next_vertex++)
if(
edges_[last_vertex][next_vertex] != std::numeric_limits<int>::max() // Edge exists
&& (explored_set & (1U << next_vertex)) == 0 // We don't go back to already explored vertex
) {
// Perform the traversal and see if we find a new shortest path/cycle to the destination state
const unsigned int next_set = explored_set + (1U << next_vertex);
const int next_cost = min_path_[explored_set][last_vertex] + edges_[last_vertex][next_vertex];
if(next_cost < min_path_[next_set][next_vertex]) {
min_path_[next_set][next_vertex] = next_cost;
min_path_last_vertex_[next_set][next_vertex] = last_vertex;
}
}
}
}
int result_cost = min_path_[(1 << num_vertices_) - 1][0];
std::vector<int> cycle = {0};
if (result_cost != std::numeric_limits<int>::max()) {
int cur_state = (1 << num_vertices_) - 1;
int cur_vertex = 0;
while(cur_state > 0) { // Traverse back the minimum cycle
int prev_vertex = min_path_last_vertex_[cur_state][cur_vertex];
cur_state -= (1 << cur_vertex);
cur_vertex = prev_vertex;
cycle.push_back(cur_vertex);
}
std::reverse(cycle.begin(), cycle.end());
}
return std::make_pair(min_path_[(1 << num_vertices_) - 1][0], cycle); // The state corresponding to having traversed the cycle
}
};
int main() {
TravellingSalesmanGraph graph(4);
graph.add_edge(0, 1, 4);
graph.add_edge(1, 2, 5);
graph.add_edge(2, 3, 4);
graph.add_edge(3, 0, 6);
graph.add_edge(0, 2, 1);
graph.add_edge(1, 3, 2);
int min_tsp_cycle_cost;
std::vector<int> min_tsp_cycle;
std::tie(min_tsp_cycle_cost, min_tsp_cycle) = graph.find_travelling_salesman_cycle();
return 0;
}
Over here, we use bitwise operators to keep track of the sets of vertices we have explored (&
, <<
). You can read more about them here:
Bitwise Operators in C/C++ - geeksforgeeks.org
The algorithm used:
Held–Karp algorithm - wikipedia.org
classes | ||
std::numeric_limits |
en.cppreference.com | cplusplus.com |
std::pair |
en.cppreference.com | cplusplus.com |
std::vector |
en.cppreference.com | cplusplus.com |
functions | ||
std::make_pair |
en.cppreference.com | cplusplus.com |
std::max |
en.cppreference.com | cplusplus.com |
std::numeric_limits::max |
en.cppreference.com | cplusplus.com |
std::reverse |
en.cppreference.com | cplusplus.com |
std::tie |
en.cppreference.com | cplusplus.com |
std::vector::resize |
en.cppreference.com | cplusplus.com |
std::vector::vector |
en.cppreference.com | cplusplus.com |
Create a solution for the Travelling Salesman Problem, that is, given a graph, find a minimum total weight cycle that goes through each of its vertices exactly once. Optimize for average or worst-case time complexity and describe said performance characteristic in your sample.
For comprehensibility, the implementation should construct some graph and then find the solution to the given problem on it.