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

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

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

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

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

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

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

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

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

• [math]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 )[/math],
• [math]b[x]=\sum_{z \in Ch(x)} \limits \max \left ( a[z], b[z] \right )[/math]

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

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

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

Псевдокод

function dfs(x: int):
   for (child : Ch[x])
       dfs(child)
       a[x] = max(a[x], b[child] + w[x][child] - с[child])  //по формуле выше, но без b[x](прибавим его один раз в конце) 
       b[x] += с[child] 
   a[x] += b[x]                                 // так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x                                      
   c[x] = max(a[x], b[x])
//в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] 

Задача о сумме длин всех путей в дереве

Решим эту задачу за [math] O(n) [/math]. Пуcть задано подвешенное дерево. Рассмотрим количество путей для вершины [math] v [/math]. Во-первых, это пути не проходящие через эту вершину, то есть все пути между её сыновьями. Во-вторых, пути, которые оканчиваются вершиной [math] v [/math]. И в третьих, это пути проходящие через вершину [math] v [/math], они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из сыновей вершины [math] v [/math].

Теперь подсчитаем пути для каждого варианта. Обозначим [math] S[v]\ - [/math] размер поддерева [math] v [/math], [math] F[v]\ - [/math] сумма длин всех путей вершины [math] v [/math], [math] G[v]\ - [/math] количество путей оканчивающихся вершиной [math] v [/math], [math] H[v]\ - [/math] количество путей проходящих через вершину [math] v [/math]. Если вершина [math] u [/math] лист, то [math] S[u] [/math] = 1, а [math] G[u] [/math] = 0.

1. Пути не проходящие через эту вершину. Это просто сумма суммы длин для всех поддеревьев детей или [math] \sum_{x \in Ch(v)} \limits F[x][/math].

2. Пути оканчивающиеся в вершине [math] v [/math]. Рассмотрим ребро, соединяющее вершину [math] v [/math] и одного ее сына, пусть это будет вершина [math] g [/math]. Переберем все пути, которые начинаются с этого ребра и идут вниз. Это будет сумма путей оканчивающихся в [math] g + S[g] [/math], так как суммарная длина поддерева [math] g [/math] уже сосчитана и каждый такой путь мы продлили ребром, соединяющим вершины [math] v [/math] и [math] g [/math]. Всего таких путей: [math] G[v] = \sum_{x \in Ch(v)} \limits {(G[x] + S[x])}[/math].

3. Пути проходящие через вершину [math] v [/math]. Рассмотрим двух сыновей этой вершины: [math] x [/math] и [math] y [/math]. Нам надо подсчитать все пути, которые поднимаются из поддерева [math] x [/math] в [math] v [/math] и затем опускаются в поддерево [math] y [/math] и наоборот. То есть по каждому пути, оканчивающимся в вершине [math] x [/math] мы пройдем столько раз сколько элементов в поддереве [math] y [/math], следовательно таких путей будет [math] G[x]S[y] [/math]. Аналогично, если будем подниматься из поддерева [math] y [/math]. Также надо учитывать сколько раз мы проходим по ребрам, соединяющим вершины [math] x [/math] [math] v [/math] и [math] y [/math] [math] x [/math]. Итого для двух вершин [math] x [/math] и [math] y [/math]: [math] G[x]S[y] + G[y]S[x] + 2S[x]S[y] [/math], следовательно ( [math] x,y \in Ch(v)[/math]) [math] H[v] = \sum_{x,y\ x \ne y} \limits{(G[x]S[y] + G[y]S[x] + 2S[x]S[y])} [/math]. Но такой подсчет испортит асимптотику до [math] O(n^2) [/math].

Заметим, что [math] \sum_{x,y} \limits {(G[x]S[y])} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} [/math]. Но еще надо учесть, что [math] x \ne y [/math], следовательно [math] \sum_{x,y\ x \ne y} \limits{(G[x]S[y])} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(G[x]S[x])} [/math]. Аналогично для [math] S[x]S[y] [/math]. Итак: [math] H[v] = 2(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(G[x]S[x])} ) + 2(\sum_{x} \limits {S[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(S[x]S[x])})[/math].

Ответ задачи: [math] F[v] = \sum_{x \in Ch(v)} \limits F[x] + G[v] + H[v] [/math]. Асимптотика каждого слагаемого равна [math]O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )[/math], где n — количество вершин в дереве, следовательно и [math] F[v] [/math] находится за [math] O(n) [/math].

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

Теорема:

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

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

[math]\triangleright[/math]

[math]\forall x \in \left \{ 1 \dots n \right \}: \left | Ch(x) \right | \leqslant n[/math], поэтому [math]\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[/math].

[math]\triangleleft[/math]

См. Также

• Задача коммивояжера, ДП по подмножествам
• Задача о числе путей в ациклическом графе

Источники информации

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