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

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

Главной особенностью динамического программирования по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях. Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.

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

Пусть задано взвешенное дерево, с весами, обозначенными как $w_{i,j}$, где $i$ и $j$ — вершины дерева, соединённые ребром. Задача: составить такое паросочетание, чтобы суммарный вес всех рёбер, входящих в него, был максимальным.

Для решения данной задачи существует несколько алгоритмов. Например, алгоритм Куна, который имеет верхнюю оценку порядка $O \left ( n^3 \right )$. Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до $O \left ( n \right )$.

Обозначим $a[i]$ как паросочетание максимального веса в поддереве с корнем в $i$-той вершине, при этом $i$-тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево $i$-ой вершины; аналогично $b[i]$ - как паросочетание максимального веса в поддерева с корнем в $i$-той вершине, но только при этом $i$-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево $i$-ой вершины; а $c[i]=\max \left ( a[i],b[i] \right )$, таким образом, ответ на задачу будет находиться в $c[root]$, где $root$ - корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине $i$, нам необходимо найти максимальное паросочетание для всех поддеревьев $i$-ой вершины.

Обозначим $Ch(x)$ — как множество сыновей вершины $x$ и будем находить значения $a[x]$ и $b[x]$ следующим образом:

Если вершина $x$ — лист, то $a[x]=b[x]=0$,

в противном же случае

• $a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y} +\sum_{\substack{z \neq y\\z \in Ch(x)}} \limits \max \left ( a[z],b[z] \right )\right )$,
• $b[x]=\sum_{z \in Ch(x)} \limits \max \left ( a[z], b[z] \right )$

С учётом того, что $c[i]=\max \left ( a[i],b[i] \right )$, эти формулы можно переписать как

• $a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y}-c[y] \right )+b[x]$
• $b[x]=\sum_{z \in Ch(x)} \limits c[z]$.

Теперь оценим количество операций, необходимых нам для нахождения $c[root]$. Так как $c[i]=\max \left ( a[i],b[i] \right )$, то для вычисления $c[root]$ необходимо вычислить $a[root]$, $b[root]$. Для вычисления и того, и другого необходимо время порядка $O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )$, где n — количество вершин в дереве.

Псевдокод

int dfs(int x):
   for (child : Ch[x])
       dfs(child);
       a[x] = max(a[x], b[child] + w[x][child] - с[child]);
       b[x] += с[child];
   a[x] += b[x]
   c[x] = max(a[x], b[x]); 
dfs(root);
return c[root];

Амортизированные оценки для ДП на дереве

Теорема:

Пусть какой-либо алгоритм на дереве работает за время $O \left ( \left |Ch \left ( x \right) \right |^k \right )$ для вершины x, тогда время обработки им всего дерева не превышает $O \left ( n^k \right )$:

Доказательство:

$\triangleright$

$\forall x \in \left \{ 1 \dots n \right \}: \left | Ch(x) \right | \leqslant n$, поэтому $\sum_{x=1}^n \limits \left | Ch \left ( x \right ) \right |^k \leqslant \sum_{x=1}^n \limits | Ch \left ( x \right ) | \cdot n^{k-1}=n \cdot n^{k-1}=n^k$.

$\triangleleft$

Ссылки

• В. В. Лепин, Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве
• Алгоритм Куна для поиска максимального паросочетания
• Википедия — Паросочетание