47
правок
Изменения
→Задача о максимальном независимом множестве на дереве
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не являлись бы соседними. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.
===Решение===
[[Файл:Independent_set_treeparosochetanie.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множествокакое-то ребро из корня* Не взять корень в наше множествони одного ребра из корня
В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.
Теперь наши формулы имеют вид:<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>O(n^2)</tex> до <tex>O(n)</tex>.
