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

Август 12, 2022

Главная
Информатика
Деревья оптимального поиска (ДОП)

Содержание

2. Типичный пример - сканер компилятора, который определяет, относится ли каждое слово программы (идентификатор) к классу ключевых
5. 10 30 60 10 30 60 10 30 60 10 30 60 10 30 60
7. Задача построения ДОП может ставиться в двух вариантах: Известны вершины и их веса (дерево не меняется
17. (0,9) (5,9) (0,4) (1,4) (1,3) (2,3) (0,0) (1,1) (2,2) (3,3) (4,4) (9,9) (8,8) (7,7) (6,6) (5,5)
20. Алгоритм построения ДОП
21. Алгоритм построения ДОП При h>1: h = j–i – размер поддерева DO ( h = 2,
24. Приближенные алгоритмы построения ДОП Известны быстрые алгоритмы, строящие почти оптимальные деревья поиска. Назовем эти алгоритмы А1
25. 25 20 5 10 10 10 5 5 5 5
31. К У Р А П О В А Е Л Е Н А В И К
33. Скачать презентацию

Слайд 2

Типичный пример - сканер компилятора, который определяет, относится ли каждое слово

программы (идентификатор) к классу ключевых слов.
Статистические измерения на сотнях компилируемых программ могут дать информацию об относительных частотах появления в тексте программы конкретных ключевых слов.

Слайд 3

Слайд 4

Слайд 5

10
30
60
10
30
60
10
30
60
10
30
60
10
30
60

Слайд 6

Слайд 7

Задача построения ДОП
может ставиться в двух вариантах:
Известны вершины и их

веса (дерево не меняется в процессе поиска).
Вес вершины определяется в процессе работы (после каждого поиска вершины её вес увеличивается на единицу).
В этом случае нужно перестраивать структуру дерева.

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17

(0,9)
(5,9)
(0,4)
(1,4)
(1,3)
(2,3)
(0,0)
(1,1)
(2,2)
(3,3)
(4,4)
(9,9)
(8,8)
(7,7)
(6,6)
(5,5)
(5,8)
(5,6)
(7,8)

Слайд 18

Слайд 19

Слайд 20

Алгоритм построения ДОП

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