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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Реализация)
м (Реализация)
Строка 34: Строка 34:
  
 
===Реализация===
 
===Реализация===
 +
Заполним изначально массив dp[N][2] числом -1.
 +
 
     calculate(v, useRoot):
 
     calculate(v, useRoot):
         if dp[v][useRoot] не было посчитанно ранее:
+
         if dp[v][useRoot] != -1:
 
             return dp[v][useRoot]      //вернули уже посчитанное значение dp[vertex][root]
 
             return dp[v][useRoot]      //вернули уже посчитанное значение dp[vertex][root]
 
         sum = 0
 
         sum = 0
         if use_root == 0:                    //случай 1: не берем ребра из корня
+
         if useRoot == 0:                    //случай 1: не берем ребра из корня
 
             for (для) всех u из множества детей v:
 
             for (для) всех u из множества детей v:
 
                 sum += calculate(u, 1)
 
                 sum += calculate(u, 1)
 
             dp[v][useRoot] = sum       
 
             dp[v][useRoot] = sum       
             return sum
+
        else:   
        max1 = dp[v][0]                //случай 2: берем какое-то ребро
+
             max1 = dp[v][0]                //случай 2: берем какое-то ребро
        for (для) всех x из множества детей v:
+
            for (для) всех x из множества детей v:
            max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
+
                max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
        dp[v][useRoot] = max1           
+
            dp[v][useRoot] = max1           
 
         return dp[v][useRoot]
 
         return dp[v][useRoot]
  

Версия 00:30, 14 января 2013

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

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

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

Формулировка

Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

Решение

Максимальное взвешенное паросочетание

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

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:

  • Разрешить выбирать ребро из корня к ребенку.
  • Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

Рекуррентная формула

Обозначим в качестве [math]dp(vertex, use\_root)[/math] функцию, возвращающую ответ для поддерева с корнем [math]vertex[/math]. Если [math]use\_root=1[/math], то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из [math]v[/math] в [math]u[/math] как [math]w[v,u][/math]

[math]dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)[/math]
[math]dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}[/math]

Заметим, что вторую формулу можно упростить:
[math]\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)[/math]

Теперь наши формулы имеют вид:
[math]dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)[/math]
[math]dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}[/math]

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с [math]O(n^2)[/math] до [math]O(n)[/math].

Реализация

Заполним изначально массив dp[N][2] числом -1.

   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:    
           max1 = dp[v][0]                 //случай 2: берем какое-то ребро
           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]

Ссылки