Minimum Hamiltonian cycles for each subset of graph vertices

(BUT). First, we solve the problem of finding the minimum length of all simple cycles containing a vertex zero (numbering of vertices from zero). We use dynamic programming . We will consider simple paths from vertex zero to vertex i :

0 = v 1 → v 2 → ... → v k-1 → v k = i

It does not matter to us in which order the vertices were visited, so it will store only the bit mask of the vertices visited (that is, the mask number is from zero (inclusive) to 2 the ^{number of vertices} (non-inclusive), such that its i -th bit equals one i ). Let's get a two-dimensional array:

dp[i][mask] is the minimum length of a simple path from vertex zero to vertex i passing through the vertices specified by the bit mask mask .

Initially, dp[0][2 0 ] = 0 , the remaining elements are equal to infinity. Let's make the dynamics forward: we will go through the last vertex and mask of the visited vertices and try to go to each of the unvisited vertices. We will also update the answer - by closing the path, that is, adding an edge to the последняя вершина → стартовая вершина .

It works for O(n 2 * 2 n )

(B) Now we solve the original problem. It would be possible to go over each vertex and solve the problem (A) with this vertex as the starting point, we would have O( n 3 * 2 n ) .

But so the answer for each subset will be considered several times - once for each vertex that is included in the subset (when this vertex was the original one). You can avoid this by making sure that for each subset there is a selected source vertex. For example, you can take the vertex with the maximum number as it.

Thus, we will iterate through each vertex, run the algorithm from point (A) with this vertex as the starting point, but we will consider only the paths that pass through the vertices with numbers less than the numbers of the starting vertex. So we will ensure that the answer for each subset will be counted once.

It works for = O(n 2 * 2 n )

 #include <iostream> #include <vector> using namespace std; int main() { // считаем что граф является полным и вводится с клавиатуры, // сначала число вершин n, // затем матрица смежности графа (квадратная матрица размера n) int number_vertexes; cin >> number_vertexes; vector<vector<double>> distances(number_vertexes, vector<double>(number_vertexes)); for (vector<double> &line : distances) { for (double &distance : line) { cin >> distance; } } // подмножество задаётся битовой маской из диапозона [0, 2^n) // i-ый бит равен единице ↔ вершина i входит в подмножество int mask_count = 1 << number_vertexes; const double max_double = numeric_limits<double>::max(); // answer[mask] == ответ для подмножества, задаваемого mask vector<double> answer(mask_count, max_double); // ответ для пустого подмножества точек --- ноль answer[0] = 0; for (int start_point = 0; start_point < number_vertexes; ++start_point) { // чтобы не считать ответ для каждой подмаски много раз // выберем для каждой подмаски стартовой вершниу --- вершину с наибольшим номером // таким образом для стартовой вершины i можем считать что существуют только вершины [0..i-1] // это значительно ускорит перебор int number_points_current = start_point + 1; int mask_count_current = 1 << number_points_current; // для каждой вершины start_point посчитаем динамику: // dp[i][mask] --- минимальная длина простого пути из вершины start_point в вершину i, // проходящего через вершины, задаваемые битовой маской mask // (start_point и i входят в mask) vector<vector<double>> dp(number_points_current, vector<double>(mask_count_current, max_double)); dp[start_point][1 << start_point] = 0; // динамика вперёд: перебираем последнюю вершину и маску посещённых вершин, for (int mask = 0; mask < mask_count_current; ++mask) { for (int last_point = 0; last_point < number_points_current; ++last_point) { // если существует путь из начальной вершины в последнюю if (dp[last_point][mask] != max_double) { // пытаемся пойти из последней вершину в каждую, ещё не посещённую for (int next_point = 0; next_point < number_points_current; ++next_point) { if ((mask & (1 << next_point)) == 0) { int next_mask = mask | (1 << next_point); double next_distance = dp[last_point][mask] + distances[last_point][next_point]; dp[next_point][next_mask] = min(dp[next_point][next_mask], next_distance); } } // пытаемся пойти из последней вершину в стартовую, то есть замкнуть путь double next_distance = dp[last_point][mask] + distances[last_point][start_point]; answer[mask] = min(answer[mask], next_distance); } } } } // как-нибудь используем полученный массив answer return 0; }