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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Деревья оптимального поиска (ДОП), слайд №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. - количество операций сравнения, необходимых для поиска данной вершины.
Описание слайда:
, пропорциональный частоте поиска этой вершины. , пропорциональный частоте поиска этой вершины. Пример. Если из каждых 100 операций поиска 15 операций приходятся на вершину Сумма весов всех вершин дает вес дерева W: W= Каждая вершина , корень дерева – на уровне 1. - количество операций сравнения, необходимых для поиска данной вершины.

Слайд 4


Определение. В дереве с n вершинами средневзвешенная высота равна Определение. В дереве с n вершинами средневзвешенная высота равна = Определение. Дерево, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска ДОП.
Описание слайда:
Определение. В дереве с n вершинами средневзвешенная высота равна Определение. В дереве с n вершинами средневзвешенная высота равна = Определение. Дерево, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска ДОП.

Слайд 5


Пример: Рассмотрим множество из трех ключей Пример: Рассмотрим множество из трех ключей = 60, = 30, = 10; W=100. Эти три ключа можно расположить в дереве поиска пятью различными способами:
Описание слайда:
Пример: Рассмотрим множество из трех ключей Пример: Рассмотрим множество из трех ключей = 60, = 30, = 10; W=100. Эти три ключа можно расположить в дереве поиска пятью различными способами:

Слайд 6


= 1,7 = 1,7 = 2,5 =2,2 Очевидно, для минимизации средней длины пути поиска нужно стремиться вершины с наибольшим весом располагать ближе к корню дерева.
Описание слайда:
= 1,7 = 1,7 = 2,5 =2,2 Очевидно, для минимизации средней длины пути поиска нужно стремиться вершины с наибольшим весом располагать ближе к корню дерева.

Слайд 7


Задача построения ДОП Задача построения ДОП может ставиться в двух вариантах: Известны вершины и их веса (дерево не меняется в процессе поиска). Вес вершины определяется в процессе работы (после каждого поиска вершины её вес увеличивается на единицу). В этом случае нужно перестраивать структуру дерева.
Описание слайда:
Задача построения ДОП Задача построения ДОП может ставиться в двух вариантах: Известны вершины и их веса (дерево не меняется в процессе поиска). Вес вершины определяется в процессе работы (после каждого поиска вершины её вес увеличивается на единицу). В этом случае нужно перестраивать структуру дерева.

Слайд 8


Точный алгоритм построения ДОП Точный алгоритм построения ДОП 3 вершины = 5 конфигураций дерева 4 вершины = 14 конфигураций дерева 5 вершин = 62 конфигурации дерева Количество возможных конфигураций дерева из n вершин с ростом n растет экспоненциально, т.е. как . Таким образом, при больших n задача построения ДОП кажется безнадежной.
Описание слайда:
Точный алгоритм построения ДОП Точный алгоритм построения ДОП 3 вершины = 5 конфигураций дерева 4 вершины = 14 конфигураций дерева 5 вершин = 62 конфигурации дерева Количество возможных конфигураций дерева из n вершин с ростом n растет экспоненциально, т.е. как . Таким образом, при больших n задача построения ДОП кажется безнадежной.

Слайд 9


Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать: Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать: все их поддеревья также оптимальны. На этом свойстве основан алгоритм, который находит все большие и большие оптимальные поддеревья, начиная с отдельных вершин. Т.к. вес дерева постоянный, то вместо средневзвешенной высоты будем рассматривать взвешенную высоту дерева: Р =
Описание слайда:
Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать: Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать: все их поддеревья также оптимальны. На этом свойстве основан алгоритм, который находит все большие и большие оптимальные поддеревья, начиная с отдельных вершин. Т.к. вес дерева постоянный, то вместо средневзвешенной высоты будем рассматривать взвешенную высоту дерева: Р =

Слайд 10


Для ДОП справедливо соотношение: Для ДОП справедливо соотношение: = W+ , где левого и правого поддеревьев. Обозначим - оптимальное поддерево, состоящее из вершин , … - вес поддерева Очевидно, Р = - взвешенная высота всего дерева из n вершин W = - вес всего дерева - пустое поддерево  = 0, = 0.
Описание слайда:
Для ДОП справедливо соотношение: Для ДОП справедливо соотношение: = W+ , где левого и правого поддеревьев. Обозначим - оптимальное поддерево, состоящее из вершин , … - вес поддерева Очевидно, Р = - взвешенная высота всего дерева из n вершин W = - вес всего дерева - пустое поддерево  = 0, = 0.

Слайд 11


Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев: Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев: = + 0 ≤ i < j ≤ n = + min (+ ) 0 ≤ i < j ≤ n i < k ≤ j При нахождении min будем запоминать k, при котором достигается min, обозначать его k* и записывать в матрицу Это значение является индексом (номером) корня поддерева в упорядоченном массиве вершин.
Описание слайда:
Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев: Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев: = + 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 - пустые поддеревья - поддеревья из одной вершины - поддеревья из двух вершин - дерево из трех вершин
Описание слайда:
Матрица корней поддеревьев полностью определяет структуру дерева. Матрица корней поддеревьев полностью определяет структуру дерева. Пример: =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
Описание слайда:
=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
Описание слайда:
+ 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=) и добавляем эту вершину в левое поддерево, берем и добавляем вершину в правое поддерево и т.д.
Описание слайда:
Идея алгоритма построения ДОП по матрице Идея алгоритма построения ДОП по матрице Исходные вершины должны быть упорядочены по ключам, в матрице берем это номер корня всего дерева в упорядоченном массиве вершин. Добавляем эту вершину в дерево через обычное добавление в СДП. Затем в матрице берем значение (k=) и добавляем эту вершину в левое поддерево, берем и добавляем вершину в правое поддерево и т.д.

Слайд 16


Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП. Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП. Номер вершины совпадает с ключом.
Описание слайда:
Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП. Пример: Возьмем произвольную матрицу для 9 вершин и построим по ней ДОП. Номер вершины совпадает с ключом.

Слайд 17


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

Слайд 18


Трудоемкость метода: Трудоемкость метода: Существует значений , формула (2) требует выбора одного из 0 ≤ i < j ≤ n значений, трудоемкость сводится к операций, т.е. трудоемкость кубическая. В матрице существует закономерность ≤ ≤ Это позволяет сократить поиск до этого диапазона, что дает возможность уменьшить трудоемкость до квадратичной.
Описание слайда:
Трудоемкость метода: Трудоемкость метода: Существует значений , формула (2) требует выбора одного из 0 ≤ i < j ≤ n значений, трудоемкость сводится к операций, т.е. трудоемкость кубическая. В матрице существует закономерность ≤ ≤ Это позволяет сократить поиск до этого диапазона, что дает возможность уменьшить трудоемкость до квадратичной.

Слайд 19


Деревья оптимального поиска (ДОП), слайд №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) …
Описание слайда:
Алгоритм построения ДОП Вычисление 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
Описание слайда:
Алгоритм построения ДОП При 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 Трудоемкость точного алгоритма построения ДОП: по времени О() по занимаемой памяти О() При больших объемах деревьев такие алгоритмы становятся неэффективными.
Описание слайда:
Создание дерева: 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


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

Слайд 24


Приближенные алгоритмы построения ДОП Известны быстрые алгоритмы, строящие почти оптимальные деревья поиска. Назовем эти алгоритмы А1 и А2. Алгоритм А1: В качестве корня берем вершину с наибольшим весом, будем поступать так же для каждого поддерева.
Описание слайда:
Приближенные алгоритмы построения ДОП Известны быстрые алгоритмы, строящие почти оптимальные деревья поиска. Назовем эти алгоритмы А1 и А2. Алгоритм А1: В качестве корня берем вершину с наибольшим весом, будем поступать так же для каждого поддерева.

Слайд 25


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

Слайд 26


Алгоритм A1 на псевдокоде Алгоритм A1 на псевдокоде <сортировка по убыванию весов> DO (i=1, n) Добавить (Root, ) OD
Описание слайда:
Алгоритм A1 на псевдокоде Алгоритм A1 на псевдокоде <сортировка по убыванию весов> DO (i=1, n) Добавить (Root, ) OD

Слайд 27


Алгоритм А2: Алгоритм А2: Алгоритм отличается тем, что вершины должны быть упорядочены по возрастанию ключей. Находим «центр тяжести», т.е. путем последовательного суммирования весов определим вершину , для которой справедливы неравенства: и ≥ В качестве «центра тяжести» берется вершина, для которой сумма весов левой и правой части массива как можно меньше отличаются друг от друга. Иногда для большей точности также рассматриваются две ближайшие к выбранной вершины: и .
Описание слайда:
Алгоритм А2: Алгоритм А2: Алгоритм отличается тем, что вершины должны быть упорядочены по возрастанию ключей. Находим «центр тяжести», т.е. путем последовательного суммирования весов определим вершину , для которой справедливы неравенства: и ≥ В качестве «центра тяжести» берется вершина, для которой сумма весов левой и правой части массива как можно меньше отличаются друг от друга. Иногда для большей точности также рассматриваются две ближайшие к выбранной вершины: и .

Слайд 28


Деревья оптимального поиска (ДОП), слайд №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
Описание слайда:
Алгоритм А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 хороший: дерево асимптотически приближается к оптимальному.
Описание слайда:
Трудоемкость приближенных алгоритмов: Трудоемкость приближенных алгоритмов: по времени О(n* по занимаемой памяти О(n) Алгоритм А1 «плохой» : при n-->∞ дерево равносильно случайному (с точки зрения средневзвешенной высоты); Алгоритм А2 хороший: дерево асимптотически приближается к оптимальному.

Слайд 31


К У Р А П О В А Е Л Е Н А В И К Т О Р О В Н А
Описание слайда:
К У Р А П О В А Е Л Е Н А В И К Т О Р О В Н А

Слайд 32


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию