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

1. Построение и анализ алгоритмов

Лекция 4
Динамическое программирование
Оптимальные деревья поиска
16.02.2016
Динамическое
программирование
1

2. Пример 3. Оптимальные деревья поиска

См. начало в Лекции 3.
См. также раздел 2.8
пособия «Деревья кодирования и поиска»
16.02.2016
Динамическое
программирование
2

3. Оптимальные деревья поиска

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

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

a3
I
a2
III
a3
II
a1
a1
a2
a3
a1
a2
IV
a1
V
Пример дерева
поиска из трёх
элементов
a1 < a2 < a3 .
a1
a3
a2
a2
a3
Рис. 2.9. Все различные расширенные БДП из трёх элементов a1 < a2 < a3
16.02.2016
Динамическое
программирование
4

5. Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .

Заданы вероятности предъявления элемента x для
поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .
Дерево
Варианты значений , и
Стоимость
= 1/3
= 3/6
= 4/7
= 5/8
= 1/3
= 2/6
= 2/7
= 2/8
= 1/3
= 1/6
= 1/7
= 1/8
Значения стоимости при заданных , и
I
3 + 2 +
6/3
14/6
17/7
20/8
II
2 + 3 +
6/3
13/6
15/7
17/8
III
2 + + 2
5/3
10/6
12/7
14/8
IV
+ 3 + 2
6/3
11/6
12/7
13/8
V
+ 2 + 3
6/3
10/6
11/7
12/8
Среднее (по всем предъявлениям x) число сравнений (стоимость) в
случаях успешного поиска как функция переменных , и ,
16.02.2016
Динамическое
программирование
5

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
Динамическое
программирование
6

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

Все эти 2n + 1 событий (исходов поиска)
n
( Ai )1
n
( Bi ) 0
могут быть упорядочены:
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
Динамическое
программирование
7

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

Тогда среднее число (математическое ожидание)
сравнений при поиске можно записать в виде
n
n
i 1
i 0
С0, n pi (l ( Ai ) 1) qi l ( Bi ),
где l (x) – уровень узла x (или длина пути от корня до
узла x) в БДП.
Здесь уровень узла определён так, что l (корень) = 0.
Итак, задача состоит в том, чтобы по заданным весам
pi 1n и qi 0n
построить БДП, минимизирующее значение C0,n .
16.02.2016
Динамическое
программирование
8

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

Такое дерево называют оптимальным БДП.
Есть ли сходство этой задачи с задачей построения
оптимального префиксного кода ?
В чём сходство, в чём различие?
Ответ.
16.02.2016
Динамическое
программирование
9

10.

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

11. Конец повторения прошлой лекции

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

12. Построение оптимальных деревьев поиска

Дано:
1)набор элементов a1 < a2 < … < an–1 < an .
2) набор весов
n
n
pi 1 и qi 0
1) i 1..n pi + i 0..n qi = 1.
Требуется: по заданным весам построить БДП,
минимизирующее значение C0,n.
n
n
i 1
i 0
С0, n pi (l ( Ai ) 1) qi l ( Bi ),
16.02.2016
Динамическое
программирование
12

13. Идея

Пусть имеется оптимальное дерево.
Согласно принципу оптимальности, лежащему в
основе метода динамического программирования,
левое и правое поддеревья этого дерева в свою
очередь также должны быть оптимальны.
16.02.2016
Динамическое
программирование
13

14. Идея

Tij -поддерево БДП из элементов
(при 0 i j n).
ai 1 , ..., a j
Tij БДП{ai 1, ..., a j }
ak
aj
a i 1
Bi
Bj
Рис. 2.10. Структура расширенного поддерева Tij
корнем поддерева может быть любой из элементов , т. е. k i +1..j.
16.02.2016
Динамическое
программирование
14

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}.
l(X)
l = l(rij)
rij
L(X)
16.02.2016
Динамическое
программирование
15

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

j
k i 1
j
j
pk (l ( Ak ) 1) qk l ( Bi )
k i
j
k i 1
k i 1
j
pk ( L( Ak ) l 1) qk ( L( Bi ) l )
k i
j
j
pk ( L( Ak ) 1) qk L( Bi ) (
k i
k i 1
j
pk qk ) l Cij wij l ,
k i
где
j
Cij
k i 1
j
pk ( L( Ak ) 1) qk L( Bi ),
k i
j
wij
k i 1
j
pk qk .
k i
Cij - стоимость поддерева Tij.
wij - вес поддерева Tij.
wij wi, j 1 ( p j q j )
16.02.2016
Динамическое
программирование
16

17. Идея: структура дерева + принцип оптимальности

ak
aj
a i 1
Bi
Bj
Рис. 2.10. Структура расширенного поддерева Tij
Сij min {Сi,k 1 Сk , j ( wi,k 1 wk , j pk )}
i k j
16.02.2016
Динамическое
программирование
17

18. Преобразование

Сij min {Сi,k 1 Сk , j ( wi,k 1 wk , j pk )}
i k j
wi,k 1 wk , j pk wij
+
wij не зависит от структуры поддерева Tij
Сij min {Сi,k 1 Сk , j } wij
i k j
16.02.2016
Динамическое
программирование
18

19.

1) Cii = 0
2) разности индексов k – 1 i и j – k в слагаемых
Ci,k 1 и Ck,j меньше, чем разность индексов j – i в Cij.
3) L = j – i , L=0..n
16.02.2016
Динамическое
программирование
19

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

l=0
Т(0, 0)
Т(1, 1)
Т(2, 2)
Т(3, 3)
…
l=1
Т(0, 1)
Т(1, 2)
Т(2, 3)
…
Т(n 2, n 1)
l=2
Т(0, 2)
Т(1, 3)
…
Т(n 3, n 1)
Т(n 2, n)
…
…
…
…
…
l = n –2
Т(0, n 2) Т(1, n 1) Т(2, n)
l = n –1
Т(0, n 1)
l=n
Т(0, n)
Т(1, n)
Т(n 1, n 1) Т(n, n)
Т(n 1, n)
Tij:
wij=
Cij=
Numij=
arg min {Сi ,k 1 Сk , j } Num
i k j
16.02.2016
Динамическое
программирование
20

21.

for (i =0; i<n; i++) {c[i] [i] = 0; w[i] [i] = q[i];} //заполнена первая строка
for (L=1; L<n; L++) {
for (i=0; i<n-L; 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
};
n 2/2 элементов
}
памяти и n 3/3
c[i][j] = c[i][j] + w[i][j]; выполнений тела
внутреннего цикла
}
}
16.02.2016
Динамическое
программирование
21

22.

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

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
Динамическое
программирование
23

24. Модификация Д.Кнута ri,j 1  rij  ri +1,j

Модификация Д.Кнута
ri,j 1 rij ri +1,j
ri, j 1
Bi
Ai+1 Bi+1
rij
…
ri +1, j
Aj 1 Bj 1 Aj
Bj
Рис. 2.14. Соотношение между корнями поддеревьев оптимального БДП
Вместо k = (i +1) .. j
16.02.2016
k = num[i ][j 1] .. num[i +1][j ]
Динамическое
программирование
24

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
Динамическое
программирование
25

26.

КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
16.02.2016
Динамическое
программирование
26