Динамика по поддеревьям — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Рекуррентная формула)
м (rollbackEdits.php mass rollback)
 
(не показано 90 промежуточных версий 11 участников)
Строка 1: Строка 1:
=Динамика по деревьям=
+
Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.
 +
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
  
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
+
== Задача о паросочетании максимального веса в дереве ==
==Задача о максимальном независимом множестве на дереве==
 
===Формулировка===
 
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
 
===Решение===
 
[[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]]
 
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
 
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
 
  
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
+
{{Задача
* Взять корень в наше множество
+
|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 dpi=180>I(u) = \max\left\{a[u]\ +\  \sum_{\text{grandchild}\ w\  of\  u}I(w),\ \sum_{\text{child}\  w\  of\  u}I(w) \right\}</tex>
+
Если вершина <tex>x</tex> {{---}} лист, то <tex>a[x]=b[x]=0</tex>,
  
===Псевдокод===
+
в противном же случае
    function calculate(v):
 
        if dp[v] != -1:
 
            return dp[v]
 
            #вернули уже посчитанное значение dp[v]
 
        sum1 = 0
 
        #случай 1: не берем корень
 
        for u in child(v):
 
            sum1 += calculate(u)
 
        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
+
* <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[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> — число вершин в дереве.
 +
 
 +
 
 +
=== Псевдокод ===
 +
<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> v </tex>. Рассмотрим ребро, соединяющее вершину <tex> v </tex> и одного ее сына, пусть это будет вершина <tex> g </tex>. Переберем все пути, которые начинаются с этого ребра и идут вниз. Сумма длин всех таких путей будет сумма путей оканчивающихся в <tex> g + 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> y </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> 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 \right )</tex>, где <tex> n </tex> — число вершин в дереве, следовательно и время работы самого алгоритма <tex> O \left (n \right ) </tex>.
 +
 
 +
== Амортизированные оценки для ДП на дереве ==
 +
{{Теорема
 +
|statement=
 +
Пусть какой-либо алгоритм на дереве работает за время <tex>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>, поэтому <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>.
 +
}}
 +
 
 +
==См. также==
 +
* [[Задача коммивояжера, ДП по подмножествам]]
 +
* [[Задача о числе путей в ациклическом графе]]
 +
 
 +
==Источники информации==
 +
*[http://www.mathnet.ru/links/c14aca73a4926918a879905ffcd4ad7a/timb86.pdf В. В. Лепин, Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве]
 +
* [http://ru.wikipedia.org/wiki/Паросочетание Википедия — Паросочетание]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Динамическое программирование]]
 +
[[Категория: Другие задачи динамического программирования]]
 +
[[Категория:Алгоритмы на графах]]

Текущая версия на 19:10, 4 сентября 2022

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

Задача о паросочетании максимального веса в дереве

Задача:
Пусть задано взвешенное дерево, с весами, обозначенными как [math]w_{i,j}[/math], где [math]i[/math] и [math]j[/math] — вершины дерева, соединённые ребром.. Необходимо составить такое паросочетание, чтобы суммарный вес всех рёбер, входящих в него, был максимальным.

Для решения данной задачи существует несколько алгоритмов. Например, алгоритм Куна, который имеет верхнюю оценку порядка [math]O \left ( n^3 \right )[/math]. Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до [math]O \left ( n \right )[/math].

Обозначим [math]a[i][/math] как паросочетание максимального веса в поддереве с корнем в [math]i[/math]-той вершине, при этом [math]i[/math]-тая вершина соединена ребром, входящим в паросочетание, с вершиной, входящей в поддерево [math]i[/math]-ой вершины; аналогично [math]b[i][/math] — как паросочетание максимального веса в поддерева с корнем в [math]i[/math]-той вершине, но только при этом [math]i[/math]-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево [math]i[/math]-ой вершины; а [math]c[i]=\max \left ( a[i],b[i] \right )[/math], таким образом, ответ на задачу будет находиться в [math]c[root][/math], где [math]root[/math] — корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине [math]i[/math], нам необходимо найти максимальное паросочетание для всех поддеревьев [math]i[/math]-ой вершины.

Обозначим [math]Ch(x)[/math] — как множество сыновей вершины [math]x[/math] и будем находить значения [math]a[x][/math] и [math]b[x][/math] следующим образом:

Если вершина [math]x[/math] — лист, то [math]a[x]=b[x]=0[/math],

в противном же случае

  • [math]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 )[/math],
  • [math]b[x]=\sum_{z \in Ch(x)} \limits \max \left ( a[z], b[z] \right )[/math]

С учётом того, что [math]c[i]=\max \left ( a[i],b[i] \right )[/math], эти формулы можно переписать как

  • [math]a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y}-c[y] \right )+b[x][/math]
  • [math]b[x]=\sum_{z \in Ch(x)} \limits c[z][/math].


Теперь оценим количество операций, необходимых нам для нахождения [math]c[root][/math]. Так как [math]c[i]=\max \left ( a[i],b[i] \right )[/math], то для вычисления [math]c[root][/math] необходимо вычислить [math]a[root][/math], [math]b[root][/math]. Для вычисления и того, и другого необходимо время порядка [math]O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )[/math], где [math] n [/math] — число вершин в дереве.


Псевдокод

// в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] 
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]) // по формуле выше, но без b[x] (прибавим его один раз в конце) 
       b[x] += с[i] 
   a[x] += b[x]                                // так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x                                      
   c[x] = max(a[x], b[x])

Задача о сумме длин всех путей в дереве

Задача:
Найти сумму длин всех путей в дереве.

Решим эту задачу за [math] O(n) [/math]. Пусть задано подвешенное дерево. Рассмотрим пути проходящие в поддереве вершины [math] v [/math]. Во-первых, это пути, не проходящие через эту вершину, то есть все пути в поддеревьях её сыновей. Во-вторых, пути, которые оканчиваются вершиной [math] v [/math]. И в-третьих, это пути, проходящие через вершину [math] v [/math], они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из сыновей вершины [math] v [/math].

Теперь подсчитаем пути для каждого варианта. Обозначим [math] S[v]\ - [/math] размер поддерева [math] v [/math], [math] F[v]\ - [/math] сумма длин всех путей в поддереве вершины [math] v [/math], [math] G[v]\ - [/math] сумма длин всех путей начинающихся в поддереве вершины v и оканчивающихся вершиной [math] v [/math], [math] H[v]\ - [/math] сумма длин всех путей проходящих через вершину [math] v [/math]. Если вершина [math] u [/math] лист, то [math] S[u] [/math] = 1, а [math] G[u] [/math] = [math] H[u] [/math] = 0.

  1. Пути не проходящие через эту вершину. Это просто сумма суммы длин путей для всех поддеревьев детей или [math] \sum_{x \in Ch(v)} \limits F[x][/math].
  2. Пути оканчивающиеся в вершине [math] v [/math]. Рассмотрим ребро, соединяющее вершину [math] v [/math] и одного ее сына, пусть это будет вершина [math] g [/math]. Переберем все пути, которые начинаются с этого ребра и идут вниз. Сумма длин всех таких путей будет сумма путей оканчивающихся в [math] g + S[g] [/math], так как суммарная длина путей оканчивающихся в вершине [math] g [/math] уже сосчитана и каждый такой путь, которых ровно [math] S[g] [/math] мы продлили ребром, соединяющим вершины [math] v [/math] и [math] g [/math]. Суммарная длина таких путей: [math] G[v] = \sum_{x \in Ch(v)} \limits {\Bigl(G[x] + S[x]\Bigl)}[/math].
  3. Пути проходящие через вершину [math] v [/math]. Рассмотрим двух сыновей этой вершины: [math] x [/math] и [math] y [/math]. Нам надо подсчитать все пути, которые поднимаются из поддерева [math] x [/math] в [math] v [/math] и затем опускаются в поддерево [math] y [/math] и наоборот. То есть по каждому пути, оканчивающимся в вершине [math] x [/math] мы пройдем столько раз сколько элементов в поддереве [math] y [/math], следовательно суммарная длина таких путей будет [math] G[x]S[y] [/math]. Аналогично, если будем подниматься из поддерева [math] y [/math]. Также надо учитывать сколько раз мы проходим по ребрам, соединяющим вершины [math] x [/math] [math] v [/math] и [math] y [/math] [math] x [/math]. Итого для двух вершин [math] x [/math] и [math] y [/math]: [math] G[x]S[y] + G[y]S[x] + 2S[x]S[y] [/math], следовательно ( [math] x,y \in Ch(v)[/math]) [math] H[v] = \sum_{x,y\ x \ne y} \limits{\Bigl(G[x]S[y] + G[y]S[x] + 2S[x]S[y]\Bigl)} [/math]. Но такой подсчет испортит асимптотику до [math] O(n^2) [/math]. Заметим, что [math] \sum_{x,y} \limits {\Bigl(G[x]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} [/math]. Но еще надо учесть, что [math] x \ne y [/math], следовательно [math] \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)} [/math]. Аналогично для [math] S[x]S[y] [/math]. Итак: [math] 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) [/math].

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

Амортизированные оценки для ДП на дереве

Теорема:
Пусть какой-либо алгоритм на дереве работает за время [math]O \left ( \left |Ch \left ( x \right) \right |^k \right )[/math] для вершины x, тогда время обработки им всего дерева не превышает [math]O \left ( n^k \right )[/math]:
Доказательство:
[math]\triangleright[/math]
[math]\forall x \in \left \{ 1 \dots n \right \}: \left | Ch(x) \right | \leqslant n[/math], поэтому [math]\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[/math].
[math]\triangleleft[/math]

См. также

Источники информации