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