Динамика по поддеревьям
Главной особенностью динамического программирования по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях. Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
Задача о паросочетании максимального веса в дереве
| Задача: |
| Пусть задано взвешенное дерево, с весами, обозначенными как [math]w_[/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_\limits \left ( b[y]+w_ +\sum_> \limits \max \left ( a[z],b[z] \right )\right )[/math] ,
- [math]b[x]=\sum_ \limits \max \left ( a[z], b[z] \right )[/math]
С учётом того, что [math]c[i]=\max \left ( a[i],b[i] \right )[/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_^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.
- Пути не проходящие через эту вершину. Это просто сумма суммы длин путей для всех поддеревьев детей или [math] \sum_ \limits F[x][/math] .
- Пути оканчивающиеся в вершине [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_ \limits <\Bigl(G[x] + S[x]\Bigl)>[/math] .
- Пути проходящие через вершину [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_ \limits <\Bigl(G[x]S[y] + G[y]S[x] + 2S[x]S[y]\Bigl)>[/math] . Но такой подсчет испортит асимптотику до [math] O(n^2) [/math] . Заметим, что [math] \sum_ \limits = \sum_ \limits \sum_ \limits [/math] . Но еще надо учесть, что [math] x \ne y [/math] , следовательно [math] \sum_ \limits = \sum_ \limits \sum_ \limits — \sum_ \limits [/math] . Аналогично для [math] S[x]S[y] [/math] . Итак: [math] H[v] = \biggl(\sum_ \limits \sum_ \limits — \sum_ \limits \biggl) + \biggl(\sum_ \limits \sum_ \limits — \sum_ \limits \biggl) [/math] .
Ответ задачи: [math] F[v] = \sum_ \limits F[x] + G[v] + H[v] [/math] . Асимптотика каждого слагаемого равна [math]O \left ( \sum_^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] :
См. также
Источники информации
Источник
Вывести все пути от корня до листовых узлов бинарного дерева
Для заданного бинарного дерева напишите эффективный алгоритм для вывода всех путей от корневого узла до каждого конечного узла в нем.
Например, рассмотрим следующее бинарное дерево:
The binary tree has four root-to-leaf paths:
1 —> 2 —> 4
1 —> 2 —> 5
1 —> 3 —> 6 —> 8
1 —> 3 —> 7 —> 9
Идея состоит в том, чтобы обойти дерево в предзаказ моды и сохранить каждый встреченный узел на текущем пути от корня к листу в векторе. Если мы встретим листовой узел, выведите все узлы, присутствующие в векторе. Ниже приведена реализация этой идеи на C++, Java и Python:
C++
результат:
1 2 4
1 2 5
1 3 6 8
1 3 7 9
Java
результат:
[1, 2, 4]
[1, 2, 5]
[1, 3, 6, 8]
[1, 3, 7, 9]
Python
результат:
[1, 2, 4]
[1, 2, 5]
[1, 3, 6, 8]
[1, 3, 7, 9]
Временная сложность приведенного выше решения равна O(n) , куда n это общее количество узлов в бинарном дереве. Программа требует O(h) дополнительное место для стека вызовов, где h это высота дерева.
Проблема кажется немного сложной для решения без рекурсии. Существует один обходной путь, когда мы сохраняем путь от корня к листу в строке, когда мы итеративно проходим по дереву, и печатаем путь всякий раз, когда встречаем какой-либо конечный узел. Это показано ниже на C++, Java и Python:
Источник