Динамика по поддеревьям — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
Строка 34: Строка 34:
  
 
===Реализация===
 
===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числами -1. (<tex>V</tex> {{---}} число вершин)
+
== Псевдокод ==
  
    calculate(v, useRoot):
+
dfs(int x):
        if dp[v][useRoot] != -1:
+
    for child : Ch[x]
            return dp[v][useRoot]           //вернули уже посчитанное значение dp[vertex][root]
+
        dfs(child);
         sum = 0
+
        a[x] = max(a[x], b[child] + w[x][child] - с[child]);
        if useRoot == 0:                    //случай 1: не берем ребра из корня
+
         b[x] += с[child];
            for (для) всех u из множества детей v:
+
    a[x] += b[x]
                sum += calculate(u, 1)
+
    c[x] = max(a[x], b[x]);
            dp[v][useRoot] = sum     
+
dfs(root);
        else:                              //случай 2: берем какое-то ребро   
+
return c[root];
            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]
 
  
 
== Амортизированные оценки для ДП на дереве ==
 
== Амортизированные оценки для ДП на дереве ==

Версия 22:47, 1 января 2014

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

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

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

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


Пусть задано взвешенное дерево, с весами, обозначенными как [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 — количество вершин в дереве.

Реализация

Псевдокод

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];

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

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

Ссылки