ДП по подмножествам (битовые маски): разбор с задачей коммивояжёра

Коротко

ДП по подмножествам применяется там, где нужен перебор всех сочетаний, а элементов немного. Ограничение жёсткое: при n = 25 уже 33 миллиона состояний, при n = 30 — миллиард.

Идея: подмножество как число

Любое подмножество набора из n элементов кодируется числом от 0 до 2ⁿ − 1. Единичный бит на позиции i означает «элемент i входит в подмножество».

элементы:  A  B  C  D
маска 5 =  0  1  0  1  (двоичное 0101)
           ↑     ↑
подмножество {A, C}

Отсюда все операции над множествами становятся битовыми:

mask | (1 << i)      # добавить элемент i
mask & ~(1 << i)     # удалить элемент i
mask & (1 << i)      # проверить наличие элемента i
mask ^ (1 << i)      # переключить
bin(mask).count('1') # размер подмножества
mask == (1 << n) - 1 # все элементы на месте

Число как ключ состояния — это и есть весь приём. Массив dp размером 2ⁿ индексируется маской напрямую.

Классика: задача коммивояжёра

Есть n городов и матрица расстояний. Нужно объехать все города по одному разу и вернуться в начальный, минимизировав путь.

Полный перебор — n! маршрутов. При n = 15 это триллион. ДП по маскам сводит задачу к 2ⁿ · n состояний, то есть примерно 500 тысяч — разница колоссальная.

Состояние: dp[mask][last] — минимальная длина пути, который начался в городе 0, посетил ровно города из mask и закончился в городе last.

Переход: из состояния (mask, last) идём в непосещённый город next:

dp[mask | (1<<next)][next] = min(..., dp[mask][last] + dist[last][next])

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float('inf')
    full = (1 << n) - 1

    # dp[mask][last]
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0        # стартуем в городе 0, посещён только он

    for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == INF:
                continue
            if not mask & (1 << last):
                continue          # last обязан быть в маске

            for nxt in range(n):
                if mask & (1 << nxt):
                    continue      # уже посещён

                new_mask = mask | (1 << nxt)
                candidate = dp[mask][last] + dist[last][nxt]
                if candidate < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = candidate

    # замыкаем маршрут возвратом в город 0
    return min(dp[full][last] + dist[last][0] for last in range(1, n))


dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]

print(tsp(dist))   # 80  → маршрут 0-1-3-2-0

Сложность — O(2ⁿ · n²): состояний 2ⁿ · n, из каждого n переходов.

Восстановление маршрута

Добавим массив предшественников.

def tsp_with_path(dist: list[list[int]]):
    n = len(dist)
    INF = float('inf')
    full = (1 << n) - 1

    dp = [[INF] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == INF or not mask & (1 << last):
                continue
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                new_mask = mask | (1 << nxt)
                cand = dp[mask][last] + dist[last][nxt]
                if cand < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = cand
                    parent[new_mask][nxt] = last

    # находим лучшее замыкание
    best_last = min(range(1, n), key=lambda l: dp[full][l] + dist[l][0])
    total = dp[full][best_last] + dist[best_last][0]

    # разматываем путь
    path = [0]
    mask, last = full, best_last
    while last != -1:
        path.append(last)
        prev = parent[mask][last]
        mask ^= (1 << last)
        last = prev

    return total, path[::-1]


print(tsp_with_path(dist))   # (80, [0, 1, 3, 2, 0])

Перебор всех подмасок маски

Ещё один важный приём: иногда нужно перебрать все подмножества данного подмножества. Например, в задаче о разбиении на группы.

submask = mask
while submask:
    # обрабатываем submask
    submask = (submask - 1) & mask

Идиома (submask - 1) & mask выглядит загадочно, но делает ровно нужное: переходит к следующей подмаске в порядке убывания.

Неочевидный факт: суммарное число подмасок по всем маскам равно 3ⁿ, а не 4ⁿ. Каждый элемент независимо находится в одном из трёх состояний — не в маске, в маске но не в подмаске, в подмаске. Это делает алгоритмы вида «для каждой маски перебрать подмаски» приемлемыми при n ≤ 18.

def min_partition_cost(n: int, cost: dict) -> int:
    """Разбить множество на группы с минимальной суммарной стоимостью."""
    full = (1 << n) - 1
    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0

    for mask in range(1, 1 << n):
        submask = mask
        while submask:
            if submask in cost:
                rest = mask ^ submask
                if dp[rest] != INF:
                    dp[mask] = min(dp[mask], dp[rest] + cost[submask])
            submask = (submask - 1) & mask

    return dp[full]

Полезные битовые приёмы

mask & -mask                  # младший единичный бит
mask & (mask - 1)             # сбросить младший единичный бит
(mask & (mask - 1)) == 0      # маска — степень двойки (один элемент)
bin(mask).count('1')          # количество элементов
mask.bit_count()              # то же, Python 3.10+, быстрее
full ^ mask                   # дополнение подмножества

bit_count() появился в Python 3.10 и работает заметно быстрее подсчёта через строку — в горячем цикле разница заметна.

Типичные задачи

Задача коммивояжёра — разобрана выше.

Назначение работников на задачи. dp[mask] — минимальная стоимость, если задачи из mask уже розданы. Работник определяется числом единиц в маске.

def assignment(cost: list[list[int]]) -> int:
    n = len(cost)
    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        worker = bin(mask).count('1')      # следующий свободный работник
        if worker == n:
            continue
        for task in range(n):
            if not mask & (1 << task):
                new_mask = mask | (1 << task)
                dp[new_mask] = min(dp[new_mask], dp[mask] + cost[worker][task])

    return dp[(1 << n) - 1]


print(assignment([[9, 2, 7], [6, 4, 3], [5, 8, 1]]))   # 10

Гамильтонов путь — существует ли маршрут через все вершины. Тот же каркас, что и коммивояжёр, но без весов.

Раскраска графа в минимальное число цветов — перебор независимых множеств.

Разбиение множества на подмножества с ограничениями.

Когда приём не подходит

Ограничение по n жёсткое и обойти его нельзя:

Если в задаче n больше 25, ДП по маскам почти наверняка не то решение — ищите другую структуру: жадность, поток, или динамику по другому параметру.

Обратная подсказка: если в условии n ≤ 20, это сильный намёк на битовые маски. Такое маленькое ограничение редко бывает случайным.

Частые ошибки

Приоритет операторов. В Python & имеет более низкий приоритет, чем ==. Выражение mask & 1 << i == 0 разберётся неправильно. Всегда ставьте скобки: (mask & (1 << i)) == 0.

Проверка if mask & (1 << i) как булевой. Работает в Python, но возвращает не 0/1, а само значение бита. При сравнении с True даст неверный результат.

Забытая проверка, что last входит в mask. Без неё обрабатываются несуществующие состояния, и ответ портится.

Неверный порядок обхода масок. Переходы должны идти от масок с меньшим числом бит к большим. Обычный цикл for mask in range(1 << n) это обеспечивает, потому что добавление бита всегда увеличивает число.

Память. dp размером 2²⁰ × 20 из Python-объектов займёт сотни мегабайт. При больших n используйте array или numpy.

Что запомнить

• Подмножество кодируется числом, единичный бит — наличие элемента.
• Массив dp индексируется маской напрямую.
• Задача коммивояжёра решается за O(2ⁿ·n²) вместо O(n!).
• Перебор подмасок: submask = (submask - 1) & mask, суммарно 3ⁿ операций.
• Ограничение n ≤ 20–22; ограничение в условии — намёк на этот приём.
• Скобки в битовых выражениях обязательны из-за приоритета операторов.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→