ДП по Битовой МаскеBitmask DP

Задача коммивояжёра: дано n городов и матрица попарных расстояний dist[i][j], нужно найти маршрут минимальной длины, посещающий каждый город ровно один раз и возвращающийся в стартовый город. Наивный перебор всех перестановок городов — O(n!). Ключевое наблюдение Хелда—Карпа (1962): для вычисления оптимального продолжения маршрута не нужно помнить весь порядок посещения городов — достаточно знать МНОЖЕСТВО уже посещённых городов и город, в котором маршрут сейчас находится. Это резко сокращает число различных состояний: вместо n! разных порядков — всего 2ⁿ·n пар (множество, текущий город).The traveling salesman problem: given n cities and a pairwise distance matrix dist[i][j], find the minimum-length route visiting every city exactly once and returning to the starting city. A naive brute-force search over all city permutations is O(n!). Held and Karp's key observation (1962): computing the optimal continuation of a route doesn't require remembering the entire visiting order — knowing the SET of already-visited cities and the city the route is currently at is enough. This drastically cuts the number of distinct states: instead of n! different orderings, there are only 2ⁿ·n pairs (set, current city).

Состояние dp[mask][i] — минимальная стоимость маршрута, который начинается в фиксированном городе 0, посещает ровно множество городов, закодированное битовой маской mask (бит k установлен, если город k посещён), и заканчивается в городе i (обязательно i ∈ mask). Переход: dp[mask][i] = min по всем j ∈ mask, j≠i от (dp[mask без i][j] + dist[j][i]) — маршрут в состояние (mask, i) получен из состояния (mask без города i, j) добавлением последнего перехода j→i. Базовый случай: dp[{0}][0] = 0 (только стартовый город, стоимость 0). Порядок заполнения — по возрастанию числа установленных битов в mask (popcount), потому что переход всегда идёт от маски с на один город меньше к маске с текущим городом добавленным. Ответ на задачу — min по всем i≠0 от dp[full_mask][i] + dist[i][0] (замкнуть маршрут возвращением в город 0), где full_mask — маска со всеми n битами установленными.The state dp[mask][i] is the minimum cost of a route that starts at a fixed city 0, visits exactly the set of cities encoded by the bitmask mask (bit k set if city k is visited), and ends at city i (necessarily i ∈ mask). The transition: dp[mask][i] = min over all j ∈ mask, j≠i of (dp[mask without i][j] + dist[j][i]) — the route to state (mask, i) is obtained from state (mask without city i, j) by adding the final transition j→i. The base case: dp[{0}][0] = 0 (only the starting city, cost 0). The fill order proceeds by increasing popcount of mask, because the transition always moves from a mask with one fewer city to a mask with the current city added. The answer to the problem is the min over all i≠0 of dp[full_mask][i] + dist[i][0] (close the route by returning to city 0), where full_mask is the mask with all n bits set.

Восстановление самого маршрута — обратный проход, аналогичный другим статьям: для каждого (mask, i) хранится, какой j дал минимум при переходе, и, начиная с лучшего конечного i при full_mask, последовательно снимаются биты по цепочке parent[mask][i] = j, пока маска не станет содержать только город 0.Reconstructing the actual route is a backward pass, similar to other articles: for each (mask, i), the j that produced the minimum at the transition is stored, and starting from the best final i at full_mask, bits are peeled off one by one following the chain parent[mask][i] = j, until the mask contains only city 0.

Важная честная оговорка: O(2ⁿ·n²) — огромный прогресс по сравнению с O(n!), но это всё ещё ЭКСПОНЕНЦИАЛЬНОЕ время, а не полиномиальное. ДП по битовой маске не превращает NP-трудную задачу в полиномиальную — она превращает практически безнадёжный перебор в задачу, решаемую точно для малых и средних n (реалистично — до 20-22 городов при разумных ограничениях по памяти, поскольку сама таблица dp занимает O(2ⁿ·n) памяти). За пределами этого диапазона точное решение через битовую маску так же непрактично, как и полный перебор, и нужны эвристики или приближённые алгоритмы.An important honest caveat: O(2ⁿ·n²) is enormous progress over O(n!), but it's still EXPONENTIAL time, not polynomial. Bitmask DP doesn't turn an NP-hard problem into a polynomial one — it turns a practically hopeless brute force into a problem solvable exactly for small and medium n (realistically up to around 20-22 cities under reasonable memory constraints, since the dp table itself takes O(2ⁿ·n) memory). Beyond that range, the exact bitmask solution is just as impractical as brute force, and heuristics or approximation algorithms are needed instead.

// dp[mask][i]: минимальная стоимость посетить mask, закончив в i; город 0 — старт// dp[mask][i]: min cost to visit mask, ending at i; city 0 is the start
int tspHeldKarp(std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    int FULL = 1 << n;
    std::vector<std::vector<int>> dp(FULL, std::vector<int>(n, INF));
    dp[1][0] = 0;                                    // только город 0 посещён// only city 0 visited
    for (int mask = 1; mask < FULL; mask++)
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i)) || dp[mask][i] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;    // j ещё не посещён// j not yet visited
                int nmask = mask | (1 << j);
                dp[nmask][j] = std::min(dp[nmask][j], dp[mask][i] + dist[i][j]);
            }
        }
    int best = INF;
    for (int i = 1; i < n; i++) best = std::min(best, dp[FULL-1][i] + dist[i][0]);
    return best;                                    // O(2^n · n^2)// O(2^n · n^2)
}

4-5 городов на плоскости — демонстрация проигрывает заполнение таблицы dp[mask][i] в порядке возрастания числа городов в mask (popcount), подсвечивая текущую маску как множество цветных городов-узлов, а затем восстанавливает оптимальный маршрут обратным проходом.4-5 cities in the plane — the demo auto-plays filling the dp[mask][i] table in order of increasing city count in mask (popcount), highlighting the current mask as a set of colored city nodes, then reconstructs the optimal tour with a backward pass.