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

Нажмите для полного просмотра!

Динамическое программирование Оптимальные деревья поиска, слайд №2

Динамическое программирование Оптимальные деревья поиска, слайд №3

Динамическое программирование Оптимальные деревья поиска, слайд №4

Динамическое программирование Оптимальные деревья поиска, слайд №5

Динамическое программирование Оптимальные деревья поиска, слайд №6

Динамическое программирование Оптимальные деревья поиска, слайд №7

Динамическое программирование Оптимальные деревья поиска, слайд №8

Динамическое программирование Оптимальные деревья поиска, слайд №9

Динамическое программирование Оптимальные деревья поиска, слайд №10

Динамическое программирование Оптимальные деревья поиска, слайд №11

Динамическое программирование Оптимальные деревья поиска, слайд №12

Динамическое программирование Оптимальные деревья поиска, слайд №13

Динамическое программирование Оптимальные деревья поиска, слайд №14

Динамическое программирование Оптимальные деревья поиска, слайд №15

Динамическое программирование Оптимальные деревья поиска, слайд №16

Динамическое программирование Оптимальные деревья поиска, слайд №17

Динамическое программирование Оптимальные деревья поиска, слайд №18

Динамическое программирование Оптимальные деревья поиска, слайд №19

Динамическое программирование Оптимальные деревья поиска, слайд №20

Динамическое программирование Оптимальные деревья поиска, слайд №21

Динамическое программирование Оптимальные деревья поиска, слайд №22

Динамическое программирование Оптимальные деревья поиска, слайд №23

Динамическое программирование Оптимальные деревья поиска, слайд №24

Динамическое программирование Оптимальные деревья поиска, слайд №25

Динамическое программирование Оптимальные деревья поиска, слайд №26

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Динамическое программирование Оптимальные деревья поиска. Доклад-сообщение содержит 26 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Пример дерева поиска из трех элементов a1

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Постановка задачи (продолжение) Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Конец повторения прошлой лекции Решение поставленной задачи на следующей лекции.

Слайд 12

Описание слайда:

Построение оптимальных деревьев поиска Дано: набор элементов a1

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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