Оптимальные бинарные деревья поиска - Программирование, компьютеры и кибернетика доклад

Структура оптимальных бинарных деревьев поиска. Рекурсивное решение; вычисление математического ожидания стоимости поиска; выбор ключа, который приводит к его минимальному значению. Вычисленные с помощью процедуры Optimal_BST для распределения ключей.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


Министерство образования и науки Украины
Министерство образования и науки АРК
Крымский инженерно-педагогический университет
ОПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА
1. Оптимальные бинарные деревья поиска
2. Структура оптимального бинарного дерева поиска
4. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска.
Оптимальные бинарные деревья поиска
Предположим, что разрабатывается программа, предназначенная для перевода текстов с русского языка на украинский. Для каждого русского слова необходимо найти украинский эквивалент. Один из возможных путей поиска -- построение бинарного дерева поиска с n русскими словами, выступающими в роли ключей, и украинскими эквивалентами, играющими роль сопутствующих данных. Поскольку поиск с помощью этого дерева будет производиться для каждого отдельного слова из текста, полное затраченное на него время должно быть как можно меньше. С помощью красно-черного дерева или любого другого сбалансированного бинарного дерева поиска можно добиться того, что время каждого отдельного поиска будет равным O(lgn). Однако слова встречаются с разной частотой, и может получиться так, что какое-нибудь часто употребляемое слово (например, предлог или союз) находится далеко от корня, а такое редкое слово, как "контрвстреча", -- возле корня. Такой способ организации привел бы к замедлению перевода, поскольку количество узлов, просмотренных в процессе поиска ключа в бинарном дереве, равно увеличенной на единицу глубине узла, содержащего данный ключ. Нужно сделать так, чтобы слова, которые встречаются в тексте часто, были размещены поближе к корню. Кроме того, в исходном тексте могут встречаться слова, для которых перевод отсутствует. Таких слов вообще не должно быть в бинарном дереве поиска. Как организовать бинарное дерево поиска, чтобы свести к минимуму количество посещенных в процессе поиска узлов, если известно, с какой частотой встречаются слова?
Необходимая нам конструкция известна как оптимальное бинарное дерево поиска (optimal binary search tree). Приведем формальное описание задачи. Имеется заданная последовательность К = (k 1 , k 2 ,..., k n ), состоящая из n различных ключей, которые расположены в отсортированном порядке (так что k 1 < k 2 <... < k n ). Из этих ключей нужно составить бинарное дерево поиска. Для каждого ключа к{ задана вероятность pi поиска этого ключа. Кроме того, может выполняться поиск значений, отсутствующих в последовательности К, поэтому следует предусмотреть n + 1 фиктивных ключей (d 0 , d 1 ,..., d n ), представляющих эти значения. В частности, do представляет все значения, меньшие k 1 , a d n -- все значения, превышающие кп. Фиктивный ключ d i (i = 1,2,..., n -- 1) представляет все значения, которые находятся между k i и k i +1 . Для каждого фиктивного ключа d i задана соответствующая ей вероятность q i . Например бинарное дерево поиска для множества, состоящего из n = 5 ключей.
Каждый ключ k i представлен внутренним узлом, а каждый фиктивный ключ d i является листом. Поиск может быть либо успешным (найден какой-то ключ k i ), либо неудачным (возвращается какой-то фиктивный ключ d i ), поэтому справедливо соотношение
Вероятности, соответствующие внутренним узлам p i и листьям q i , приведены таблице.
Поскольку вероятность поиска каждого обычного и фиктивного ключа считается известной, можно определить математическое ожидание стоимости поиска по заданному бинарному дереву поиска T. Предположим, что фактическая cтоимость поиска определяется количеством проверенных узлов, т.е. увеличенной на единицу глубиной узла на дереве T, в котором находится искомый ключ. Тогда математическое ожидание стоимости поиска в дереве T равно
где величина depth T () обозначает глубину узла в дереве T. В таблице показано математическое ожидание стоимости поиска для вышеуказанного бинарного дерева.
Построим для данного набора вероятностей бинарное дерево поиска, математическое ожидание стоимости поиска для которого будет минимальным. Такое дерево называется оптимальным бинарным деревом поиска. Построим оптимальное бинарное дерево поиска для вероятностей, заданных в таблице.
Математическое ожидание поиска в этом дереве равно 2.80. Этот пример демонстрирует, что оптимальное бинарное дерево поиска -- это не обязательно дерево минимальной высоты. Кроме того, в оптимальном дереве ключ, которому соответствует максимальная вероятность, не всегда находится в корне. В данном случае вероятность имеет самую большую величину для ключа k 5 , хотя в корне оптимального бинарного дерева расположен ключ k 2 . (Минимальная величина математического ожидания для всевозможных бинарных деревьев поиска, в корне которых находится ключ k 5 , равна 2.85) Последовательный перебор всех возможных деревьев в данном случае оказывается неэффективным.
Чтобы сконструировать бинарное дерево поиска, можно обозначить ключами k 1 , k 2 , … , k n узлы бинарного дерева с n узлами, а затем добавить листья для фиктивных ключей. В задаче 12-4 было показано, что количество бинарных деревьев с n узлами равно, так что количество бинарных деревьев, которые надо проверять при полном переборе, растет экспоненциально с ростом n. Эта задача будет решаться методом динамического программирования.
2. Структура оптимального бинарного дерева поиска
Чтобы охарактеризовать оптимальную подструктуру оптимального бинарного дерева поиска, исследуем его поддеревья. Рассмотрим произвольное поддерево бинарного дерева поиска. Оно должно содержать ключи, которые составляют непрерывный интервал k i ,...,k j Для некоторых 1 < i < j < n. Кроме того, такое поддерево должно также содержать в качестве листьев фиктивные ключи d i-1 , … ,d j .
Теперь можно сформулировать оптимальную подструктуру: если в состав оптимального бинарного дерева поиска T входит поддерево T', содержащее ключи k i ,...,k j , то это поддерево тоже должно быть оптимальным для вспомогательной подзадачи с ключами k i ,...,k j и фиктивными ключами d i-1 , … ,d j . Для доказательства этого утверждения применяется обычный метод "вырезания и вставки". Если бы существовало поддерево Т", математическое ожидание поиска в котором ниже, чем математическое ожидание поиска в поддереве Т', то из дерева Т можно было бы вырезать поддерево Т' и подставить вместо него поддерево Т". В результате получилось бы дерево, математическое ожидание времени поиска, в котором оказалось бы меньше, что противоречит оптимальности дерева Т.
Покажем с помощью описанной выше оптимальной подструктуры, что оптимальное решение задачи можно воссоздать из оптимальных решений вспомогательных задач. Если имеется поддерево, содержащее ключи k i ,...,k j , то один из этих ключей, скажем, k r (i<=r<=j) будет корнем этого оптимального поддерева. Поддерево, которое находится слева от корня k r , будет содержать ключи k i ,..., k r -1 (и фиктивные ключи d i -1 ,…,d r-1 ), а правое поддерево - ключи k r +1 ,…,k j (и фиктивные ключи d r ,...,d j ). Как только будут проверены все ключи k r (где I <= r <= j), которые являются кандидатами на роль корня, и найдем оптимальные бинарные деревья поиска, содержащие элементы k i ,…,k r -1 , и k r+1 ,…,k j , мы гарантированно построим оптимальное бинарное дерево поиска. Стоит сделать одно замечание по поводу "пустых" поддеревьев. Предположим, что в поддереве с ключами k i ,..., k j в качестве корня выбран ключ k i .
Согласно приведенным выше рассуждениям, поддерево, которое находится слева от корня k i , содержит ключи k i ,…,k i -1 . Интерпретировать эту последовательность необходимо как такую, в которой не содержится ни одного ключа. Однако следует иметь в виду, что поддеревья содержат помимо реальных и фиктивные ключи. Примем соглашение, согласно которому поддерево, состоящее из ключей k i ,…k i -1 , не содержит обычных ключей, но содержит один фиктивный ключ d i -1 . Аналогично, если в качестве корня выбран ключ k i , то правое поддерево не содержит обычных ключей, но содержит один фиктивный ключ d j .
Теперь все готово для рекурсивного определения оптимального решения. В качестве вспомогательной задачи выберем задачу поиска оптимального бинарного дерева поиска, содержащего ключи k i ,..., k j , где i >= 1, j <= n и j >= i - 1 (если j = n -- 1, то фактических ключей не существует, имеется только фиктивный ключ d i -1 ). Определим величину е[i,j] как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами к{,..., kj. В конечном итоге нужно вычислить величину е[1,n].
Если j = i -- 1, то все просто. В этом случае имеется всего один фиктивный ключ d i -1 , и математическое ожидание стоимости поиска равно е[i,i - 1] = q i -1 .
Если j >= i, то среди ключей k i ,…, k j нужно выбрать корень k r , а потом из ключей k i ,…, k r -1 составить левое оптимальное бинарное дерево поиска, а из ключей k r +1 ,…, k j -- правое оптимальное бинарное дерево поиска. Глубина каждого узла в поддереве возрастает на единицу. Согласно уравнению
математическое ожидание стоимости поиска в этом поддереве возрастает на величину суммы по всем вероятностям поддерева. Обозначим эту сумму вероятностей, вычисленную для поддерева с ключами k i ,…, k j так:
Таким образом, если k r -- корень оптимального поддерева, содержащего ключи
к i ,..., k j , то выполняется соотношение
выражение для величины е [i,j] можно переписать так:
Это рекурсивное соотношение предполагает, что нам известно, какой узел k r используется в качестве корня. На эту роль выбирается ключ, который приводит к минимальному значению математического ожидания стоимости поиска.
С учетом этого получаем окончательную рекурсивную формулу:
Величины е[r, j] -- это математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через root [i,j] (где 1 <= i <= j <= n) индекс r узла k r , который является корнем оптимального бинарного дерева поиска, содержащего ключи k i ,…, k j .
4. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска
Для решения данной задачи ее необходимо разбить на несколько подзадач. Во вспомогательных задачах индексы элементов изменяются последовательно. Прямая рекурсивная реализация уравнения может оказаться неэффективной.
Вместо этого будем сохранять значения e[i,j] в таблице е [1..n+1,0..n]. Первый индекс должен пробегать не n, а n+1 значений. Это объясняется тем, что для получения поддерева, в который входит только фиктивный ключ d n , понадобится вычислить и сохранить значение е[n+1,n]. Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ d 0 , нужно вычислить и сохранить значение е [1,0]. Необходимо использовать только те элементы e[i,j], для которых j >= i-1. Кроме того, необходимо использовать таблицу root[i,j], в которую будут заноситься корни поддеревьев, содержащих ключи k i ,..., k j . В этой таблице задействованы только те записи, для которых 1 <= i <= j <= n.
Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении e[i,j] вычислять значения w(i,j) "с нуля", для чего потребуется (j - i) операций сложения, будем сохранять эти значения в таблице w [l..n+1,0..n]. В базовом случае вычисляются величины
w [i, i-1] = q i -1 для 1 <= i <= n + 1.
Таким образом, каждое из (n 2 ) значений матрицы w [i, j] можно вычислить за время (1).
Ниже приведен псевдокод, который принимает в качестве входных данных вероятности p i ,... ,p n и q 0 ,…,q n и размер n и возвращает таблицы е и root.
Работа представленной выше процедуры такова. Цикл for в строках 1-3 инициализирует значения е[i, i-1] и w[i, i-1]. Затем в цикле for в строках 4-13 с помощью рекуррентных соотношений вычисляются элементы матриц е[i,j] и w[i,j] для всех индексов 1 <= i <= j <= n.
В первой итерации, когда l = 1, в этом цикле вычисляются элементы е [i, i] и w [i, i] для i = 1,2,..., n.
Во второй итерации, когда l = 2, вычисляются элементы е[i, i+1] и w[i,i+1] для i= 1,2,...,n-1 и т.д.
Во внутреннем цикле for (строки 9-13) каждый индекс r апробируется на роль индекса корневого элемента k r оптимального бинарного дерева поиска с ключами к i ,... ,k j . В этом цикле элементу root [i,j] присваивается то значение индекса r, которое подходит лучше всего.
Ниже показаны таблицы е[i, j], w[i,j] и root[i,j], вычисленные с помощью процедуры Optimal_BST для распределения ключей. Таблицы повернуты так, чтобы диагонали располагались горизонтально. В процедуре Optimal_BST строки вычисляются снизу вверх, а в каждой строке заполнение элементов производится слева направо.
Время выполнения процедуры Optimal_BST равно (n 3 ). Легко увидеть, что время работы составляет О(n 2 ), поскольку циклы for этой процедуры трижды вложены друг в друга, и индекс каждого цикла принимает не более n значений. Далее, ндексы циклов в процедуре Optimal_BST изменяются во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура Optimal_BST выполняется в течение времени (n 3 ).
1. Кормен Т.Х. Алгоритмы: построение и анализ / Т.Х. Кормен, Ч.И. Лейзерсон. Р.Л. Ривест, К. Штайн. - [2-е изд.]: пер. с англ. - М.: Изд. дом «Вильямс», 2005. - 1296 с.
2. Интернет-Университет Информационных Технологий «intuit.ru»
Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска. презентация [330,6 K], добавлен 19.10.2014
Основные критерии и требования к средствам поиска по ресурсу. Технологии создания инструментов поиска. Способы поиска по ресурсу. Принцип действия поиска по ключевым словам и при помощи поисковых систем. Разработка ресурса "Поиск по ресурсу" в виде блога. курсовая работа [983,7 K], добавлен 01.02.2015
Средства поиска информации в сети Интернет. Основные требования и методика поиска информации. Структура и характеристика поисковых сервисов. Глобальные поисковые машины WWW (World Wide Web). Планирование поиска и сбора информации в сети Интернет. реферат [32,2 K], добавлен 02.11.2010
Выбор и анализ языка программирования для проектирования системы автоматизированного поиска по таблицам. Ввод в теории поиска и принятия решений. Роль формальных методов при решении практических проблем выбора. Средства ввода и корректировки таблиц. отчет по практике [53,0 K], добавлен 12.05.2015
Особенности проведения поиска по реквизитам документа, контексту, специализированным классификаторам (тематический), интеллектуальный. Средства и инструменты поиска в компьютерных справочно-правовых системах "гарант", "консультантплюс", "кодекс". реферат [25,9 K], добавлен 19.03.2016
Обзор алгоритмов распознания объектов на двумерных изображениях. Выбор языка программирования. Обнаружение устойчивых признаков изображения. Исследование алгоритмов поиска объектов на плоскости. Модификация алгоритма поиска максимума дискретной функции. дипломная работа [1,0 M], добавлен 16.06.2013
Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь". курсовая работа [684,8 K], добавлен 05.04.2015
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Оптимальные бинарные деревья поиска доклад. Программирование, компьютеры и кибернетика.
Доклад: Секретарь. Скачать бесплатно и без регистрации
Курсовая Работа Совершенствование Кредитной Политики Коммерческого Банка
Реферат: Соотношение веры и знания. Эразм Роттердамский. Скачать бесплатно и без регистрации
Кино В Казахстане Эссе
Курсовая работа по теме Створення програми-органайзера
Реферат На Тему Классификация Документов
Реферат: История легкой атлетики 2
Реферат: Untitled Essay Research Paper Words 1393
Курсовая Работа На Тему Финансовое Управление
Реферат: Конфликт цивилизации и культуры. Скачать бесплатно и без регистрации
Шпаргалка: Consecutio tempOrum правило последовательности времен латинский
Основы Оценки Коррекции Телосложения Реферат
Реферат по теме Электрические трехфазные цепи
Написать Сочинение Про Природу
Реферат: Системы управления материальными потоками в производственной логистике. Скачать бесплатно и без регистрации
Реферат: Философский экзистенциализм: его представители, идеи. Скачать бесплатно и без регистрации
Контрольная работа по теме Ручная дуговая сварка покрытыми электродами
Как Связаны Великодушие И Сострадание Итоговое Сочинение
Реферат по теме Христианизация Руси
Напишите Сочинение Эссе Значение Психологии Для Медсестры
Технология изготовления кристаллов полупроводниковых интегральных микросхем - Коммуникации, связь, цифровые приборы и радиоэлектроника курсовая работа
История русского языка - Иностранные языки и языкознание презентация
История вычислительной техники - Программирование, компьютеры и кибернетика дипломная работа