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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Решение)
(→‎Динамика по деревьям)
Строка 1: Строка 1:
 
=Динамика по деревьям=
 
=Динамика по деревьям=
  
−
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
+
Рассмотрим динамику по дереву на примере задачи о максимальном взвешенном паросочетании в дереве.
 
==Задача о максимальном взвешенном паросочетании на дереве==
 
==Задача о максимальном взвешенном паросочетании на дереве==
 
===Формулировка===
 
===Формулировка===
Строка 8: Строка 8:
 
===Решение===
 
===Решение===
 
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
 
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
−
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
 
 
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
 
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
  
 
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
 
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
−
* Взять какое-то ребро из корня
+
* Занять корень каким-то ребром
−
* Не взять ни одного ребра из корня
+
* Не занимать корень ребрами
  
−
В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.
+
В первом случае мы не сможем рассматривать его детей вовсе. В ином случае мы переходим в его поддеревья и выполняем то же самое действие.
 +
Если мы оставляем корень свободным, значит может разрешить всем его детям иметь в своих поддеревьях занятый корень. В ином случае мы можем разрешить не всем детям, а только тем, которые уже не заняты ребром из корня.
  
 
===Рекуррентная формула===
 
===Рекуррентная формула===
Строка 26: Строка 26:
 
Теперь наши формулы имеют вид:<br>
 
Теперь наши формулы имеют вид:<br>
 
<tex>dp(u, 0) = \sum_{\text{child}\ v\  of\  u}dp(w, 1)</tex><br>
 
<tex>dp(u, 0) = \sum_{\text{child}\ v\  of\  u}dp(w, 1)</tex><br>
−
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u,w]  \}\right\}</tex>
+
<tex>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\}</tex>
  
 
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.
 
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.
Строка 36: Строка 36:
 
             #вернули уже посчитанное значение dp[v][root]
 
             #вернули уже посчитанное значение dp[v][root]
 
         sum1 = 0
 
         sum1 = 0
−
         #случай 1: не берем корень
+
         #случай 1: не берем ребра из корня
−
         for u in child(v):
+
         if root==0:
−
            sum1 += calculate(u, 1)
+
            for u in child(v):
−
         sum2 = a[v]
+
                sum1 += calculate(u, 1)
−
         #случай 2: берем корень
+
            #выполняем мемоизацию
−
         for u in child(v):
+
            dp[v][root] = sum1
−
             for t in child(u): # считаем, что у нас нет ребер наверх, к корню
+
            return sum1
−
                sum2 += calculate(t)
+
         max1 = dp[v][0]
 +
         #случай 2: берем какое-то ребро
 +
         for x in child(v):
 +
             max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
 
         # выполняем мемоизацию
 
         # выполняем мемоизацию
−
         dp[v] = max(sum1, sum2)
+
         dp[v][root] = max1
−
         return dp[v]
+
         return dp[v][root]
−
 
 
−
child(v) -- возвращает детей вершины v
 
  
 
==Общие принципы динамики по поддеревьям==
 
==Общие принципы динамики по поддеревьям==
 
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.
 
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Версия 21:18, 13 января 2013

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

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

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

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

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

Решение

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

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

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

  • Занять корень каким-то ребром
  • Не занимать корень ребрами

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

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

[math]dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 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)\ +\ a[u] \}\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(w, 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].

Псевдокод

   function calculate(v, root):
       if dp[v][root] != -1:
           return dp[v][root]
           #вернули уже посчитанное значение dp[v][root]
       sum1 = 0
       #случай 1: не берем ребра из корня
       if root==0:
           for u in child(v):
               sum1 += calculate(u, 1)
           #выполняем мемоизацию
           dp[v][root] = sum1
           return sum1
       max1 = dp[v][0]
       #случай 2: берем какое-то ребро
       for x in child(v):
           max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
       # выполняем мемоизацию
       dp[v][root] = max1
       return dp[v][root]

Общие принципы динамики по поддеревьям

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Динамика_по_поддеревьям&oldid=29617»