Презентация Деревья оптимального поиска (ДОП) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья оптимального поиска (ДОП) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 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 слайд
![Деревья оптимального поиска](/documents_6/d31e26533a90ea817f619c61072f1da6/img0.jpg)
Содержание слайда: Деревья оптимального поиска (ДОП)
До сих пор предполагалось, что все вершины дерева ищутся одинаково часто.
Однако встречаются ситуации, когда известны вероятности обращения к отдельным ключам дерева.
Обычно для таких ситуаций характерно постоянство ключей (структура дерева остается неизменной).
№2 слайд
![Типичный пример - сканер](/documents_6/d31e26533a90ea817f619c61072f1da6/img1.jpg)
Содержание слайда: Типичный пример - сканер компилятора, который определяет, относится ли каждое слово программы (идентификатор) к классу ключевых слов.
Типичный пример - сканер компилятора, который определяет, относится ли каждое слово программы (идентификатор) к классу ключевых слов.
Статистические измерения на сотнях компилируемых программ могут дать информацию об относительных частотах появления в тексте программы конкретных ключевых слов.
№3 слайд
![, пропорциональный частоте](/documents_6/d31e26533a90ea817f619c61072f1da6/img2.jpg)
Содержание слайда: , пропорциональный частоте поиска этой вершины.
, пропорциональный частоте поиска этой вершины.
Пример. Если из каждых 100 операций поиска 15 операций приходятся на вершину
Сумма весов всех вершин дает вес дерева W:
W=
Каждая вершина , корень дерева – на уровне 1.
- количество операций сравнения, необходимых для поиска данной вершины.
№7 слайд
![Задача построения ДОП Задача](/documents_6/d31e26533a90ea817f619c61072f1da6/img6.jpg)
Содержание слайда: Задача построения ДОП
Задача построения ДОП
может ставиться в двух вариантах:
Известны вершины и их веса (дерево не меняется в процессе поиска).
Вес вершины определяется в процессе работы (после каждого поиска вершины её вес увеличивается на единицу).
В этом случае нужно перестраивать структуру дерева.
№8 слайд
![Точный алгоритм построения](/documents_6/d31e26533a90ea817f619c61072f1da6/img7.jpg)
Содержание слайда: Точный алгоритм построения ДОП
Точный алгоритм построения ДОП
3 вершины = 5 конфигураций дерева
4 вершины = 14 конфигураций дерева
5 вершин = 62 конфигурации дерева
Количество возможных конфигураций дерева из n вершин с ростом n растет экспоненциально, т.е. как .
Таким образом, при больших n задача построения ДОП кажется безнадежной.
№9 слайд
![Однако оптимальные деревья](/documents_6/d31e26533a90ea817f619c61072f1da6/img8.jpg)
Содержание слайда: Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать:
Однако оптимальные деревья обладают важным свойством, которое помогает их обнаруживать:
все их поддеревья также оптимальны.
На этом свойстве основан алгоритм, который находит все большие и большие оптимальные поддеревья, начиная с отдельных вершин.
Т.к. вес дерева постоянный, то вместо средневзвешенной высоты будем рассматривать взвешенную высоту дерева:
Р =
№10 слайд
![Для ДОП справедливо](/documents_6/d31e26533a90ea817f619c61072f1da6/img9.jpg)
Содержание слайда: Для ДОП справедливо соотношение:
Для ДОП справедливо соотношение:
= W+ ,
где левого и правого поддеревьев.
Обозначим
- оптимальное поддерево,
состоящее из вершин , …
- вес поддерева
Очевидно,
Р = - взвешенная высота всего дерева из n вершин
W = - вес всего дерева
- пустое поддерево = 0, = 0.
№11 слайд
![Величины и вычисляются по](/documents_6/d31e26533a90ea817f619c61072f1da6/img10.jpg)
Содержание слайда: Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев:
Величины и вычисляются по рекуррентным формулам для всех возможных поддеревьев:
= + 0 ≤ i < j ≤ n
= + min (+ ) 0 ≤ i < j ≤ n
i < k ≤ j
При нахождении min будем запоминать k, при котором достигается min, обозначать его k* и записывать в матрицу
Это значение является индексом (номером) корня поддерева в упорядоченном массиве вершин.
№12 слайд
![Матрица корней поддеревьев](/documents_6/d31e26533a90ea817f619c61072f1da6/img11.jpg)
Содержание слайда: Матрица корней поддеревьев полностью определяет структуру дерева.
Матрица корней поддеревьев полностью определяет структуру дерева.
Пример:
=1, =2, =3;
=60, =30, =10; W =100
- пустые поддеревья
- поддеревья из одной вершины
- поддеревья из двух вершин
- дерево из трех вершин
№15 слайд
![Идея алгоритма построения ДОП](/documents_6/d31e26533a90ea817f619c61072f1da6/img14.jpg)
Содержание слайда: Идея алгоритма построения ДОП по матрице
Идея алгоритма построения ДОП по матрице
Исходные вершины должны быть упорядочены по ключам, в матрице берем это номер корня всего дерева в упорядоченном массиве вершин.
Добавляем эту вершину в дерево через обычное добавление в СДП.
Затем в матрице берем значение (k=) и добавляем эту вершину в левое поддерево, берем и добавляем вершину в правое поддерево и т.д.
№18 слайд
![Трудоемкость метода](/documents_6/d31e26533a90ea817f619c61072f1da6/img17.jpg)
Содержание слайда: Трудоемкость метода:
Трудоемкость метода:
Существует значений , формула (2) требует выбора одного из 0 ≤ i < j ≤ n значений, трудоемкость сводится к операций, т.е. трудоемкость кубическая.
В матрице существует закономерность
≤ ≤
Это позволяет сократить поиск до этого диапазона, что дает возможность уменьшить трудоемкость до квадратичной.
№21 слайд
![Алгоритм построения ДОП При h](/documents_6/d31e26533a90ea817f619c61072f1da6/img20.jpg)
Содержание слайда: Алгоритм построения ДОП
При 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](/documents_6/d31e26533a90ea817f619c61072f1da6/img21.jpg)
Содержание слайда: Создание дерева: 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
Трудоемкость точного алгоритма построения ДОП:
по времени О()
по занимаемой памяти О()
При больших объемах деревьев такие алгоритмы становятся неэффективными.
№27 слайд
![Алгоритм А Алгоритм А](/documents_6/d31e26533a90ea817f619c61072f1da6/img26.jpg)
Содержание слайда: Алгоритм А2:
Алгоритм А2:
Алгоритм отличается тем, что вершины должны быть упорядочены по возрастанию ключей.
Находим «центр тяжести», т.е. путем последовательного суммирования весов определим вершину , для которой справедливы неравенства:
и ≥
В качестве «центра тяжести» берется вершина, для которой сумма весов левой и правой части массива как можно меньше отличаются друг от друга.
Иногда для большей точности также рассматриваются две ближайшие к выбранной вершины: и .
№30 слайд
![Трудоемкость приближенных](/documents_6/d31e26533a90ea817f619c61072f1da6/img29.jpg)
Содержание слайда: Трудоемкость приближенных алгоритмов:
Трудоемкость приближенных алгоритмов:
по времени О(n*
по занимаемой памяти О(n)
Алгоритм А1 «плохой» : при n-->∞ дерево равносильно случайному (с точки зрения средневзвешенной высоты);
Алгоритм А2 хороший: дерево асимптотически приближается к оптимальному.
Скачать все slide презентации Деревья оптимального поиска (ДОП) одним архивом:
Похожие презентации
-
Сбалансированные деревья поиска
-
Поиск оптимального пути в 3D
-
Дополнительные возможности: регулярные выражения. Метрика бета-версия, отличия и логика работы
-
Разработка и реализация алгоритма создания и балансировки двоичного дерева поиска со взвешенными узлами
-
B и Красно-Черные деревья
-
Разведка и допросы
-
Деревья. Лекция 11, 12
-
Реализация бинарных деревьев на Си
-
Графы: деревья
-
Дополнительные возможности при работе с пользовательскими функциями