- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Построение и анализ алгоритмов. Динамическое программирование. Оптимальные деревья поиска. (Лекция 4)
Содержание
- 2. 16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало
- 3. Оптимальные деревья поискаРанее при рассмотрении БДП, как
- 4. 16.02.2016Динамическое программированиеПример дерева поиска из трёх элементов a1
- 5. Заданы вероятности предъявления элемента x для поиска:
- 6. Постановка задачиПоиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1
- 7. Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0
- 8. Тогда среднее число (математическое ожидание) сравнений при
- 9. Такое дерево называют оптимальным БДП. Есть ли
- 10. Очевидное решение поставленной задачи состоит в переборе
- 11. Конец повторения прошлой лекции16.02.2016Динамическое программирование
- 12. Построение оптимальных деревьев поискаДано: набор элементов a1
- 13. Пусть имеется оптимальное дерево. Согласно принципу оптимальности,
- 14. ИдеяTij -поддерево БДП из элементов(при 0 ≤ i ≤ j
- 15. ОбозначенияПусть l = l(rij)- уровень корня rij поддерева
- 16. Вклад поддерева Tij в стоимость C0,nгдеCij - стоимость поддерева Tij. wij - вес поддерева Tij.16.02.2016Динамическое программирование
- 17. Идея: структура дерева + принцип оптимальности16.02.2016Динамическое программирование
- 18. Преобразование+wij не зависит от структуры поддерева Tij 16.02.2016Динамическое программирование
- 19. Cii = 0разности индексов k – 1 − i и j – k в слагаемых
- 20. Таблица (аналогия с задачей о перемножении цепочки матриц)16.02.2016Динамическое программирование
- 21. for (i =0; i
- 22. См. пример в файле «2_08_ОДП.doc»С.67,68-…16.02.2016Динамическое программирование
- 23. Построение БДП по таблице значений numBinT MakeOptBST (int
- 24. Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j 16.02.2016Динамическое программированиеВместо k = (i +1)
- 25. См. с.72 Так в ранее рассмотренном примере
- 26. Скачать презентацию
- 27. Похожие презентации
16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало в Лекции 3.См. также раздел 2.8 пособия «Деревья кодирования и поиска»
Слайд 2
16.02.2016
Динамическое программирование
Пример 3. Оптимальные деревья поиска
См. начало в
Лекции 3.
поиска»
Слайд 3
Оптимальные деревья поиска
Ранее при рассмотрении БДП, как правило,
предполагалось, что для поиска различные ключи предъявляются с равной
вероятностью.Пусть теперь заранее известно, что некоторые ключи предъявляются чаще других.
Тогда расположение «частых» ключей ближе к корню дерева сократит время их поиска и, возможно, среднее время поиска (по разным предъявлениям ключей).
16.02.2016
Динамическое программирование
Слайд 5 Заданы вероятности предъявления элемента x для поиска: P
(x = a1) = α; P (x = a2) = β; P (x = a3) = γ.
16.02.2016
Динамическое программирование
Среднее (по всем
предъявлениям x) число сравнений (стоимость) в случаях успешного поиска как функция переменных α, β и γ,
Слайд 6
Постановка задачи
Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an.
Пусть последовательность упорядочена:
a1
успешных исходов поиска, т. е. Ai : (x = ai) для i ∈ 1..n,
B0, …, Bn - события, соответствующие вариантам неудачных исходов поиска,
т. е. Bi : (ai < x < ai+1) для i ∈ 0..n.
Здесь для упрощения записи событий B0 и Bn добавлены фиктивные элементы a0 = −∞ и an+1 = +∞, которые не должны использоваться в алгоритме.
16.02.2016
Динамическое программирование
Слайд 7
Все эти 2n + 1 событий (исходов поиска)
могут быть упорядочены:
B0
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
Динамическое программирование
Постановка задачи (продолжение)
Слайд 8 Тогда среднее число (математическое ожидание) сравнений при поиске
можно записать в виде
где l (x) – уровень узла
x (или длина пути от корня до узла x) в БДП. Здесь уровень узла определён так, что l (корень) = 0.
16.02.2016
Динамическое программирование
Постановка задачи (продолжение)
Итак, задача состоит в том, чтобы по заданным весам
построить БДП, минимизирующее значение C0,n .
Слайд 9
Такое дерево называют оптимальным БДП.
Есть ли сходство
этой задачи с задачей построения оптимального префиксного кода ?
В
чём сходство, в чём различие?Ответ.
16.02.2016
Динамическое программирование
Постановка задачи (продолжение)
Слайд 10 Очевидное решение поставленной задачи состоит в переборе всех
структурно различных бинарных деревьев с n узлами и выборе
дерева с наименьшей стоимостью C0,n .Однако поскольку (см. лекции про БДП) число bn структурно различных бинарных деревьев с n узлами есть
, то этот способ вряд ли будет иметь практическую ценность.
Оказывается, приемлемое по количеству вычислений решение данной задачи может быть получено методом динамического программирования.
16.02.2016
Динамическое программирование
Слайд 12
Построение оптимальных деревьев поиска
Дано:
набор элементов a1
набор весов
Σi∈1..n pi + Σi∈0..n qi = 1.
Требуется: по заданным весам построить БДП, минимизирующее значение
C0,n. 16.02.2016
Динамическое программирование
Слайд 13
Пусть имеется оптимальное дерево.
Согласно принципу оптимальности, лежащему
в основе метода динамического программирования, левое и правое поддеревья
этого дерева в свою очередь также должны быть оптимальны.16.02.2016
Динамическое программирование
Идея
Слайд 14
Идея
Tij -поддерево БДП из элементов
(при 0 ≤ i ≤ j ≤ n).
корнем поддерева может быть любой из элементов , т. е.
k ∈ i +1..j.16.02.2016
Динамическое программирование
Слайд 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}.
16.02.2016
Динамическое программирование
l = l(rij)
rij
L(X)
l(X)
Слайд 16
Вклад поддерева Tij в стоимость C0,n
где
Cij - стоимость
поддерева Tij.
wij - вес поддерева Tij.
16.02.2016
Динамическое программирование
Слайд 18
Преобразование
+
wij не зависит от структуры поддерева Tij
16.02.2016
Динамическое
программирование
Слайд 19
Cii = 0
разности индексов k – 1 − i и j – k в слагаемых Ci,k−1
и Ck,j меньше, чем разность индексов j – i в Cij.
L
= j – i , L=0..n16.02.2016
Динамическое программирование
Слайд 20
Таблица
(аналогия с задачей о перемножении цепочки матриц)
16.02.2016
Динамическое
программирование
Слайд 21 for (i =0; i
первая строка
for (L=1; 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];
}
}
16.02.2016
Динамическое программирование
n 2/2 элементов памяти и n 3/3 выполнений тела внутреннего цикла
Вычисление таблицы
Слайд 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
Динамическое программирование
Слайд 24
Модификация Д.Кнута
ri,j −1 ≤ rij ≤ ri +1,j
16.02.2016
Динамическое программирование
Вместо k = (i +1) .. j
⇒ k = num[i ][j −1] .. num[i +1][j ]
Слайд 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
Динамическое программирование
