Изменения

Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве. == Задача о паросочетании максимального веса в дереве == {{Задача|definition = Пусть задано взвешенное дерево, с весами, обозначенными как <tex>w_{i,j}</tex>, где <tex>i</tex> и <tex>j</tex> — вершины дерева, соединённые ребром.. Необходимо составить такое [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях | паросочетание]], чтобы суммарный вес всех рёбер, входящих в него, был максимальным.}}Для решения данной задачи существует несколько алгоритмов. Например, [[алгоритм_Куна_для_поиска_максимального_паросочетания | алгоритм Куна]], который имеет верхнюю оценку порядка <tex>O \left ( n^3 \right )</tex>. Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до <tex>O \left ( n \right )</tex>. Обозначим <tex>a[i]</tex> как паросочетание максимального веса в поддереве с корнем в <tex>i</tex>-той вершине, при этом <tex>i</tex>-тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево <tex>i</tex>-ой вершины; аналогично <tex>b[i]</tex> {{---}} как паросочетание максимального веса в поддерева с корнем в <tex>i</tex>-той вершине, но только при этом <tex>i</tex>-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево <tex>i</tex>-ой вершины; а <tex>c[i]=\max \left ( a[i],b[i] \right )</tex>, таким образом, ответ на задачу будет находиться в <tex>c[root]</tex>, где <tex>root</tex> {{---}} корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине <tex>i</tex>, нам необходимо найти максимальное паросочетание для всех поддеревьев <tex>i</tex>-ой вершины. Обозначим <tex>Ch(x)</tex> {{---}} как множество сыновей вершины <tex>x</tex> и будем находить значения <tex>a[x]</tex> и <tex>b[x]</tex> следующим образом: Если вершина <tex>x</tex> {{---}} лист, то <tex>a[x]=b[x]=0</tex>, в противном же случае * <tex>a[x]=Динамика по деревьям\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y} +\sum_{\substack{z \neq y\\z \in Ch(x)}} \limits \max \left ( a[z],b[z] \right )\right )</tex>,* <tex>b[x]=\sum_{z \in Ch(x)} \limits \max \left ( a[z], b[z] \right )</tex> С учётом того, что <tex>c[i]=\max \left ( a[i],b[i] \right )</tex>, эти формулы можно переписать как * <tex>a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y}-c[y] \right )+b[x]</tex>* <tex>b[x]=\sum_{z \in Ch(x)} \limits c[z]</tex>.

Теперь оценим количество операций, необходимых нам для нахождения <tex>c[root]</tex>. Так как <tex>c[i]===Решение===\max \left ( a[i],b[Файл:parosochetanie.png|100px|i] \right|frame|Максимальное взвешенное паросочетание)</tex>, то для вычисления <tex>c[root]</tex> необходимо вычислить <tex>a[root]</tex>, <tex>b[root]Главное отличие этой задачи от других динамически решаемых </tex>. Для вычисления и того, и другого необходимо время порядка <tex>O \left ( \sum_{{---x=1}} ответ в одном поддереве влияет на решение ^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )</tex>, где <tex> n </tex> — число вершин в остальныхдереве. 

Рассмотрим наше первое состояние=== Псевдокод === <font color = darkgreen>// в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color = darkgreen> '''function''' dfs(x: '''int''', a: '''int[]''', b: '''int[]''', когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещиc: '''int[]''', w: '''int[][]''', Ch: '''int[]'''): '''for''' (i :Ch[x]) dfs(i, a, b, c, w, Ch)* Занять корень каким a[x] = max(a[x], b[i] + w[x][i] -то ребромс[i]) <font color = darkgreen>// по формуле выше, но без b[x] (прибавим его один раз в конце) </font color = darkgreen> b[x] += с[i] * Не занимать корень ребрами a[x] += b[x] <font color = darkgreen>// так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x</font color = darkgreen> c[x] = max(a[x], b[x])

В первом случае мы не сможем рассматривать его детей вовсе== Задача о сумме длин всех путей в дереве =={{Задача|definition = Найти сумму длин всех путей в дереве.}}Решим эту задачу за <tex> O(n) </tex>. Пусть задано подвешенное дерево. В ином случае мы переходим Рассмотрим пути проходящие в его поддеревья и выполняем то же самое действиеподдереве вершины <tex> v </tex>.Если мы оставляем корень свободнымВо-первых, это пути, не проходящие через эту вершину, значит можем разрешить всем его детям иметь то есть все пути в своих поддеревьях занятый кореньеё сыновей. В ином случае мы можем разрешить не всем детямВо-вторых, а только темпути, которые уже не заняты ребром оканчиваются вершиной <tex> v </tex>. И в-третьих, это пути, проходящие через вершину <tex> v </tex>, они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из корнясыновей вершины <tex> v </tex>.

Теперь подсчитаем пути для каждого варианта. Обозначим <tex> S[v]\ - </tex> размер поддерева <tex> v </tex>, <tex> F[v]\ - </tex> сумма длин всех путей в поддереве вершины <tex> v </tex>, <tex> G[v]\ - </tex> сумма длин всех путей начинающихся в поддереве вершины v и оканчивающихся вершиной <tex> v </tex>, <tex> H[v]\ - </tex> сумма длин всех путей проходящих через вершину <tex> v </tex>. Если вершина <tex> u </tex> лист, то <tex> S[u] </tex> =1, а <tex> G[u] </tex> =<tex> H[u] </tex> =Рекуррентная формула===0.# Пути не проходящие через эту вершину. Это просто сумма суммы длин путей для всех поддеревьев детей или <tex> \sum_{x \in Ch(v)} \limits F[x]</tex>.Обозначим # Пути оканчивающиеся в качестве вершине <tex>dp(uv </tex>. Рассмотрим ребро, соединяющее вершину <tex> v </tex> и одного ее сына, root)пусть это будет вершина <tex> g </tex> функцию. Переберем все пути, возвращающую ответ для поддерева которые начинаются с корнем этого ребра и идут вниз. Сумма длин всех таких путей будет сумма путей оканчивающихся в <tex>ug + S[g] </tex>, так как суммарная длина путей оканчивающихся в вершине <tex> g </tex> уже сосчитана и каждый такой путь, которых ровно <tex> S[g] </tex> мы продлили ребром, соединяющим вершины <tex> v </tex> и <tex> g </tex>. Суммарная длина таких путей: <tex> G[v] = \sum_{x \in Ch(v)} \limits {\Bigl(G[x] + S[x]\Bigl)}</tex>.Если # Пути проходящие через вершину <tex> v </tex>. Рассмотрим двух сыновей этой вершины: <tex> x </tex> и <tex> y </tex>. Нам надо подсчитать все пути, которые поднимаются из поддерева <tex> x </tex> в <tex> v </tex> и затем опускаются в поддерево <tex>root=1y </tex>и наоборот. То есть по каждому пути, то оканчивающимся в вершине <tex> x </tex> мы пройдем столько раз сколько элементов в этом поддереве <tex> y </tex>, следовательно суммарная длина таких путей будет <tex> G[x]S[y] </tex>. Аналогично, если будем подниматься из поддерева <tex> y </tex>. Также надо учитывать сколько раз мы разрешаем занимать кореньпроходим по ребрам, соединяющим вершины <tex> x </tex> <tex> v </tex> и <tex> y </tex> <tex> x </tex>. Иначе нетИтого для двух вершин <tex> x </tex> и <tex> y </tex>: <tex> G[x]S[y] + G[y]S[x] + 2S[x]S[y] </tex>, следовательно ( <tex> x,y \in Ch(v)</tex>) <tex> H[v] = \sum_{x,y\ x \ne y} \limits{\Bigl(G[x]S[y] + G[y]S[x] + 2S[x]S[y]\Bigl)} </tex>. Но такой подсчет испортит асимптотику до <tex> O(n^2) </tex>. Заметим, что <tex> \sum_{x,y} \limits {\Bigl(G[x]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} </tex>. Но еще надо учесть, что <tex> x \ne y </tex>, следовательно <tex> \sum_{x,y\ x \ne y} \limits{\Bigl(G[x]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x]\Bigl)} </tex>. Аналогично для <tex> S[x]S[y] </tex>. Итак: <tex> H[v] = \biggl(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x]\Bigl)} \biggl) + \biggl(\sum_{x} \limits {S[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(S[x]S[x]\Bigl)} \biggl) </tex>.

Ответ задачи: <tex>dp(u, 0) F[v] = \sum_{x \text{childin Ch(v)}\ limits F[x] + G[v\ of\ u}dp(w, 1)] + H[v] </tex><br>. Асимптотика каждого слагаемого равна <tex>dp(u, 1) = \maxO \left\{dp(u, 0),\ \max_sum_{\text{childx=1}^n \ xlimits \ of\ u}\{dpleft | Ch(x, 0)\ +right | \ right )=O \sum_{left ( n \text{child}right )</tex>, где <tex> n </tex> — число вершин в дереве, следовательно и время работы самого алгоритма <tex> O \ v\ of\ u; \ v \ne x }dpleft (v, 1)\ +\ a[u] \}n \right\}) </tex>.

Заметим== Амортизированные оценки для ДП на дереве =={{Теорема|statement=Пусть какой-либо алгоритм на дереве работает за время <tex>O \left ( \left |Ch \left ( x \right) \right |^k \right )</tex> для вершины x, что вторую формулу можно упростить:тогда время обработки им всего дерева не превышает <tex>O \left ( n^k \right )<br/tex>:|proof=<tex>\sum_forall x \in \left \{1 \dots n \right \}: \textleft | Ch(x) \right | \leqslant n</tex>, поэтому <tex>\sum_{childx=1}^n \ vlimits \ ofleft | Ch \ u; left ( x \ v right ) \right |^k \leqslant \ne sum_{x =1}dp^n \limits | Ch \left (v, x \right ) | \cdot n^{k-1) }= dp(u, 0) n \cdot n^{k- dp(x, 1)}=n^k</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)\ +\ w* [[u,xЗадача о числе путей в ациклическом графе]] \}\right\}</tex>

Заметим==Источники информации==*[http://www.mathnet.ru/links/c14aca73a4926918a879905ffcd4ad7a/timb86.pdf В. В. Лепин, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)<Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве]* [http:/tex> до <tex>O(n)</tex>ru.wikipedia.org/wiki/Паросочетание Википедия — Паросочетание]

===Псевдокод=== 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]