Редактирование: Динамика по поддеревьям

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.
+
=Динамика по поддеревьям=
 +
 
 +
Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
 
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
 
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
 +
==Задача о максимальном взвешенном паросочетании на дереве==
 +
===Формулировка===
 +
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.
  
== Задача о паросочетании максимального веса в дереве ==
+
===Решение===
 
+
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
{{Задача
+
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
|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[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>
+
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
'''function''' dfs(x: '''int''', a: '''int[]''', b: '''int[]''', c: '''int[]''', w: '''int[][]''', Ch: '''int[]'''):
+
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>  
    '''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])
 
  
== Задача о сумме длин всех путей в дереве ==
+
<tex>dp(u, 0) = \sum_{\text{child}\ v\  of\  u}dp(v, 1)</tex><br>
{{Задача
+
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x]  \}\right\}</tex>
|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> количество путей оканчивающихся вершиной <tex> v </tex>, <tex> H[v]\ - </tex> количество путей проходящих через вершину <tex> v </tex>. Если вершина <tex> u </tex> лист, то <tex> S[u] </tex> = 1, а <tex> G[u] </tex> = 0.
+
Заметим, что вторую формулу можно упростить:<br>
# Пути не проходящие через эту вершину. Это просто сумма суммы длин для всех поддеревьев детей или <tex> \sum_{x \in Ch(v)} \limits F[x]</tex>.
+
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</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 \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] = 2\biggl(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x]\Bigl)} \biggl) + 2\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>.
+
Теперь наши формулы имеют вид:<br>
 +
<tex>dp(u, 0) = \sum_{\text{child}\ v\  of\  u}dp(v, 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>
  
== Амортизированные оценки для ДП на дереве ==
+
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</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>.
 
}}
 
  
==См. также==
+
===Реализация===
* [[Задача коммивояжера, ДП по подмножествам]]
+
    calculate(v, useRoot):
* [[Задача о числе путей в ациклическом графе]]
+
        if dp[v][useRoot] != -1:
 +
            return dp[v][useRoot]      //вернули уже посчитанное значение dp[vertex][root]
 +
        sum = 0
 +
        if use_root == 0:                    //случай 1: не берем ребра из корня
 +
            for (для) всех u из множества детей v:
 +
                sum += calculate(u, 1)
 +
            dp[v][useRoot] = sum     
 +
            return sum
 +
        max1 = dp[v][0]                 //случай 2: берем какое-то ребро
 +
        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/c14aca73a4926918a879905ffcd4ad7a/timb86.pdf В. В. Лепин, Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве]
+
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]
* [http://ru.wikipedia.org/wiki/Паросочетание Википедия — Паросочетание]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]
[[Категория: Другие задачи динамического программирования]]
 
[[Категория:Алгоритмы на графах]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: