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

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

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

Пусть задано взвешенное дерево, с весами, обозначенными как [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[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]c[root][/math]. Так как , то для вычисления [math]c[root][/math] необходимо вычислить [math]a[root][/math], [math]b[root][/math]. Для вычисления и того, и другого необходимо время порядка , где 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]

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

Теорема:

Пусть какой-либо алгоритм на дереве работает за время для вершины x, тогда время обработки им всего дерева не превышает :

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

, поэтому .

Ссылки

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