Деревья оптимального поиска (ДОП) - презентация, доклад, проект скачать

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

Деревья оптимального поиска (ДОП), слайд №1

Деревья оптимального поиска (ДОП), слайд №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

Деревья оптимального поиска (ДОП), слайд №27

Деревья оптимального поиска (ДОП), слайд №28

Деревья оптимального поиска (ДОП), слайд №29

Деревья оптимального поиска (ДОП), слайд №30

Деревья оптимального поиска (ДОП), слайд №31

Деревья оптимального поиска (ДОП), слайд №32

Содержание ▲

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

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

Слайд 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

Слайд 14

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

+ min (+ ) = + min (+ ) = 0

Слайд 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

Слайд 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 хороший: дерево асимптотически приближается к оптимальному.