Динамика по разложению: таблица на каждое состояние мешка

Если ты напишешь динамику по столбцам решётки для независимого множества с весами и объяснишь, откуда время 2^O(w) · n при ширине w, листай до «Теперь сам».

Как думаешь, что хранить для мешка

Решётка из трёх строк и ста столбцов: склады вдоль трёх параллельных улиц, соседние склады нельзя брать вместе. Вершин 300, подмножеств 2³⁰⁰. Древесная ширина такой решётки - 3, мешок - столбец плюс одна вершина.

Ответь себе до чтения: что нужно знать о уже обработанной левой части решётки, чтобы продолжить вправо? Только то, какие склады взяты в последнем столбце: от остального левая часть отделена этим столбцом. Возможных вариантов последнего столбца - восемь, из них допустимых (без двух соседей) - пять. Значит, вся «память» о левой части - пять чисел.

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

Укладка плитки рядами. Чтобы положить следующий ряд, надо знать только, как лёг предыдущий: какие клетки заняты на границе. Как уложены ряды раньше, уже неважно - их отделяет последний ряд. Для каждого варианта границы запоминаешь лучшую укладку, которая к нему приводит, и идёшь дальше.

Чем шире ряд, тем больше вариантов границы - экспоненциально по ширине, но длина пола на это число не влияет: работа растёт линейно с числом рядов.

Механизм: состояние мешка и переход

Решётка k × N, проход по столбцам. Состояние - маска взятых вершин столбца: бит i равен единице, если взята вершина i. Допустима маска без двух соседних единиц: m & (m >> 1) = 0.

лучшее[m] - лучший вес левой части, если в текущем столбце взят набор m
переход к столбцу j:
    новое[m] = вес(m в столбце j) + max по p, где m & p = 0, лучшее[p]
    (m & p = 0 - никакая взятая вершина не стоит рядом со взятой слева)
ответ = max по m лучшее[m] в последнем столбце

Допустимых масок высоты k - число Фибоначчи F(k + 2): 3, 5, 8, 13, … - растёт как 1,618ᵏ. Переходов на столбец - пар совместимых масок, около 2,4ᵏ. Время - 2^O(k) · N.

Общий случай. По любому разложению ширины w работает та же схема. Состояние мешка - какие его вершины взяты; мешок «наследует» от детей лучшие значения, согласованные на общих вершинах, а вес вершин самого мешка при объединении детей вычитают, чтобы не посчитать его дважды. Для независимого множества с весами это даёт 2^w · w^O(1) · n (теорема из книги Цыгана и др.). Так решаются и раскраска, и доминирующее множество, и гамильтонов цикл - у каждой задачи своё описание состояния мешка.

Правило

Динамика по древесному разложению хранит лучшее значение для каждого состояния мешка (для независимого множества - для каждого его допустимого подмножества) и переходит между соседними мешками, сверяя состояния на общих вершинах. Время 2^O(w) · n при ширине w: экспонента от ширины, линия от размера графа.

Разбор: решётка три на три против перебора

dopustimye перечисляет маски столбца без соседних единиц, po_stolbcam - динамика по столбцам, perebor - все 2⁹ подмножеств решётки 3 × 3 с проверкой соседства по вертикали и горизонтали. Три случайных набора весов.

import random

def dopustimye(k):
    # наборы вершин столбца без двух соседей по вертикали
    maski = []
    for m in range(2 ** k):
        if m & (m >> 1) == 0:
            maski.append(m)
    return maski

def ves_maski(stolbec, m):
    s = 0
    for i in range(len(stolbec)):
        if m >> i & 1 == 1:
            s = s + stolbec[i]
    return s

def po_stolbcam(vesa, k):
    maski = dopustimye(k)
    luchshee = {}
    for m in maski:
        luchshee[m] = ves_maski(vesa[0], m)
    for j in range(1, len(vesa)):
        novoe = {}
        for m in maski:
            best = 0
            for p in maski:
                if m & p == 0 and luchshee[p] > best:
                    best = luchshee[p]
            novoe[m] = best + ves_maski(vesa[j], m)
        luchshee = novoe
    otvet = 0
    for m in maski:
        otvet = max(otvet, luchshee[m])
    return otvet

def perebor(vesa, k):
    dlina = len(vesa)
    luchshee = 0
    for vse in range(2 ** (k * dlina)):
        ok = True
        summa = 0
        for j in range(dlina):
            m = vse >> (j * k) & (2 ** k - 1)
            if m & (m >> 1) != 0:
                ok = False
            if j > 0 and m & (vse >> ((j - 1) * k) & (2 ** k - 1)) != 0:
                ok = False
            summa = summa + ves_maski(vesa[j], m)
        if ok:
            luchshee = max(luchshee, summa)
    return luchshee

random.seed(30)
for proba in range(3):
    vesa = []
    for j in range(3):
        stolbec = []
        for i in range(3):
            stolbec.append(random.randint(1, 9))
        vesa.append(stolbec)
    print(po_stolbcam(vesa, 3), perebor(vesa, 3))

25 25
26 26
34 34

Ответы совпали. Динамика на каждом из двух переходов перебрала пары из пяти допустимых масок - меньше тридцати сравнений на переход, - а перебор проверил 512 подмножеств. На решётке 3 × 100 динамика сделает 99 таких переходов, а перебор - 2³⁰⁰ проверок.

Разбор: как растёт таблица с высотой

perehodov считает, сколько допустимых масок у столбца высоты k, сколько совместимых пар и сколько всего переходов на решётке длины 100.

def dopustimye(k):
    maski = []
    for m in range(2 ** k):
        if m & (m >> 1) == 0:
            maski.append(m)
    return maski

def perehodov(k, dlina):
    maski = dopustimye(k)
    par = 0
    for m in maski:
        for p in maski:
            if m & p == 0:
                par = par + 1
    return [len(maski), par, par * (dlina - 1)]

for k in [2, 3, 4, 5, 6, 8]:
    print(k, 2 ** k, perehodov(k, 100))

2 4 [3, 7, 693]
3 8 [5, 17, 1683]
4 16 [8, 41, 4059]
5 32 [13, 99, 9801]
6 64 [21, 239, 23661]
8 256 [55, 1393, 137907]

Масок 3, 5, 8, 13, 21, 55 - числа Фибоначчи, 1,618ᵏ, меньше всех 2ᵏ наборов. Пар - 7, 17, 41, 99, 239, 1393 - растут примерно в 2,4 раза на строку. На решётке 8 × 100 - 137 907 совместимых переходов (программа проверяет все 55² · 99 = 299 475 пар): мгновение, хотя вершин 800. Удвоить длину - удвоить работу. Добавить строку - умножить на 2,4.

Это и есть вся суть параметра «древесная ширина»: за малую ширину платишь экспонентой, за размер - линией.

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

Хранят меньше, чем отделяет мешок. Если для решётки помнить только «сколько взято в последнем столбце», а не какие, переход не проверит соседство - ответ неверный.

Хранят больше, чем нужно. Состояние «весь левый кусок» - снова экспонента от размера. Хранится ровно то, через что левая часть общается с правой, - мешок.

Идут по разложению большой ширины. Плохое разложение решётки (например, мешок-строка длины 100 при обходе по строкам) даёт 2¹⁰⁰ состояний вместо 2³. Разложение надо выбирать узким - здесь проход по короткой стороне.

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

Динамика по профилю - стандартный приём для задач на полосах и решётках: замощения, раскраски таблиц, размещение на плате, где ширина мала, а длина велика. Тот же приём лежит под вероятностным выводом в графических моделях и под решателями, которые ищут узкое разложение в графе ограничений и считают по нему: на структурированных входах это обгоняет перебор на порядки.

Теперь сам

1. Сколько допустимых масок у столбца высоты 7?
2. Решётка 4 × 1000. Каков порядок числа переходов?
3. Почему в переходе достаточно проверять m & p = 0, а не соседство с другими столбцами?