Минимальный гамильтонов циклов для каждого подмножества вершин графа

Имеется граф с n вершинами, необходимо для каждого подмножества вершин (всего 2n подмножеств) найти длину минимального простого цикла, проходящего через каждую вершину подмножества.

Ответ

(А). Сначала решим задачу нахождения минимальной длины всех простых циклов, содержащих вершину ноль (нумерация вершин с нуля). Воспользуемся динамическим программированием. Будем рассматривать простые пути из вершины ноль в вершину i
0 = v1 → v2 → ... → vk-1 → vk = i
Нам не важно в каком именно порядке были посещены вершин, поэтому будет хранить только битовую маску посещённых вершин (то есть число mask от нуля (включительно) до 2число вершин (невключительно), такое что его i-ый бит равен единице ⇔ была посещена вершина i). Заведём двумерный массив:
dp[i][mask] — минимальная длина простого пути из вершины ноль в вершину i, проходящего через вершины, задаваемые битовой маской mask
Изначально dp[0][20] = 0, остальные элементы равны бесконечности. Сделаем динамику вперёд: будем перебирать последнюю вершину и маску посещённых вершин и пытаться пойти в каждую из непосещённых вершин. Также будем обновлять ответ — путём замыкания пути, то есть добавления ребра последняя вершина → стартовая вершина
Работает это за O(n2 * 2n)

(Б). Теперь решим исходную задачу. Можно было бы перебрать каждую вершину и решить задачу (А) с этой вершиной в качестве стартовой, получилось бы O(n3 * 2n)
Но так ответ для каждого подмножества будет считаться несколько раз — по разу для каждой вершины, входящей в подмножество (когда эта вершина была исходной). Можно этого избежать, сделав так, чтобы для каждого подмножества была выделенная исходная вершина. Например, в качестве неё можно взять вершину с максимальным номером.
Таким образом, мы будем перебирать каждую вершину, запускать алгоритм из пункта (А) с этой вершиной в качестве стартовой, но будем рассматривать только пути, проходящие через вершины с номерами меньшими номера стартовой вершины. Так мы обеспечим, что ответ для каждого подмножества будет подсчитан один раз.
Работает это за = O(n2 * 2n)

#include #include using namespace std;
int main() { // считаем что граф является полным и вводится с клавиатуры, // сначала число вершин n, // затем матрица смежности графа (квадратная матрица размера n) int number_vertexes; cin >> number_vertexes; vector> distances(number_vertexes, vector(number_vertexes)); for (vector &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::max(); // answer[mask] == ответ для подмножества, задаваемого mask vector 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> dp(number_points_current, vector(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; }