Динамическое программирование Хорошие бинарные деревья поиска

Сентябрь 3, 2022

Главная
Алгебра
Динамическое программирование Хорошие бинарные деревья поиска

Содержание

2. 03.03.2014 Динамическое программирование Хорошие БДП Не оптимальные БДП, но достаточно хорошие Эвристика Выбор корня в БДП
3. 03.03.2014 Динамическое программирование Эвристика для хороших БДП R(i,j) – корень БДТ. Далее рекурсивно определяются корни поддеревьев.
4. 03.03.2014 Динамическое программирование Пример (см. лекцию 4.1. «Оптимальные БДП»)
5. 03.03.2014 Динамическое программирование a4 Хорошие деревья Хорошее дерево совпало с оптимальным !
6. 03.03.2014 Динамическое программирование Оптимальное сбалансированное БДП существует не всегда (Контр) пример. n = 3, qi =
7. 03.03.2014 Динамическое программирование
8. 03.03.2014 Динамическое программирование I II III p1 =  + 2ε, p2 =  − ε,
9. 03.03.2014 Динамическое программирование IV V p1 + 3p2 + 2p3= = 1 − 3ε p1 +
10. 03.03.2014 Динамическое программирование Смешанная тактика Пока n велико строим рекурсивно хорошее БДП Если для текущего поддерева
12. Скачать презентацию

Слайд 2

03.03.2014
Динамическое программирование
Хорошие БДП
Не оптимальные БДП, но достаточно хорошие
Эвристика
Выбор корня в БДП

так, чтобы веса поддеревьев различались минимально
(сбалансированность по весам)
Пусть, как и ранее,

0 ≤ i ≤ j ≤ n

Слайд 3

03.03.2014
Динамическое программирование
Эвристика для хороших БДП
R(i,j) – корень БДТ.
Далее рекурсивно определяются корни

поддеревьев.

БДП – сбалансировано, если каждая внутренняя вершина
балансирует поддерево, корнем которого она является

Слайд 4

03.03.2014
Динамическое программирование
Пример (см. лекцию 4.1. «Оптимальные БДП»)

Слайд 5

03.03.2014
Динамическое программирование
a4
Хорошие деревья
Хорошее дерево совпало с оптимальным !

Слайд 6

03.03.2014
Динамическое программирование
Оптимальное сбалансированное БДП существует не всегда
(Контр) пример.
n = 3, qi

= 0, при 0≤ i ≤ 3,
p1 = (a) =  + 2ε, p2 = p(a2) =  − ε, p3 = p(a3) =  − ε,

a1

a2

a3

q0 = 0

q1 = 0

q2 = 0

q3 = 0

 + 2ε

 − ε

 − ε

Слайд 7

03.03.2014
Динамическое программирование

Слайд 8

03.03.2014
Динамическое программирование
I
II
III
p1 =  + 2ε, p2 =  − ε,

p3 =  − ε,

3p1 + 2p2 + p1=
= 2 + 3ε

2p1 + 3p2 + p3=
= 2

2p1 + p2 + 2p3=
= 1 + ε

Хорошее БДП

Слайд 9

03.03.2014
Динамическое программирование
IV
V
p1 + 3p2 + 2p3=
= 1 − 3ε
p1 + 2p2

+ 3p3=
= 1 − 3ε

Оптимальные БДП

Слайд 10

03.03.2014
Динамическое программирование
Смешанная тактика
Пока n велико строим рекурсивно хорошее БДП
Если для текущего

поддерева n уже не очень велико, то строим оптимальное поддерево

Аналогия:
ср. построение оптимальных и хороших БДП
с алгоритмами построения
кодов Хаффмана и Фано-Шеннона