Динамика по поддеревьям — различия между версиями
ZeRoGerc (обсуждение | вклад) (→Задача о паросочетании максимального веса в дереве) |
ZeRoGerc (обсуждение | вклад) (→Псевдокод) |
||
| Строка 29: | Строка 29: | ||
== Псевдокод == | == Псевдокод == | ||
| − | dfs(int x): | + | '''int''' dfs('''int''' x): |
| − | for child : Ch[x] | + | '''for''' (child : Ch[x]) |
dfs(child); | dfs(child); | ||
| − | a[x] = max(a[x], b[child] + w[x][child] - с[child]); | + | a[x] = '''max'''(a[x], b[child] + w[x][child] - с[child]); |
b[x] += с[child]; | b[x] += с[child]; | ||
a[x] += b[x] | a[x] += b[x] | ||
| − | c[x] = max(a[x], b[x]); | + | c[x] = '''max'''(a[x], b[x]); |
dfs(root); | dfs(root); | ||
| − | return c[root]; | + | '''return''' c[root]; |
== Амортизированные оценки для ДП на дереве == | == Амортизированные оценки для ДП на дереве == | ||
Версия 15:44, 7 декабря 2014
Содержание
Динамика по поддеревьям
Главной особенностью динамического программирования по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях. Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
Задача о паросочетании максимального веса в дереве
Пусть задано взвешенное дерево, с весами, обозначенными как , где и — вершины дерева, соединённые ребром. Задача: составить такое паросочетание, чтобы суммарный вес всех рёбер, входящих в него, был максимальным.
Для решения данной задачи существует несколько алгоритмов. Например, алгоритм Куна, который имеет верхнюю оценку порядка . Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до .
Обозначим как паросочетание максимального веса в поддереве с корнем в -той вершине, при этом -тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево -ой вершины; аналогично - как паросочетание максимального веса в поддерева с корнем в -той вершине, но только при этом -тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево -ой вершины; а , таким образом, ответ на задачу будет находиться в , где - корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине , нам необходимо найти максимальное паросочетание для всех поддеревьев -ой вершины.
Обозначим — как множество сыновей вершины и будем находить значения и следующим образом:
Если вершина — лист, то ,
в противном же случае
- ,
С учётом того, что , эти формулы можно переписать как
- .
Теперь оценим количество операций, необходимых нам для нахождения . Так как , то для вычисления необходимо вычислить , . Для вычисления и того, и другого необходимо время порядка , где n — количество вершин в дереве.
Псевдокод
int 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];
Амортизированные оценки для ДП на дереве
| Теорема: |
Пусть какой-либо алгоритм на дереве работает за время для вершины x, тогда время обработки им всего дерева не превышает : |
| Доказательство: |
| , поэтому . |
