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

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

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

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

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

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

Постановка задачи Поиск будет осуществляться среди набора данных 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 = +, которые не должны использоваться в алгоритме.

Постановка задачи (продолжение) Все эти 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 – внешним узлам (листьям) расширенного дерева поиска.

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

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

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

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

Построение оптимальных деревьев поиска Дано: набор элементов a1 < a2 < … < an–1 < an . набор весов i1..n pi + i0..n qi = 1. Требуется: по заданным весам построить БДП, минимизирующее значение C0,n.

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

Идея Tij -поддерево БДП из элементов (при 0  i  j  n). корнем поддерева может быть любой из элементов , т. е. k  i +1..j.

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

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

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

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

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

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

for (i =0; i<n; i++) {c[i] [i] = 0; w[i] [i] = q[i];} //заполнена первая строка 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 }; } c[i][j] = c[i][j] + w[i][j]; } }

См. пример в файле «2_08_ОДП.doc» С.67,68-…

Построение БДП по таблице значений 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).

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

См. с.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.

КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ