Презентация Деревья оптимального поиска (ДОП) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья оптимального поиска (ДОП) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 32 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:32 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.57 MB
- Просмотров:61
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Деревья оптимального поиска (ДОП)
До сих пор предполагалось, что все вершины дерева ищутся одинаково часто.
Однако встречаются ситуации, когда известны вероятности обращения к отдельным ключам дерева.
Обычно для таких ситуаций характерно постоянство ключей (структура дерева остается неизменной).
№2 слайд
Содержание слайда: Типичный пример - сканер компилятора, который определяет, относится ли каждое слово программы (идентификатор) к классу ключевых слов.
Типичный пример - сканер компилятора, который определяет, относится ли каждое слово программы (идентификатор) к классу ключевых слов.
Статистические измерения на сотнях компилируемых программ могут дать информацию об относительных частотах появления в тексте программы конкретных ключевых слов.
№3 слайд
Содержание слайда: , пропорциональный частоте поиска этой вершины.
, пропорциональный частоте поиска этой вершины.
Пример. Если из каждых 100 операций поиска 15 операций приходятся на вершину
Сумма весов всех вершин дает вес дерева W:
W=
Каждая вершина , корень дерева – на уровне 1.
- количество операций сравнения, необходимых для поиска данной вершины.
№4 слайд
Содержание слайда: Определение. В дереве с n вершинами средневзвешенная высота равна
Определение. В дереве с n вершинами средневзвешенная высота равна
=
Определение. Дерево, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска ДОП.
№5 слайд
Содержание слайда: Пример: Рассмотрим множество из трех ключей
Пример: Рассмотрим множество из трех ключей
= 60, = 30, = 10; W=100.
Эти три ключа можно расположить в дереве поиска пятью различными способами:
№6 слайд
Содержание слайда: = 1,7
= 1,7
= 2,5
=2,2
Очевидно, для минимизации средней длины пути поиска нужно стремиться вершины с наибольшим весом располагать ближе к корню дерева.
№7 слайд
Содержание слайда: Задача построения ДОП
Задача построения ДОП
может ставиться в двух вариантах:
Известны вершины и их веса (дерево не меняется в процессе поиска).
Вес вершины определяется в процессе работы (после каждого поиска вершины её вес увеличивается на единицу).
В этом случае нужно перестраивать структуру дерева.
№8 слайд
Содержание слайда: Точный алгоритм построения ДОП
Точный алгоритм построения ДОП
3 вершины = 5 конфигураций дерева
4 вершины = 14 конфигураций дерева
5 вершин = 62 конфигурации дерева
Количество возможных конфигураций дерева из n вершин с ростом n растет экспоненциально, т.е. как .
Таким образом, при больших n задача построения ДОП кажется безнадежной.
№9 слайд
Содержание слайда: Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать:
Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать:
все их поддеревья также оптимальны.
На этом свойстве основан алгоритм, который находит все большие и большие оптимальные поддеревья, начиная с отдельных вершин.
Т.к. вес дерева постоянный, то вместо средневзвешенной высоты будем рассматривать взвешенную высоту дерева:
Р =
№10 слайд
Содержание слайда: Для ДОП справедливо соотношение:
Для ДОП справедливо соотношение:
= W+ ,
где левого и правого поддеревьев.
Обозначим
- оптимальное поддерево,
состоящее из вершин , …
- вес поддерева
Очевидно,
Р = - взвешенная высота всего дерева из n вершин
W = - вес всего дерева
- пустое поддерево = 0, = 0.
№11 слайд
Содержание слайда: Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев:
Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев:
= + 0 ≤ i < j ≤ n
= + min (+ ) 0 ≤ i < j ≤ n
i < k ≤ j
При нахождении min будем запоминать k, при котором достигается min, обозначать его k* и записывать в матрицу
Это значение является индексом (номером) корня поддерева в упорядоченном массиве вершин.
№12 слайд
Содержание слайда: Матрица корней поддеревьев полностью определяет структуру дерева.
Матрица корней поддеревьев полностью определяет структуру дерева.
Пример:
=1, =2, =3;
=60, =30, =10; W =100
- пустые поддеревья
- поддеревья из одной вершины
- поддеревья из двух вершин
- дерево из трех вершин
№13 слайд
Содержание слайда: =1, =2, =3;
=1, =2, =3;
=60, =30, =10; W =100
Вычисление взвешенных высот поддеревьев:
+ min (+ ) = 60 k*=1
0<k≤1
+ min (+ = 30 k*=2
1<k≤2
+ min (+ = 10 k*=3
2<k≤3
№14 слайд
Содержание слайда: + min (+ ) =
+ min (+ ) =
0<k≤2 k=1 k=2
= 90 + min (0+30, 60+0) = 120 k*=1
+ min (+ ) =
1<k≤3 k=2 k=3
= 40 + min (0+10, 30+0) = 50 k*=2
+ min (+ ) =
0<k≤3 k=1 k=2 k=3
= 100 + min (0+50, 60+10, 120+0) = 150 k*=1
№15 слайд
Содержание слайда: Идея алгоритма построения ДОП по матрице
Идея алгоритма построения ДОП по матрице
Исходные вершины должны быть упорядочены по ключам, в матрице берем это номер корня всего дерева в упорядоченном массиве вершин.
Добавляем эту вершину в дерево через обычное добавление в СДП.
Затем в матрице берем значение (k=) и добавляем эту вершину в левое поддерево, берем и добавляем вершину в правое поддерево и т.д.
№16 слайд
Содержание слайда: Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП.
Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП.
Номер вершины совпадает с ключом.
№17 слайд
Содержание слайда:
№18 слайд
Содержание слайда: Трудоемкость метода:
Трудоемкость метода:
Существует значений , формула (2) требует выбора одного из 0 ≤ i < j ≤ n значений, трудоемкость сводится к операций, т.е. трудоемкость кубическая.
В матрице существует закономерность
≤ ≤
Это позволяет сократить поиск до этого диапазона, что дает возможность уменьшить трудоемкость до квадратичной.
№19 слайд
Содержание слайда:
№20 слайд
Содержание слайда: Алгоритм построения ДОП
Вычисление AW - матрицы весов:
DO (i=0, n)
DO (j=i+1, n)
A = A +
OD
OD
Вычисление матриц AP и AR:
Обозначим h = j – i – размер поддерева
При h =1:
DO (i=0, n-1)
j=i+1; = A = j
OD
При h>1:
DO (h=2,3,…,n) …
№21 слайд
Содержание слайда: Алгоритм построения ДОП
При h>1: h = j–i – размер поддерева
DO ( h = 2, 3, …, n )
DO ( i = 0, ..., n – h )
j := i + h
m := AR i, j-1
min : = AP i, m-1 + AP m, j
DO ( k = m+1, ..., AR i+1, j )
x : = AP i, k-1 + AP k, j
IF ( x < min ) m := k , min := x FI
OD
AP i, j := min + AW i, j
AR i, j := m
OD
OD
№22 слайд
Содержание слайда: Создание дерева: Create Tree(0,n)
Создание дерева: Create Tree(0,n)
Create Tree(L,R) // L,R - границы массива вершин V
IF(L<R)
k =
Добавить (Root, )
Create Tree(L,k-1)
Create Tree(k,R)
FI
Трудоемкость точного алгоритма построения ДОП:
по времени О()
по занимаемой памяти О()
При больших объемах деревьев такие алгоритмы становятся неэффективными.
№23 слайд
Содержание слайда:
№24 слайд
Содержание слайда: Приближенные алгоритмы построения ДОП
Известны быстрые алгоритмы, строящие почти оптимальные деревья поиска. Назовем эти алгоритмы А1 и А2.
Алгоритм А1:
В качестве корня берем вершину с наибольшим весом, будем поступать так же для каждого поддерева.
№25 слайд
Содержание слайда:
№26 слайд
Содержание слайда: Алгоритм A1 на псевдокоде
Алгоритм A1 на псевдокоде
<сортировка по убыванию весов>
DO (i=1, n)
Добавить (Root, )
OD
№27 слайд
Содержание слайда: Алгоритм А2:
Алгоритм А2:
Алгоритм отличается тем, что вершины должны быть упорядочены по возрастанию ключей.
Находим «центр тяжести», т.е. путем последовательного суммирования весов определим вершину , для которой справедливы неравенства:
и ≥
В качестве «центра тяжести» берется вершина, для которой сумма весов левой и правой части массива как можно меньше отличаются друг от друга.
Иногда для большей точности также рассматриваются две ближайшие к выбранной вершины: и .
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда: Алгоритм А2 на псевдокоде
Алгоритм А2 на псевдокоде
А2 (L, R)
wes = 0, sum = 0
IF (L ≤ R)
DO ( i = L, L+1, …, R ) wes = wes + OD
DO( i = L, L+1, …, R)
IF (sum < wes/2 и sum +> wes/2 ) OD FI
sum = sum +
OD
Добавить ( root,
A2 ( L, i-1 )
A2 ( i+1, R)
FI
№30 слайд
Содержание слайда: Трудоемкость приближенных алгоритмов:
Трудоемкость приближенных алгоритмов:
по времени О(n*
по занимаемой памяти О(n)
Алгоритм А1 «плохой» : при n-->∞ дерево равносильно случайному (с точки зрения средневзвешенной высоты);
Алгоритм А2 хороший: дерево асимптотически приближается к оптимальному.
№31 слайд
Содержание слайда: К У Р А П О В А Е Л Е Н А В И К Т О Р О В Н А
№32 слайд
Содержание слайда: Relax
Скачать все slide презентации Деревья оптимального поиска (ДОП) одним архивом:
