Динамика на дереве: трудная задача становится линейной

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

Как думаешь, что делает дерево лёгким

Отдел из ста сотрудников, у каждого один начальник - дерево подчинения. На корпоратив зовут людей так, чтобы никто не оказался за столом со своим прямым начальником, а суммарная «весёлость» гостей была наибольшей. На произвольном графе знакомств это задача о наибольшем независимом множестве с весами, NP-трудная; в главе о точных методах её решали ветвлением с основой 1,47.

Ответь себе до чтения: что меняет дерево? Решение по одному отделу почти не зависит от остальной компании: снаружи его касается только одно - позвали ли начальника отдела. Значит, для каждого отдела достаточно знать два ответа: «лучшее, если начальник отдела приглашён» и «лучшее, если нет».

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

Сбор отчётов снизу вверх. Каждый руководитель получает от каждого подчинённого два числа - «сколько наберёт твоя ветка, если ты пойдёшь» и «если не пойдёшь», - и считает свои два числа. Ни один руководитель не видит устройства чужих отделов, только эти пары. Наверху директор выбирает лучшее из двух своих чисел.

Двух чисел достаточно, потому что отдел связан с остальной компанией одним человеком. Будь связей больше - понадобились бы числа на каждое сочетание связующих людей, и об этом следующие уроки.

Механизм: два числа на вершину

Для вершины v с весом w(v):

s(v)    = w(v) + Σ bez(ребёнок)                  v взята: дети нет
bez(v)  = Σ max(s(ребёнок), bez(ребёнок))        v не взята: дети как
                                                 им лучше
ответ   = max(s(корень), bez(корень))

Вершины обрабатываются снизу вверх: ребёнок раньше родителя. Если номера выданы так, что у родителя номер меньше, чем у ребёнка, достаточно пройти номера с конца. Каждое ребро участвует в подсчёте один раз - время O(n). Чтобы получить сам набор, а не только вес, запоминают, какой из двух вариантов выбран, и проходят дерево обратно сверху вниз.

Почему это верно. Взятое множество внутри поддерева v влияет на остальное дерево только через v: если v взята, родителя брать нельзя, если нет - можно. Поэтому лучшее множество в поддереве при каждом из двух состояний v можно выбрать независимо от остального. Это та же оптимальная подструктура, что в разделе о динамическом программировании, только подзадачи - поддеревья.

Правило

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

Разбор: динамика против перебора

derevo строит случайное дерево: родитель каждой вершины - вершина с меньшим номером. dp - динамика с двумя числами, perebor - все 2¹¹ подмножеств для сверки.

import random

def derevo(n, zerno):
    random.seed(zerno)
    roditel = [-1]
    ves = [random.randint(1, 9)]
    for v in range(1, n):
        roditel.append(random.randrange(v))
        ves.append(random.randint(1, 9))
    return [roditel, ves]

def dp(roditel, ves):
    n = len(ves)
    s = ves[:]
    bez = [0] * n
    # дети идут после родителей, поэтому снизу вверх - с конца
    for v in range(n - 1, 0, -1):
        p = roditel[v]
        s[p] = s[p] + bez[v]
        bez[p] = bez[p] + max(s[v], bez[v])
    return max(s[0], bez[0])

def perebor(roditel, ves):
    n = len(ves)
    luchshee = 0
    for maska in range(2 ** n):
        ok = True
        for v in range(1, n):
            if maska >> v & 1 == 1 and maska >> roditel[v] & 1 == 1:
                ok = False
        if ok:
            summa = 0
            for v in range(n):
                if maska >> v & 1 == 1:
                    summa = summa + ves[v]
            luchshee = max(luchshee, summa)
    return luchshee

for zerno in [1, 2, 3]:
    t = derevo(11, zerno)
    print(t[1], dp(t[0], t[1]), perebor(t[0], t[1]))

[3, 5, 8, 8, 4, 8, 7, 1, 5, 2, 1] 39 39
[1, 2, 3, 5, 4, 1, 3, 7, 9, 9, 1] 29 29
[4, 6, 2, 1, 5, 4, 8, 9, 7, 4, 9] 39 39

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

Разбор: десять тысяч вершин

Та же динамика, считаются шаги - сколько раз ребёнок передал родителю свои два числа. Последний столбец - сумма всех весов, для сравнения с ответом.

import random

def dp(roditel, ves, schet):
    n = len(ves)
    s = ves[:]
    bez = [0] * n
    for v in range(n - 1, 0, -1):
        schet[0] = schet[0] + 1
        p = roditel[v]
        s[p] = s[p] + bez[v]
        bez[p] = bez[p] + max(s[v], bez[v])
    return max(s[0], bez[0])

random.seed(5)
for n in [100, 1000, 10000]:
    roditel = [-1]
    ves = [random.randint(1, 9)]
    for v in range(1, n):
        roditel.append(random.randrange(v))
        ves.append(random.randint(1, 9))
    schet = [0]
    print(n, dp(roditel, ves, schet), schet[0], sum(ves))

100 278 99 472
1000 3326 999 5025
10000 32792 9999 50134

Шагов ровно n − 1 - по одному на ребро. Ответ - от 59 до 66% суммы весов: в дереве много листьев, и независимое множество может взять большую часть вершин. Десять тысяч вершин - мгновение, хотя на произвольном графе той же задачи и сотня вершин требует экспоненты.

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

Одно число на вершину. «Лучшее в поддереве» без указания, взята ли вершина, не даёт собрать ответ родителю: родителю нужно знать, можно ли брать его вместе с этим лучшим.

Обход сверху вниз. Родитель считается раньше детей и складывает ещё не посчитанные числа. Порядок - от листьев к корню.

Ждут того же от графа с циклами. Один цикл - и поддерево связано с остальным уже двумя вершинами. Динамика ломается, но не насовсем: если таких связей немного, её можно обобщить. Это и есть древесная ширинаРазбирается в разделе 22, глава «Древесная ширина, цветное кодирование и нижние границы»: Древесное разложение: насколько граф похож на дерево.

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

Иерархии встречаются постоянно: оргструктура, дерево каталогов, дерево зависимостей пакетов, дерево разбора, сеть с одним путём между узлами. Многие задачи, NP-трудные в общем виде, - независимое множество, доминирующее множество, раскраска, покрытие - на деревьях решаются такой динамикой за линию. Первый вопрос к трудной задаче на графе: не дерево ли у нас, или почти дерево?

Теперь сам

1. Путь из четырёх вершин с весами 5, 1, 1, 5. Посчитай s и bez для каждой вершины, двигаясь с конца, и найди ответ.
2. Звезда: центр весом 10, пять листьев по 3. Каков ответ?
3. Почему динамика тратит на дерево ровно n − 1 шагов передачи?