Слайды и текст доклада
Pic.1
Построение и анализ алгоритмов Лекция 4 Динамическое программирование Оптимальные деревья поиска
Pic.2
Пример 3. Оптимальные деревья поиска См. начало в Лекции 3. См. также раздел 2. 8 пособия «Деревья кодирования и поиска»
Pic.3
Оптимальные деревья поиска Ранее при рассмотрении БДП, как правило, предполагалось, что для поиска различные ключи предъявляются с равной вероятностью. Пусть теперь заранее известно, что некоторые …
Pic.4
Пример дерева поиска из трех элементов a1 < a2 < a3 .
Pic.5
Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .
Pic.6
Постановка задачи Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1 < a2 < … < an–1 < an . A1, …, An- события, соответствующие …
Pic.7
Постановка задачи (продолжение) Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0 < A1 < B1 < A2 < … < Bn – 1 < An < Bn. Заданы вероятности (или частоты) этих …
Pic.8
Постановка задачи (продолжение) Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в виде где l (x) – уровень узла x (или длина пути от корня до узла x) в БДП. Здесь …
Pic.9
Постановка задачи (продолжение) Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с задачей построения оптимального префиксного кода ? В чём сходство, в чём различие? Ответ.
Pic.10
Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных деревьев с n узлами и выборе дерева с наименьшей стоимостью C0,n . Очевидное решение поставленной задачи …
Pic.11
Конец повторения прошлой лекции Решение поставленной задачи на следующей лекции.
Pic.12
Построение оптимальных деревьев поиска Дано: набор элементов a1 < a2 < … < an–1 < an . набор весов i1. . n pi + i0. . n qi = 1. Требуется: по заданным весам построить БДП, …
Pic.13
Идея Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода динамического программирования, левое и правое поддеревья этого дерева в свою очередь также должны …
Pic.14
Идея Tij -поддерево БДП из элементов (при 0 i j n). корнем поддерева может быть любой из элементов , т. е. k i +1. . j.
Pic.15
Обозначения Пусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,n L(X) - уровень узла, соответствующего событию X, в поддереве Tij Тогда l(X) = L(X) + l, где X {Bi, Ai+1, …, Bj}.
Pic.16
Вклад поддерева Tij в стоимость C0,n где Cij - стоимость поддерева Tij. wij - вес поддерева Tij.
Pic.17
Идея: структура дерева + принцип оптимальности
Pic.18
Преобразование + wij не зависит от структуры поддерева Tij
Pic.19
Cii = 0 разности индексов k – 1 i и j – k в слагаемых Ci,k1 и Ck,j меньше, чем разность индексов j – i в Cij. L = j – i , L=0. . n
Pic.20
Таблица (аналогия с задачей о перемножении цепочки матриц)
Pic.21
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 …
Pic.22
См. пример в файле «2_08_ОДП. doc» С. 67,68-…
Pic.23
Построение БДП 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, …
Pic.24
Модификация Д. Кнута ri,j 1 rij ri +1,j
Pic.26
КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ
Скачать презентацию
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!