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

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

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

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

Определение:

Множество рёбер графа, такое, что у любых двух рёбер нет общей вершины, называется паросочетанием.

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

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

Если вершина x — лист, то [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 — количество вершин в дереве.

Реализация

Заполним изначально массив [math]dp[V][2][/math] числами -1. ([math]V[/math] — число вершин)

   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]

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

Теорема:

Пусть какой-либо алгоритм на дереве работает за время [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]

Ссылки

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