Включение-исключение: гамильтонов цикл без таблицы на 2^n

Если ты умеешь считать включением-исключением и знаешь, как через него посчитать гамильтоновы циклы в полиномиальной памяти, листай до «Теперь сам».

Как думаешь, что мешает динамике по маскам на 30 вершинах

Динамика по маскам из прошлого урока решает коммивояжёра на n = 20. Её таблица - 2^n · n чисел: на двадцати вершинах это двадцать миллионов, на тридцати - тридцать миллиардов, больше любой памяти. Время 2^30 действий - около миллиарда - ещё терпимо, а память уже нет.

Прежде чем читать дальше, попробуй угадать: можно ли считать по всем подмножествам, НЕ храня ничего про каждое из них? Подсказка: иногда легче посчитать «всё подряд», а потом вычесть лишнее, чем сразу считать только правильное.

На что это похоже

Перепись гостей, которые попробовали ВСЕ блюда на банкете. Спрашивать каждого о каждом блюде долго. Зато легко узнать, сколько тарелок ушло без каждого блюда: все гости, минус те, кто пропустил салат, минус те, кто пропустил суп, но тех, кто пропустил и то и другое, мы вычли дважды - прибавим обратно. Каждый раз задаётся простой вопрос про «исключённые блюда», а ответ про «все блюда» собирается знакопеременной суммой.

Механизм: знаки по подмножествам и обходы в обход

ВКЛЮЧЕНИЕ-ИСКЛЮЧЕНИЕ
свойства P_1 … P_m (плохие); N(S) - сколько объектов обладает
всеми свойствами из множества S
объектов без единого плохого свойства =  Σ по S  (−1)^|S| · N(S)

ГАМИЛЬТОНОВЫ ЦИКЛЫ
объекты:  замкнутые обходы длины n из вершины 0 (с повторами вершин)
плохое свойство P_v:  обход ни разу не зашёл в v
обход длины n без плохих свойств посетил все n вершин,
    ровно по разу - это гамильтонов цикл

N(S) = обходов длины n из 0 в 0, не заходящих в S:
    динамика по шагам: schet[v] - сколько путей длины t в v
    по разрешённым вершинам; n шагов по O(n²) - O(n³)

циклов = Σ по S ⊆ {1 … n−1}  (−1)^|S| · N(S)
2^(n−1) множеств, на каждое O(n³) времени и O(n) памяти

Почему каждый «неправильный» обход сократится. Пусть обход пропустил ровно множество вершин M (не пустое). Он учтён во всех N(S) с S ⊆ M - со знаком (−1)^|S|. Подмножеств M с чётным размером столько же, сколько с нечётным, и сумма знаков равна нулю. Остаются только обходы с M = ∅ - гамильтоновы.

Правило

Включение-исключение считает объекты без плохих свойств как Σ по S (−1)^|S| · N(S), где N(S) - число объектов со всеми свойствами из S. Гамильтоновы циклы через вершину 0 - это замкнутые обходы длины n, не пропустившие ни одной вершины; N(S) - обходы, избегающие S, считаются динамикой по шагам за O(n³). Всего O(2^n · n³) времени и O(n) памяти против таблицы 2^n · n у динамики по маскам.

Разбор: делители и треугольник

ЧИСЛА 1..100, делящиеся на 2, 3 или 5
    на 2: 50    на 3: 33    на 5: 20
    на 6: 16    на 10: 10   на 15: 6
    на 30: 3
    50 + 33 + 20 − 16 − 10 − 6 + 3 = 74

ГАМИЛЬТОНОВЫ ЦИКЛЫ В ТРЕУГОЛЬНИКЕ 0–1–2, длина обхода 3
    S = ∅:      замкнутые обходы длины 3 из 0: 0-1-2-0 и 0-2-1-0
                (0-1-0-1 за три шага в 0 не вернулся) → 2
    S = {1}:    только 0 и 2: 0-2-0-2 не возвращается за 3 шага → 0
    S = {2}:    0
    S = {1, 2}: из 0 никуда → 0
    циклов = 2 − 0 − 0 + 0 = 2  (один цикл в двух направлениях)

На треугольнике все обходы длины три уже гамильтоновы, и поправки нулевые. На больших графах обходы с повторами многочисленны - и именно их вычитает знакопеременная сумма.

Разбор: двенадцать вершин двумя способами

Программа считает гамильтоновы циклы случайного графа на 12 вершинах динамикой по маскам (Хелд-Карп) и включением-исключением и сравнивает ответы и память.

import itertools
import random

rng = random.Random(27)
n = 12
sosedi = [[] for _ in range(n)]
for u in range(n):
    for v in range(u + 1, n):
        if rng.random() < 0.45:
            sosedi[u].append(v)
            sosedi[v].append(u)


def held_karp():                      # маски: путей из 0 через набор
    tabl = [[0] * n for _ in range(2 ** n)]   # 2^n · n чисел в памяти
    tabl[1][0] = 1
    for maska in range(1, 2 ** n):
        for v in range(n):
            if tabl[maska][v]:
                for u in sosedi[v]:
                    if not maska // 2 ** u % 2:
                        tabl[maska + 2 ** u][u] += tabl[maska][v]
    polnaya = 2 ** n - 1
    return sum(tabl[polnaya][v] for v in sosedi[0]), 2 ** n * n


def vklyuchenie_isklyuchenie():       # память - один массив на n чисел
    itog = 0
    drugie = list(range(1, n))
    for r in range(n):
        for ubrany in itertools.combinations(drugie, r):
            mozhno = [True] * n
            for x in ubrany:
                mozhno[x] = False
            schet = [0] * n           # замкнутые обходы длины n из 0
            schet[0] = 1              # только по разрешённым вершинам
            for _ in range(n):
                novyj = [0] * n
                for v in range(n):
                    if schet[v]:
                        for u in sosedi[v]:
                            if mozhno[u]:
                                novyj[u] += schet[v]
                schet = novyj
            itog += (-1) ** r * schet[0]
    return itog, n


a, pam_a = held_karp()
b, pam_b = vklyuchenie_isklyuchenie()
print("гамильтоновых циклов (с направлением):", a, b)
print("память: таблица", pam_a, "чисел против", pam_b)

гамильтоновых циклов (с направлением): 34 34
память: таблица 49152 чисел против 12

Ответы совпали: 34 направленных цикла, то есть 17 различных. Таблица динамики - 49 152 числа, у включения-исключения в памяти одновременно - массив из двенадцати. На тридцати вершинах таблица потребовала бы тридцать миллиардов чисел, а включение-исключение - те же тридцать, хотя считать придётся долго: 2^29 множеств.

Что ломается без этого

Первая ошибка - забыть знак: без (−1)^|S| сумма считает обходы с повторениями многократно. Вторая - считать обходами пути, а не замкнутые обходы, или взять длину не n: гамильтонов цикл из n вершин - ровно n рёбер. Третья - ждать, что приём находит сам цикл: он СЧИТАЕТ (и отвечает «есть ли» по ненулевому ответу), а чтобы восстановить цикл, нужна ещё работа - например, удалять рёбра и смотреть, не упал ли ответ до нуля. Четвёртая - переполнение в языках с фиксированной шириной чисел: промежуточные суммы бывают огромными, а результат маленький; Python спасает длинная арифметика.

Зачем это в работе

Включение-исключение - главный инструмент комбинаторного счёта: сколько паролей содержит хотя бы одну цифру и хотя бы одну букву, сколько перестановок без неподвижных точек, сколько чисел меньше n не имеют с ним общих делителей. В алгоритмах точного перебора оно даёт решения, которым хватает полиномиальной памяти: раскраска графа в k цветов, покрытие множествами, задачи о расписаниях. Когда время 2^n терпимо, а память 2^n - нет, стоит спросить, нельзя ли считать «в обход» со знаками.

Теперь сам

Сколько чисел от 1 до 60 не делятся ни на 2, ни на 3, ни на 5?