Построение и анализ алгоритмов. Динамическое программирование. Оптимальные деревья поиска. (Лекция 4)

Август 6, 2022

Главная
Информатика
Построение и анализ алгоритмов. Динамическое программирование. Оптимальные деревья поиска. (Лекция 4)

Содержание

2. 16.02.2016 Динамическое программирование Пример 3. Оптимальные деревья поиска См. начало в Лекции 3. См. также раздел
3. Оптимальные деревья поиска Ранее при рассмотрении БДП, как правило, предполагалось, что для поиска различные ключи предъявляются
4. 16.02.2016 Динамическое программирование Пример дерева поиска из трёх элементов a1
5. Заданы вероятности предъявления элемента x для поиска: P (x = a1) = α; P (x =
6. Постановка задачи Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена:
7. Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0 Заданы вероятности (или частоты)
8. Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в виде где l (x) –
9. Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с задачей построения оптимального префиксного кода
10. Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных деревьев с n узлами и
11. Конец повторения прошлой лекции 16.02.2016 Динамическое программирование
12. Построение оптимальных деревьев поиска Дано: набор элементов a1 набор весов Σi∈1..n pi + Σi∈0..n qi =
13. Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода динамического программирования, левое и правое
14. Идея Tij -поддерево БДП из элементов (при 0 ≤ i ≤ j ≤ n). корнем поддерева
15. Обозначения Пусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,n L(X) - уровень
16. Вклад поддерева Tij в стоимость C0,n где Cij - стоимость поддерева Tij. wij - вес поддерева
17. Идея: структура дерева + принцип оптимальности 16.02.2016 Динамическое программирование
18. Преобразование + wij не зависит от структуры поддерева Tij 16.02.2016 Динамическое программирование
19. Cii = 0 разности индексов k – 1 − i и j – k в слагаемых
20. Таблица (аналогия с задачей о перемножении цепочки матриц) 16.02.2016 Динамическое программирование
21. for (i =0; i for (L=1; L for (i=0; i j = i + L; //
22. См. пример в файле «2_08_ОДП.doc» С.67,68-… 16.02.2016 Динамическое программирование
23. Построение БДП по таблице значений num BinT MakeOptBST (int i, j ) { int k; ElemBinT
24. Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j 16.02.2016 Динамическое программирование Вместо k = (i
25. См. с.72 Так в ранее рассмотренном примере на последнем шаге при вычислении C0,4 вместо рассмотрения четырёх
27. Скачать презентацию

Слайд 2

16.02.2016
Динамическое программирование
Пример 3. Оптимальные деревья поиска
См. начало в Лекции 3.
См. также

раздел 2.8
пособия «Деревья кодирования и поиска»

Слайд 3

Оптимальные деревья поиска
Ранее при рассмотрении БДП, как правило, предполагалось, что для

поиска различные ключи предъявляются с равной вероятностью.
Пусть теперь заранее известно, что некоторые ключи предъявляются чаще других.
Тогда расположение «частых» ключей ближе к корню дерева сократит время их поиска и, возможно, среднее время поиска (по разным предъявлениям ключей).

16.02.2016

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

Слайд 4

16.02.2016
Динамическое программирование
Пример дерева поиска из трёх элементов a1 < a2 < a3 .

Слайд 5

Заданы вероятности предъявления элемента x для поиска: P (x = a1) = α; P (x = a2) = β;

P (x = a3) = γ.

16.02.2016

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

Среднее (по всем предъявлениям x) число сравнений (стоимость) в случаях успешного поиска как функция переменных α, β и γ,

Слайд 6

Постановка задачи
Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an.
Пусть последовательность упорядочена:

a1 < a2 < … < an–1 < an .
A1, …, An- события, соответствующие вариантам успешных исходов поиска,
т. е. Ai : (x = ai) для i ∈ 1..n,
B0, …, Bn - события, соответствующие вариантам неудачных исходов поиска,
т. е. Bi : (ai < x < ai+1) для i ∈ 0..n.
Здесь для упрощения записи событий B0 и Bn добавлены фиктивные элементы a0 = −∞ и an+1 = +∞, которые не должны использоваться в алгоритме.

16.02.2016

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

Слайд 7

Все эти 2n + 1 событий (исходов поиска)
могут быть упорядочены:
B0 < A1 < B1 < A2 < … < Bn – 1 < An < Bn.
Заданы вероятности

(или частоты) этих событий:
pi = P (Ai) для i ∈ 1..n, и qi = P (Bi) для i ∈ 0..n.
При этом Σi∈1..n pi + Σi∈0..n qi = 1.
События Ai соответствуют внутренним узлам расширенного дерева поиска, а события Bi – внешним узлам (листьям) расширенного дерева поиска.

16.02.2016

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

Постановка задачи (продолжение)

Слайд 8

Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в

виде
где l (x) – уровень узла x (или длина пути от корня до узла x) в БДП.
Здесь уровень узла определён так, что l (корень) = 0.

16.02.2016

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

Постановка задачи (продолжение)

Итак, задача состоит в том, чтобы по заданным весам
построить БДП, минимизирующее значение C0,n .

Слайд 9

Такое дерево называют оптимальным БДП.
Есть ли сходство этой задачи с

задачей построения оптимального префиксного кода ?
В чём сходство, в чём различие?
Ответ.

16.02.2016

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

Постановка задачи (продолжение)

Слайд 10

Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных

деревьев с n узлами и выборе дерева с наименьшей стоимостью C0,n .
Однако поскольку (см. лекции про БДП) число bn структурно различных бинарных деревьев с n узлами есть
, то этот способ вряд ли будет иметь практическую ценность.
Оказывается, приемлемое по количеству вычислений решение данной задачи может быть получено методом динамического программирования.

16.02.2016

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

Слайд 11

Конец повторения прошлой лекции
16.02.2016
Динамическое программирование

Слайд 12

Построение оптимальных деревьев поиска
Дано:
набор элементов a1 < a2 < … < an–1 < an .
набор весов
Σi∈1..n pi + Σi∈0..n qi = 1.
Требуется: по

заданным весам построить БДП, минимизирующее значение C0,n.

16.02.2016

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

Слайд 13

Пусть имеется оптимальное дерево.
Согласно принципу оптимальности, лежащему в основе метода

динамического программирования, левое и правое поддеревья этого дерева в свою очередь также должны быть оптимальны.

16.02.2016

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

Идея

Слайд 14

Идея
Tij -поддерево БДП из элементов
(при 0 ≤ i ≤ j ≤ n).
корнем поддерева может

быть любой из элементов , т. е. k ∈ i +1..j.

16.02.2016

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

Слайд 15

Обозначения
Пусть
l = l(rij)- уровень корня rij поддерева Tij в дереве T0,n
L(X)

- уровень узла, соответствующего событию X, в поддереве Tij . ( L(rij)=0 )
Тогда l(X) = L(X) + l, где X ∈{Bi, Ai+1, …, Bj}.

16.02.2016

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

l = l(rij)

rij

L(X)

l(X)

Слайд 16

Вклад поддерева Tij в стоимость C0,n
где
Cij - стоимость поддерева Tij.
wij

- вес поддерева Tij.

16.02.2016

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

Слайд 17

Идея: структура дерева + принцип оптимальности
16.02.2016
Динамическое программирование

Слайд 18

Преобразование
+
wij не зависит от структуры поддерева Tij
16.02.2016
Динамическое программирование

Слайд 19

Cii = 0
разности индексов k – 1 − i и j – k в слагаемых Ci,k−1 и Ck,j меньше,

чем разность индексов j – i в Cij.
L = j – i , L=0..n

16.02.2016

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

Слайд 20

Таблица (аналогия с задачей о перемножении цепочки матриц)
16.02.2016
Динамическое программирование

Слайд 21

for (i =0; i for

(L=1; L for (i=0; i j = i + L; // заполнение T(i, j):
w[i][ j] = w[i][j −1] + (p[j]+q[j]);
c[i][j] = +∞;
for (k =i +1 ; k< j-1; k++) { s = c[i][k −1] + c [k][j];
if (s < c[i][j] ){
c[i][j] = s;
num[i][j] = k
};
}
c[i][j] = c[i][j] + w[i][j];
}
}

16.02.2016

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

n 2/2 элементов памяти и n 3/3 выполнений тела внутреннего цикла

Вычисление таблицы

Слайд 22

См. пример в файле «2_08_ОДП.doc»
С.67,68-…
16.02.2016
Динамическое программирование

Слайд 23

Построение БДП по таблице значений num
BinT MakeOptBST (int i, j )
{ int k; ElemBinT

root;
BinT L, R;
k = num[i ][j ]; root = a[k];
if (i < k −1) L = MakeOptBST (i, k −1);
else L = NULL;
if (k < j ) R = MakeOptBST (k, j);
else R = NULL;
return ConsBT (root, L, R);
} //MakeOptBST
со стартовым вызовом T = MakeOptBST (0, n).

16.02.2016

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

Слайд 24

Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j
16.02.2016
Динамическое программирование
Вместо k = (i +1) .. j ⇒ k =

num[i ][j −1] .. num[i +1][j ]

Слайд 25

См. с.72
Так в ранее рассмотренном примере
на последнем шаге при вычислении

C0,4
вместо рассмотрения четырёх кандидатов на роль корня дерева (см. с.70)
ak (k = 1, 2, 3, 4)
можно ограничиться лишь двумя (a1 и a2), поскольку
num[0, 3] ≤ k ≤ num[1, 4],
а num[0, 3] = 1 и num[1, 4] = 2.

16.02.2016

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

Построение и анализ алгоритмов. Динамическое программирование. Оптимальные деревья поиска. (Лекция 4)

Содержание

16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало в Лекции 3.См. также

Оптимальные деревья поискаРанее при рассмотрении БДП, как правило, предполагалось, что для

16.02.2016Динамическое программированиеПример дерева поиска из трёх элементов a1 < a2 < a3 .

Заданы вероятности предъявления элемента x для поиска: P (x = a1) = α; P (x = a2) = β;

Постановка задачиПоиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена:

Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0 < A1 < B1 < A2 < … < Bn – 1 < An < Bn.Заданы вероятности

Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в

Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с

Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных

Конец повторения прошлой лекции16.02.2016Динамическое программирование

Построение оптимальных деревьев поискаДано: набор элементов a1 < a2 < … < an–1 < an . набор весовΣi∈1..n pi + Σi∈0..n qi = 1.Требуется: по

Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода

ИдеяTij -поддерево БДП из элементов(при 0 ≤ i ≤ j ≤ n). корнем поддерева может

ОбозначенияПусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,nL(X)

Вклад поддерева Tij в стоимость C0,nгдеCij - стоимость поддерева Tij. wij

Идея: структура дерева + принцип оптимальности16.02.2016Динамическое программирование

Преобразование+wij не зависит от структуры поддерева Tij 16.02.2016Динамическое программирование

Cii = 0разности индексов k – 1 − i и j – k в слагаемых Ci,k−1 и Ck,j меньше,

Таблица (аналогия с задачей о перемножении цепочки матриц)16.02.2016Динамическое программирование

for (i =0; i for

См. пример в файле «2_08_ОДП.doc»С.67,68-…16.02.2016Динамическое программирование

Построение БДП по таблице значений numBinT MakeOptBST (int i, j ){ int k; ElemBinT

Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j 16.02.2016Динамическое программированиеВместо k = (i +1) .. j ⇒ k =

См. с.72 Так в ранее рассмотренном примере на последнем шаге при вычислении

Похожие презентации

16.02.2016
Динамическое программирование
Пример 3. Оптимальные деревья поиска
См. начало в Лекции 3.
См. также

Оптимальные деревья поиска
Ранее при рассмотрении БДП, как правило, предполагалось, что для

16.02.2016
Динамическое программирование
Пример дерева поиска из трёх элементов a1 < a2 < a3 .

Постановка задачи
Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an.
Пусть последовательность упорядочена:

Все эти 2n + 1 событий (исходов поиска)
могут быть упорядочены:
B0 < A1 < B1 < A2 < … < Bn – 1 < An < Bn.
Заданы вероятности

Такое дерево называют оптимальным БДП.
Есть ли сходство этой задачи с

Конец повторения прошлой лекции
16.02.2016
Динамическое программирование

Построение оптимальных деревьев поиска
Дано:
набор элементов a1 < a2 < … < an–1 < an .
набор весов
Σi∈1..n pi + Σi∈0..n qi = 1.
Требуется: по

Пусть имеется оптимальное дерево.
Согласно принципу оптимальности, лежащему в основе метода

Идея
Tij -поддерево БДП из элементов
(при 0 ≤ i ≤ j ≤ n).
корнем поддерева может

Обозначения
Пусть
l = l(rij)- уровень корня rij поддерева Tij в дереве T0,n
L(X)

Вклад поддерева Tij в стоимость C0,n
где
Cij - стоимость поддерева Tij.
wij

Идея: структура дерева + принцип оптимальности
16.02.2016
Динамическое программирование

Преобразование
+
wij не зависит от структуры поддерева Tij
16.02.2016
Динамическое программирование

Cii = 0
разности индексов k – 1 − i и j – k в слагаемых Ci,k−1 и Ck,j меньше,

Таблица (аналогия с задачей о перемножении цепочки матриц)
16.02.2016
Динамическое программирование

См. пример в файле «2_08_ОДП.doc»
С.67,68-…
16.02.2016
Динамическое программирование

Построение БДП по таблице значений num
BinT MakeOptBST (int i, j )
{ int k; ElemBinT

Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j
16.02.2016
Динамическое программирование
Вместо k = (i +1) .. j ⇒ k =

См. с.72
Так в ранее рассмотренном примере
на последнем шаге при вычислении