Сумма всех весов вершин дерева

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

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

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

Задача:

Пусть задано взвешенное дерево, с весами, обозначенными как [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.

1. Пути не проходящие через эту вершину. Это просто сумма суммы длин путей для всех поддеревьев детей или [math] \sum_ \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_ \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_ \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] :

См. также

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

Источник

построение идеально сбалансированных бинарных деревьев. Пособие_СиАОД. Методическое пособие Новосибирск 2006 удк 681 06

Единственный в мире Музей Смайликов

Самая яркая достопримечательность Крыма

Скачать 1.96 Mb.

П ример построения двоичного Б-дерева приведен на следующем рисунке.

1. Варианты заданий
1. Написать процедуру поиска элемента с заданным ключом в Б-дереве порядка m.
2. Определить трудоемкость поиска в Б-дереве порядка m.
3. Написать процедуру определения высоты Б-дерева порядка m.
4. Запрограммировать процедуру добавления нового элемента в Б-дерева порядка m.
5. Графически изобразить Б-дерево порядка 2.
6. Запрограммировать процедуру добавления новой вершины в двоичное Б-дерево. Определить количество необходимых операций для добавления вершины.
7. Написать процедуру определения высоты двоичного Б-дерева.
8. Экспериментально сравнить двоичное Б-дерево и ИСДП по высоте как двоичные деревья.
9. Экспериментально сравнить высоты двоичного Б-дерева и случайного дерева поиска как двоичные деревья.
10. Экспериментально сравнить двоичное Б-дерево и АВЛ-дерево по высоте как двоичные деревья.
11. Графически изобразить двоичное Б-дерево.

Припишем каждой вершине дерева V_i вес w_i, пропорциональный частоте поиска этой вершины (например, если из каждых 100 операций поиска 15 операций приходятся на вершину V₁, то w₁=15). Сумма весов всех вершин дает вес дерева W. Каждая вершина V_i расположена на высоте h_i, корень расположен на высоте 1. Высота вершины равна количеству операций сравнения, необходимых для поиска этой вершины. Определим средневзвешенную высоту дерева с n вершинами следующим образом: h_ср=(w₁h₁+w₂h₂+…+w_nh_n)/W. Дерево поиска, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска (ДОП).

Пример. Рассмотрим множество из трех ключей V₁=1, V₂=2, V₃=3 со следующими весами: w₁=60, w₂=30, w₃=10, W=100. Эти три ключа можно расставить в дереве поиска пятью различными способами.

Рисунок 57 Различные деревья поиска с вершинами V ₁ =1, V ₂ =2, V ₃ =3

Легко видеть, что минимальной средневзвешенной высотой обладает дерево 1 на рисунке 57, которое представляет собой список или вырожденное дерево. Дерево 3 не является деревом оптимального поиска, хотя представляет собой идеально сбалансированное дерево. Очевидно, для минимизации средней длины пути поиска нужно стремится располагать наиболее часто используемые вершины ближе к корню дерева.

• Известны вершины и их веса.
• Вес вершины определяется в процессе работы. Например, после каждого поиска вершины ее вес увеличивается на 1. В этом случае необходимо перестраивать структуру дерева при изменении весов.
1. Точный алгоритм построения ДОП

Свойство 1. Для дерева поиска с весом W справедливо соотношение P=P_L+W+P_R, где P_L, P_R – взвешенные высоты левого и правого поддеревьев корня.

Доказательство. Пусть вершина V_i с весом w_iявляется корневой для некоторого i=1, …n. Поскольку левое и правое поддеревья являются деревьями поиска, то в левое поддерево входят вершины V₁, V₂, …, V_i-1, а в правое – V_i+1, …, V_n. Взвешенные высоты этих поддеревьев вычисляются следующим образом.

P_L = (h₁-1)w₁+(h₂-1)w₂+…+(h_i-1-1)w_i-1

P_R = (h_i+1-1)w_i+1+ …+ (h_n-1)w_n

Рассмотрим выражение взвешенной высоты для всего дерева, замечая, что h_i=1

P=h₁w₁+h₂w₂+…+h_nw_n= (h₁-1)w₁ + w₁+(h₂-1)w₂+ w₂…+(h_i-1-1)w_i-1 + w_i-1 +

+ w_i + (h_i+1-1)w_i+1+ w_i+1 …+ (h_n-1)w_n + w_n = P_L+W+P_R

Свойство 2. Все поддеревья дерева оптимального поиска также являются деревьями оптимального поиска для соответствующих подмножеств вершин.

Доказательство. Предположим, что одно из поддеревьев, например, правое, не является ДОП, т.е. существует дерево поиска с тем же множеством вершин, но с меньшей взвешенной высотой. Тогда по свойству 1 взвешенная высота всего дерева также не является минимальной. Данное противоречие доказывает свойство 2.

На основе приведенных свойств можно разработать точный алгоритм построения ДОП. Обозначим T_ij – оптимальное поддерево, состоящее из вершин V_i+1, …, V_j. Введем матрицу АR=||Ar_ij||, 0≤i,j≤n элементы которой содержат номер корневой вершины поддерева T_ij, 0≤i * , при котором достигается минимум во втором соотношении. Значение k * является индексом корневой вершины поддерева T_ij во всем множестве вершин. Занесем в матрицу АR k * –индекс корня T_ij, т.е. Ar_ij = k * , 0≤i

Источник

Читайте также:  Коробки для десертов под дерево