Динамика по поддеревьям
Динамика по поддеревьям
Главной особенностью динамического программирования по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях. Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
Задача о паросочетании максимального веса в дереве
| Определение: |
| Множество рёбер графа, такое, что у любых двух рёбер нет общей вершины, называется паросочетанием. |
Пусть задано взвешенное дерево, с весами, обозначенными как , где и — вершины дерева, соединённые ребром. Задача: составить такое паросочетание, чтобы суммарный вес всех рёбер, входящих в него, был максимальным.
Для решения данной задачи существует несколько алгоритмов. Например, алгоритм Куна, который имеет верхнюю оценку порядка . Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до .
Обозначим как паросочетание максимального веса в поддереве с корнем в i-той вершине, при этом i-тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево i-ой вершины; аналогично - как паросочетание максимального веса в поддерева с корнем в i-той вершине, но только при этом i-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево i-ой вершины; а , таким образом, ответ на задачу будет находиться в , где - корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине i, нам необходимо найти максимальное паросочетание для всех поддеревьев i-ой вершины.
Обозначим Ch(x) — как множество сыновей вершины x и будем находить значения a и b следующим образом:
Если вершина x — лист, то ,
в противном же случае
- ,
С учётом того, что , эти формулы можно переписать как
- .
Теперь оценим количество операций, необходимых нам для нахождения . Так как , то для вычисления необходимо вычислить , . Для вычисления и того, и другого необходимо время порядка , где n — количество вершин в дереве.
Реализация
Заполним изначально массив числами -1. ( — число вершин)
calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else: //случай 2: берем какое-то ребро
max1 = dp[v][0]
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]
Амортизированные оценки для ДП на дереве
| Теорема: |
Пусть какой-либо алгоритм на дереве работает за время для вершины x, тогда время обработки им всего дерева не превышает : |
| Доказательство: |
| , поэтому . |
