Динамика по поддеревьям

Динамика по деревьям

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.

Задача о максимальном независимом множестве на дереве

Формулировка

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

Решение

Максимальный независимый набор из красных вершин

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

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:

• Взять корень в наше множество
• Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

Рекуррентная формула

[math]dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)[/math]
[math]dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}[/math]

Заметим, что вторую формулу можно упростить:
[math]\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)[/math]

Теперь наши формулы имеют вид:
[math]dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)[/math]
[math]dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u] \}\right\}[/math]

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с [math]O(n^2)[/math] до [math]O(n)[/math].

Псевдокод

   function calculate(v, root):
       if dp[v][root] != -1:
           return dp[v][root]
           #вернули уже посчитанное значение dp[v][root]
       sum1 = 0
       #случай 1: не берем корень
       for u in child(v):
           sum1 += calculate(u, 1)
       sum2 = a[v]
       #случай 2: берем корень
       for u in child(v):
           for t in child(u): # считаем, что у нас нет ребер наверх, к корню
               sum2 += calculate(t)
       # выполняем мемоизацию
       dp[v] = max(sum1, sum2)
       return dp[v]

child(v) -- возвращает детей вершины v

Общие принципы динамики по поддеревьям

Самое главное и основное отличие — ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.