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

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

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 26 слайдов и доступен в формате ppt. Размер файла: 660.50 KB

Просмотреть и скачать

Pic.1
Построение и анализ алгоритмов Лекция 4 Динамическое программирование Оптимальные деревья поиска
Построение и анализ алгоритмов Лекция 4 Динамическое программирование Оптимальные деревья поиска
Pic.2
Пример 3. Оптимальные деревья поиска См. начало в Лекции 3. См. также раздел 2. 8 пособия «Деревья к
Пример 3. Оптимальные деревья поиска См. начало в Лекции 3. См. также раздел 2. 8 пособия «Деревья кодирования и поиска»
Pic.3
Оптимальные деревья поиска Ранее при рассмотрении БДП, как правило, предполагалось, что для поиска р
Оптимальные деревья поиска Ранее при рассмотрении БДП, как правило, предполагалось, что для поиска различные ключи предъявляются с равной вероятностью. Пусть теперь заранее известно, что некоторые …
Pic.4
Пример дерева поиска из трех элементов a1 < a2 < a3 .
Пример дерева поиска из трех элементов a1 < a2 < a3 .
Pic.5
Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) =
Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .
Pic.6
Постановка задачи Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последов
Постановка задачи Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1 < a2 < … < an–1 < an . A1, …, An- события, соответствующие …
Pic.7
Постановка задачи (продолжение) Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0 &
Постановка задачи (продолжение) Все эти 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 . н
Построение оптимальных деревьев поиска Дано: набор элементов a1 < a2 < … < an–1 < an . набор весов i1. . n pi + i0. . n qi = 1. Требуется: по заданным весам построить БДП, …
Pic.13
Идея Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода дин
Идея Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода динамического программирования, левое и правое поддеревья этого дерева в свою очередь также должны …
Pic.14
Идея Tij -поддерево БДП из элементов (при 0  i  j  n). корнем поддерева может быть любой из элеме
Идея Tij -поддерево БДП из элементов (при 0  i  j  n). корнем поддерева может быть любой из элементов , т. е. k  i +1. . j.
Pic.15
Обозначения Пусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,n L(X) - уровень узла, соо
Обозначения Пусть 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.
Вклад поддерева Tij в стоимость C0,n где Cij - стоимость поддерева Tij. wij - вес поддерева Tij.
Pic.17
Идея: структура дерева + принцип оптимальности
Идея: структура дерева + принцип оптимальности
Pic.18
Преобразование + wij не зависит от структуры поддерева Tij
Преобразование + wij не зависит от структуры поддерева Tij
Pic.19
Cii = 0 разности индексов k – 1  i и j – k в слагаемых Ci,k1 и Ck,j меньше, чем разность индексов
Cii = 0 разности индексов k – 1  i и j – k в слагаемых Ci,k1 и 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
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-…
См. пример в файле «2_08_ОДП. doc» С. 67,68-…
Pic.23
Построение БДП BinT MakeOptBST (int i, j ) { int k; ElemBinT root; BinT L, R; k = num[i ][j ]; root
Построение БДП 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
Модификация Д. Кнута ri,j 1  rij  ri +1,j
Pic.25
См. с. 72
См. с. 72
Pic.26
КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!