Изменения

=Динамика Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям=]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.

Главной особенностью == Задача о паросочетании максимального веса в дереве == {{Задача|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[Файл:parosochetanie.png|100px|y] \right|frame|Максимальное взвешенное паросочетание)+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[i] \right )</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> — число вершин в дереве.

=== Псевдокод === <texfont color = darkgreen>dp// в основной процедуре вызываем dfs от корня(uroot), 0) после этого ответ будет хранится в c[root] </font color = \sum_{\text{child}\ v\ of\ darkgreen> u}dp'''function''' dfs(vx: '''int''', a: '''int[]''', b: '''int[]''', c: '''int[]''', 1w: '''int[][]''', Ch: '''int[]'''): '''for''' (i : Ch[x])</tex><br><tex>dp dfs(ui, a, b, c, w, 1Ch) a[x] = \max\left\{dp(ua[x], 0b[i] + w[x][i] - с[i]) <font color = darkgreen>// по формуле выше,\ \max_{\text{child}\ но без b[x\ of\ u}\{dp] (прибавим его один раз в конце) </font color = darkgreen> b[x, 0)\ ] +\ \sum_{\text{child}\ v\ of\ u; \ v \ne = с[i] a[x }dp(v, 1)\ ] +\ w= b[x] <font color = darkgreen>// так как в a[u, x] \}\right\}пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x</texfont color = darkgreen> c[x] = max(a[x], b[x])

Заметим, что вторую формулу можно упростить:<br>== Задача о сумме длин всех путей в дереве ==<tex>\sum_{\text{childЗадача|definition = Найти сумму длин всех путей в дереве.}\ v\ of\ u; \ v \ne x }dpРешим эту задачу за <tex> O(n) </tex>. Пусть задано подвешенное дерево. Рассмотрим количество путей для вершины <tex> v</tex>. Во-первых, 1) = dp(uэто пути не проходящие через эту вершину, 0) то есть все пути между её сыновьями. Во- dp(xвторых, пути, которые оканчиваются вершиной <tex> v </tex>. И в третьих, это пути проходящие через вершину <tex> v </tex>, 1)они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из сыновей вершины <tex> v </tex>.

Теперь наши формулы имеют вид:подсчитаем пути для каждого варианта. Обозначим <tex> S[v]\ - </tex> размер поддерева <tex> v </tex>, <tex> F[v]\ - </tex> сумма длин всех путей вершины <tex> v </tex>, <tex> G[v]\ - </tex> количество путей оканчивающихся вершиной <tex> v </tex>, <tex> H[v]\ - </tex> количество путей проходящих через вершину <tex> v </tex>. Если вершина <tex> u <br/tex>лист, то <tex>dp(S[u] </tex> = 1, а <tex> G[u] </tex> = 0.# Пути не проходящие через эту вершину. Это просто сумма суммы длин для всех поддеревьев детей или <tex> \sum_{x \in Ch(v) } \limits F[x]</tex>.# Пути оканчивающиеся в вершине <tex> v </tex>. Рассмотрим ребро, соединяющее вершину <tex> v </tex> и одного ее сына, пусть это будет вершина <tex> g </tex>. Переберем все пути, которые начинаются с этого ребра и идут вниз. Это будет сумма путей оканчивающихся в <tex> g + S[g] </tex>, так как суммарная длина поддерева <tex> g </tex> уже сосчитана и каждый такой путь мы продлили ребром, соединяющим вершины <tex> v </tex> и <tex> g </tex>. Всего таких путей: <tex> G[v] = \sum_{x \text{childin Ch(v)}\ vlimits {\ ofBigl(G[x] + S[x]\ uBigl)}dp(</tex>.# Пути проходящие через вершину <tex> v </tex>. Рассмотрим двух сыновей этой вершины: <tex> x </tex> и <tex> y </tex>. Нам надо подсчитать все пути, которые поднимаются из поддерева <tex> x </tex> в <tex> v</tex> и затем опускаются в поддерево <tex> y </tex> и наоборот. То есть по каждому пути, 1)оканчивающимся в вершине <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>: <brtex>G[x]S[y] + G[y]S[x] + 2S[x]S[y] </tex>dp, следовательно (u<tex> x, 1y \in Ch(v)</tex>) <tex> H[v] = \maxsum_{x,y\ x \leftne y} \limits{dp\Bigl(G[x]S[y] + G[y]S[x] + 2S[x]S[y]\Bigl)} </tex>. Но такой подсчет испортит асимптотику до <tex> O(un^2) </tex>. Заметим, что <tex> \sum_{x, 0y} \limits {\Bigl(G[x]S[y]\Bigl),} = \sum_{x} \ limits {G[x]} \max_sum_{y} \textlimits {childS[y]}</tex>. Но еще надо учесть, что <tex> x \ne y </tex>, следовательно <tex> \ sum_{x,y\ ofx \ une y}\limits{dp\Bigl(G[x, 0]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \ +limits {S[y]} - \sum_{x} \limits {\ dpBigl(u, 0G[x]S[x]\Bigl) } </tex>. Аналогично для <tex> S[x]S[y] </tex>. Итак: <tex> H[v] = 2\biggl(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - dp\sum_{x} \limits {\Bigl(G[x]S[x, 1]\Bigl)} \ biggl) +2\biggl(\sum_{x} \ wlimits {S[u,x] } \sum_{y} \limits {S[y]} - \sum_{x}\rightlimits {\Bigl(S[x]S[x]\Bigl)}\biggl) </tex>.

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с Ответ задачи: <tex> F[v] = \sum_{x \in Ch(v)} \limits F[x] + G[v] + H[v] </tex>. Асимптотика каждого слагаемого равна <tex>O\left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left (n^2\right )</tex> до , где <tex> n </tex> — число вершин в дереве, следовательно и время работы самого алгоритма <tex>O\left (n\right )</tex>.

===РеализацияАмортизированные оценки для ДП на дереве =={{Теорема|statement=Заполним изначально массив Пусть какой-либо алгоритм на дереве работает за время <tex>dp[V][2]O \left ( \left |Ch \left ( x \right) \right |^k \right )</tex> числами -для вершины x, тогда время обработки им всего дерева не превышает <tex>O \left ( n^k \right )</tex>:|proof=<tex>\forall x \in \left \{ 1. \dots n \right \}: \left | Ch(x) \right | \leqslant n</tex>V, поэтому </tex> \sum_{x=1}^n \limits \left | Ch \left ( x \right ) \right |^k \leqslant \sum_{x=1}^n \limits | Ch \left ( x \right ) | \cdot n^{k-1}=n \cdot n^{k--1}=n^k</tex>.}} число вершин)

calculate(v, useRoot): if dp[v][useRoot] != -1: return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root] sum = 0 if useRoot См. также== 0: //случай 1: не берем ребра из корня for (для) всех u из множества детей v: sum += calculate(u, 1) dp* [v][useRoot] = sum else: //случай 2: берем какое-то ребро max1 = dp[vЗадача коммивояжера, ДП по подмножествам][0] for (для) всех x из множества детей v: max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x]) dp* [v][useRootЗадача о числе путей в ациклическом графе] = max1 return dp[v][useRoot]

==СсылкиИсточники информации==*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895fc14aca73a4926918a879905ffcd4ad7a/timb86.pdf В. В. Лепин, Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве]* [http://ru.wikipedia.org/wiki/Паросочетание Википедия — Паросочетание]