Оптимальные деревья поиска. Оптимальные бинарные деревья поиска
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования и науки Украины
Министерство образования и науки АРК
Крымский инженерно-педагогический университет
По дисциплине
Семинар по специальным дисциплинам
ОПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА
Симферополь 2011
План:
1. Оптимальные бинарные деревья поиска
2. Структура оптимального бинарного дерева поиска
3. Рекурсивное решение
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 .
3. Рекурсивное решение
Теперь все готово для рекурсивного определения оптимального решения. В качестве вспомогательной задачи выберем задачу поиска оптимального бинарного дерева поиска, содержащего ключи k i ,..., k j , где i >= 1, j <= n и j >= i - 1 (если j = n -- 1, то фактических ключей не существует, имеется только фиктивный ключ d i -1). Определим величину е как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами к{,..., kj. В конечном итоге нужно вычислить величину е.
Если j = i -- 1, то все просто. В этом случае имеется всего один фиктивный ключ d 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 , то выполняется соотношение
Заметив, что
выражение для величины е можно переписать так:
Это рекурсивное соотношение предполагает, что нам известно, какой узел k r используется в качестве корня. На эту роль выбирается ключ, который приводит к минимальному значению математического ожидания стоимости поиска.
С учетом этого получаем окончательную рекурсивную формулу:
Величины е -- это математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через root (где 1 <= i <= j <= n) индекс r узла k r , который является корнем оптимального бинарного дерева поиска, содержащего ключи k i ,…, k j .
бинарный дерево рекурсивный ключ
4. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска
Для решения данной задачи ее необходимо разбить на несколько подзадач. Во вспомогательных задачах индексы элементов изменяются последовательно. Прямая рекурсивная реализация уравнения может оказаться неэффективной.
Вместо этого будем сохранять значения e в таблице е . Первый индекс должен пробегать не n, а n+1 значений. Это объясняется тем, что для получения поддерева, в который входит только фиктивный ключ d n , понадобится вычислить и сохранить значение е. Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ d 0 , нужно вычислить и сохранить значение е . Необходимо использовать только те элементы e, для которых j >= i-1. Кроме того, необходимо использовать таблицу root, в которую будут заноситься корни поддеревьев, содержащих ключи k i ,..., k j . В этой таблице задействованы только те записи, для которых 1 <= i <= j <= n.
Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении e вычислять значения w(i,j) "с нуля", для чего потребуется (j - i) операций сложения, будем сохранять эти значения в таблице w . В базовом случае вычисляются величины
w = q i -1 для 1 <= i <= n + 1.
Для j >= i вычисляются величины
Таким образом, каждое из (n 2) значений матрицы w можно вычислить за время (1).
Ниже приведен псевдокод, который принимает в качестве входных данных вероятности p i ,... ,p n и q 0 ,…,q n и размер n и возвращает таблицы е и root.
Работа представленной выше процедуры такова. Цикл for в строках 1-3 инициализирует значения е и w. Затем в цикле for в строках 4-13 с помощью рекуррентных соотношений вычисляются элементы матриц е и w для всех индексов 1 <= i <= j <= n.
В первой итерации, когда l = 1, в этом цикле вычисляются элементы е и w для i = 1,2,..., n.
Во второй итерации, когда l = 2, вычисляются элементы е и w для i= 1,2,...,n-1 и т.д.
Во внутреннем цикле for (строки 9-13) каждый индекс r апробируется на роль индекса корневого элемента k r оптимального бинарного дерева поиска с ключами к i ,... ,k j . В этом цикле элементу root присваивается то значение индекса r, которое подходит лучше всего.
Ниже показаны таблицы е, w и root, вычисленные с помощью процедуры Optimal_BST для распределения ключей. Таблицы повернуты так, чтобы диагонали располагались горизонтально. В процедуре Optimal_BST строки вычисляются снизу вверх, а в каждой строке заполнение элементов производится слева направо.
Время выполнения процедуры Optimal_BST равно (n 3). Легко увидеть, что время работы составляет О(n 2), поскольку циклы for этой процедуры трижды вложены друг в друга, и индекс каждого цикла принимает не более n значений. Далее, ндексы циклов в процедуре Optimal_BST изменяются во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура Optimal_BST выполняется в течение времени (n 3).
Список использованной литературы:
1. Кормен Т.Х. Алгоритмы: построение и анализ / Т.Х. Кормен, Ч.И. Лейзерсон. Р.Л. Ривест, К. Штайн. - : пер. с англ. - М.: Изд. дом «Вильямс», 2005. - 1296 с.
2. Интернет-Университет Информационных Технологий «intuit.ru»
Размещено на Allbest.ru
Подобные документы
Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.
презентация , добавлен 19.10.2014
Основные критерии и требования к средствам поиска по ресурсу. Технологии создания инструментов поиска. Способы поиска по ресурсу. Принцип действия поиска по ключевым словам и при помощи поисковых систем. Разработка ресурса "Поиск по ресурсу" в виде блога.
курсовая работа , добавлен 01.02.2015
Средства поиска информации в сети Интернет. Основные требования и методика поиска информации. Структура и характеристика поисковых сервисов. Глобальные поисковые машины WWW (World Wide Web). Планирование поиска и сбора информации в сети Интернет.
реферат , добавлен 02.11.2010
Выбор и анализ языка программирования для проектирования системы автоматизированного поиска по таблицам. Ввод в теории поиска и принятия решений. Роль формальных методов при решении практических проблем выбора. Средства ввода и корректировки таблиц.
отчет по практике , добавлен 12.05.2015
Особенности проведения поиска по реквизитам документа, контексту, специализированным классификаторам (тематический), интеллектуальный. Средства и инструменты поиска в компьютерных справочно-правовых системах "гарант", "консультантплюс", "кодекс".
реферат , добавлен 19.03.2016
Обзор алгоритмов распознания объектов на двумерных изображениях. Выбор языка программирования. Обнаружение устойчивых признаков изображения. Исследование алгоритмов поиска объектов на плоскости. Модификация алгоритма поиска максимума дискретной функции.
дипломная работа , добавлен 16.06.2013
Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь".
курсовая работа , добавлен 05.04.2015
Алгоритм добавления нового элемента в дерево и поиска по нему. Порядок разработки руководства пользователя. Принцип работы с экранным меню. Методика и этапы добавления нового элемента. Формирование и содержание инструкции системного программиста.
курсовая работа , добавлен 06.06.2014
Простота поиска информации в системе "Google.ru", его технологии и функции. История термина и его применение. Выбор условий поиска, автоматическое исключение общих слов. Калькулятор и конвертирование валют. Похожие страницы и проверка правописания.
реферат , добавлен 21.02.2011
Обзор существующих систем атоматизированного поиска. Мир электронных денег. Разработка структуры системы автоматизированного поиска отделений и терминалов банков. Обоснование выбора технологии разработки, программной среды и языка программирования.
Пример построения двоичного Б-дерева приведен на следующем рисунке.
Рисунок 56 Построение двоичного Б-дерева
При построении двоичного Б-дерева реже приходится переставлять вершины, поэтому АВЛ-деревья предпочтительней в тех случаях, когда поиск ключей происходит значительно чаще, чем добавление новых элементов. Кроме того, существует зависимость от особенностей реализации, поэтому вопрос о применение того или иного тапа деревьев следует решать индивидуально для каждого конкретного случая.
Варианты заданий
Написать процедуру поиска элемента с заданным ключом в Б-дереве порядка m .
Определить трудоемкость поиска в Б-дереве порядка m .
Написать процедуру определения высоты Б-дерева порядка m .
Запрограммировать процедуру добавления нового элемента в Б-дерева порядка m .
Графически изобразить Б-дерево порядка 2.
Запрограммировать процедуру добавления новой вершины в двоичное Б-дерево. Определить количество необходимых операций для добавления вершины.
Написать процедуру определения высоты двоичного Б-дерева.
Экспериментально сравнить двоичное Б-дерево и ИСДП по высоте как двоичные деревья.
Экспериментально сравнить высоты двоичного Б-дерева и случайного дерева поиска как двоичные деревья.
Экспериментально сравнить двоичное Б-дерево и АВЛ-дерево по высоте как двоичные деревья.
Графически изобразить двоичное Б-дерево.
Деревья оптимального поиска (ДОП)
Определение дерева оптимального поиска
Припишем каждой вершине дерева V i вес w i , пропорциональный частоте поиска этой вершины (например, если из каждых 100 операций поиска 15 операций приходятся на вершину V 1 , то w 1 =15). Сумма весов всех вершин дает вес дерева W . Каждая вершина V i расположена на высоте h i , корень расположен на высоте 1. Высота вершины равна количеству операций сравнения, необходимых для поиска этой вершины. Определим средневзвешенную высоту дерева с n вершинами следующим образом: h ср =(w 1 h 1 + w 2 h 2 +…+ w n h n )/ W . Дерево поиска, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска (ДОП).
Пример . Рассмотрим множество из трех ключей V 1 =1, V 2 =2, V 3 =3 со следующими весами: w 1 =60, w 2 =30, w 3 =10, W =100. Эти три ключа можно расставить в дереве поиска пятью различными способами.
1.
Рисунок 57 Различные деревья поиска с вершинами V 1 =1, V 2 =2, V 3 =3
Легко видеть, что минимальной средневзвешенной высотой обладает дерево 1 на рисунке 57, которое представляет собой список или вырожденное дерево. Дерево 3 не является деревом оптимального поиска, хотя представляет собой идеально сбалансированное дерево. Очевидно, для минимизации средней длины пути поиска нужно стремится располагать наиболее часто используемые вершины ближе к корню дерева.
Задача построения ДОП может ставится в двух вариантах:
Известны вершины и их веса.
Вес вершины определяется в процессе работы. Например, после каждого поиска вершины ее вес увеличивается на 1. В этом случае необходимо перестраивать структуру дерева при изменении весов.
Точный алгоритм построения ДОП
Свойство 1. Для дерева поиска с весом W справедливо соотношение P = P L + W + P R , где P L , P R – взвешенные высоты левого и правого поддеревьев корня.
Доказательство . Пусть вершина V i с весом w i является корневой для некоторого i =1, … n . Поскольку левое и правое поддеревья являются деревьями поиска, то в левое поддерево входят вершины V 1 , V 2 , …, V i -1 , а в правое – V i +1 , …, V n . Взвешенные высоты этих поддеревьев вычисляются следующим образом.
P L = (h 1 -1)w 1 +(h 2 -1)w 2 +…+(h i -1 -1)w i -1
P R = (h i +1 -1)w i +1 + …+ (h n -1)w n
Рассмотрим выражение взвешенной высоты для всего дерева, замечая, что h i =1
P=h 1 w 1 +h 2 w 2 +…+h n w n = (h 1 -1)w 1 + w 1 +(h 2 -1)w 2 + w 2 …+(h i -1 -1)w i -1 + w i -1 +
+ w i + (h i+1 -1)w i+1 + w i+1 …+ (h n -1)w n + w n = P L +W+P R
Свойство 2. Все поддеревья дерева оптимального поиска также являются деревьями оптимального поиска для соответствующих подмножеств вершин.
Доказательство . Предположим, что одно из поддеревьев, например, правое, не является ДОП, т.е. существует дерево поиска с тем же множеством вершин, но с меньшей взвешенной высотой. Тогда по свойству 1 взвешенная высота всего дерева также не является минимальной. Данное противоречие доказывает свойство 2.
На основе приведенных свойств можно разработать точный алгоритм построения ДОП. Обозначим T ij – оптимальное поддерево, состоящее из вершин V i +1 , …, V j . Введем матрицу АR=||Ar ij ||, 0≤ i , j ≤ n элементы которой содержат номер корневой вершины поддерева T ij , 0≤ i j ≤ n . Взвешенную высоту поддерева T ij обозначим Ap ij , а вес поддерева T ij обозначим Aw ij , 0≤ i j ≤ n . Очевидно, что P = Ap o , n , W = Aw o , n , Т ii – пустые деревья (без вершин), Aw ii =0, Ap ii =0, i =1, … n .
Используя свойство 2, величины Aw ij , Ap ij можно вычислить рекуррентно по следующим соотношениям (для всех возможных поддеревьев):
Aw ij =Aw i,j-1 +Aw j , 0≤ i (1)
Ap ij =Aw ij + min (Ap i,k-1 +Ap k,j ), 0≤ i (2)
Во время вычислений будем запоминать индекс k * , при котором достигается минимум во втором соотношении. Значение k * является индексом корневой вершины поддерева T ij во всем множестве вершин. Занесем в матрицу А R k * –индекс корня T ij , т.е. Ar ij = k * , 0≤ i j ≤ n .
Идея построения дерева состоит в следующем. В матрице А R берем значение Ar o , n (номер корневой вершины всего дерева в упорядоченном массиве вершин), пусть оно равно k . Добавляем вершину V k в дерево, используя обычный алгоритм добавления вершин в дерево поиска. Затем из матрицы А R берем значения Ar o , k -1 и добавляем вершину с этим номером в левое поддерево. Далее берем A r k , n и добавляем вершину с этим номером в правое поддерево и т.д.
Пример. Построить дерево оптимального поиска с вершинами V 1 =1, V 2 =2, V 3 =3 и весами w 1 =60, w 2 =30, w 3 =10. Сначала вычислим Aw ij , Ap ij , Ar ij , 0≤ i j ≤ n . Легко видеть, что
T 00 , T 11 , T 22 , T 33 – пустые поддеревья
T 01 , T 12 , T 23 – поддеревья из одной вершины (1), (2), (3)
T 02 , T 13 – поддеревья из двух вершин (1,2) и (2,3)
T 03 – поддерево из трех вершин (1,2,3)
По формулам (1) и (2) вычислим элементы матрицы весов AW и элементы матрицы взвешенных высот AP , значения матрицы А R запишем в верхних уголках ячеек матрицы А P .
Аw ij | 0 | 1 | 2 | 3 |
|||||||||||
0 | 0 | 60 | 90 | 100 |
|||||||||||
1 | 0 | 30 | 40 |
||||||||||||
2 | 0 | 10 |
|||||||||||||
3 | 0 |
||||||||||||||
Аp ij | 0 | 1 | 2 | 3 |
0 | 0 | 60 1 | 120 1 | 150 1 |
1 | 0 | 30 2 | 50 2 |
|
2 | 0 | 10 3 |
||
3 | 0 |
А p 01 =А w 01 +min(А p 00 +А p 11 ) =60 (k *= 1)
0
А
p
12
=А
w
12
+
min(А
p
11
+А
p
22
) =30 (k
*=
2)
1
А
p
23
=А
w
23
+min(А
p
22
+А
p
33
) =10 (k
*=
3)
2
А
p
02
=А
w
02
+min(А
p
00
+А
p
12
, А
p
01
+А
p
22
)=90+30=120 (k
*=
1).
0А p 13 =А w 13 + min(А p 11 +А p 23 , А p 12 +А p 33 )=40+10=50 (k *= 2).
А p 03 =А w 03 +min(А p 00 +А p 13 , А p 01 +А p 23 , А p 02 +А p 33 )=100+50=150 (k *= 3).
0
Корневой вершиной будет вершина V
1
, поскольку А
r
0,3
=1.
Левое поддерево пустое, корень правого поддерева – вершина V
2
(r
1,3
=2)
и т.д. Полученное дерево показано на рисунке.
Рисунок 58 ДОП для w 1 =60, w 2 =30, w 3 =10
Поскольку существует около n 2 /2 значений Аp ij , а вычисление (2) требует выбора одного из 0i - j n значений, то весь процесс будет занимать О(n 3) операций при n →∞. Д. Кнут отмечает, что можно избавиться от одного множителя n и тем самым сохранить практическую ценность алгоритма. Поиск Аr ij можно ограничить, то есть сократить число вычислений до j - i (если найден корень оптимального поддерева T ij , то ни добавление справа новой вершины, ни отбрасывание левой вершины не могут сдвинуть вправо этот оптимальный корень). Это свойство выражается соотношением Аr i , j -1 ≤ А r ij ≤ А r i +1, j , что и ограничивает поиск Аr ij диапазоном Аr i , j -1 …А r i +1, j . Это уменьшает трудоемкость алгоритма до О(n 2) операций при n →∞.
Алгоритм на псевдокоде
Вычисление матрицы весов AW (формула 1).
DO (i = 0,...,n)
DO (j = i+1,...,n)
Aw ij:= Aw i, j-1 + w j
Алгоритм на псевдокоде
Вычисление матриц AP и AR (формула 2).
DO (i = 0,...,n - 1)
Ap ij+1:= Aw ij+1
DO (h = 2,...,n)
DO (i = 0,...,n - h)
min: = Ap i,m-1 + Ap m, j
DO (k = m+1,...,AR i+1, j)
x: = Ap i,k-1 + Ap k, j
Ap i, j:= min + Aw i, j
Алгоритм на псевдокоде
Создание дерева (L, R – границы массива вершин V,
Root – указатель на корень дерева)
IF (L
k:= Ar L,R
Добавить (Root, V k)
Создание дерева (L, k-1)
Создание дерева (k, R)
Для построения дерева необходимо вызвать процедуру создания дерева с параметрами L=0, R=n, Root=NIL.
Приближенные алгоритмы построения ДОП
Первый алгоритм (А1) предлагает в качестве корня использовать вершину с наибольшим весом. Затем среди оставшихся вершин снова выбирается вершина с наибольшим весом и помещается в левое или правое поддерево в зависимости от ее значения , и т.д.
Алгоритм на псевдокоде
Алгоритм А1(Root – указатель на корень дерева)
Обозначим
V.use – логическая переменная в структуре вершины дерева, которая показывает, что данная вершина была использована при построении дерева;
V.w – вес вершины.
Root: = NIL
DO (i = 1,...,n)
V[i].use = ЛОЖЬ
DO (i = 1,...,n)
max:=0, Index:=0
DO (j = 1,...,n)
IF (V[j].w > max и V[j]. use=ЛОЖЬ)
V .use:=ИСТИНА
Добавление в СДП (Root, V)
Рассмотрим пример построения дерева почти оптимального поиска для символов строки К У Р А П О В А Е Л Е Н А В И К Т О Р О В Н А. Всего символов в строке 23, т.е. W=23. Различные символы определяют различные вершины дерева. Частоты вхождения символов (веса) приведены в таблице.
Таблица 3 Частоты вхождения символов в строку
К | У | Р | А | П | О | В | Е | Л | Н | И | Т |
2 | 1 | 2 | 4 | 1 | 3 | 3 | 2 | 1 | 2 | 1 | 1 |
Посчитаем средневзвешенную высоту построенного дерева
P=4 . 1+3 . 2+3 . 3+2 . 3+2 . 4+1 . 4+1 . 4+2 . 5+ +2 . 5+1 . 5+1 . 6+1 . 6=78
h ср =P/W=78/23=3,39
Рисунок 59 Дерево, построенное приближенным алгоритмом А1
Второй алгоритм (А2) использует предварительно упорядоченный набор вершин. В качестве корня выбирается такая вершина, что разность весов левого и правого поддеревьев была минимальна. Для этого путем последовательного суммирования весов определим вершину V k , для которой справедливы неравенства:
и
.
Тогда в качестве "центра тяжести" может быть выбрана вершина V
k
,
V
k
-1
или V
k
+1
, т. е. вершина, для которой разность весов левого и правого поддерева минимальна. Далее действия повторяются для каждого поддерева
Алгоритм на псевдокоде
L, R – левая и правая границы рабочей части массива)
IF (L
DO (i=L, L+1, …,R) wes=wes+ V[i].w OD
DO (i=L, L+1,…,R-1)
IF (summa =wes/2) OD
summa=summa+ V[i].w
Добавление в СДП (Root, V[i])
A2(Root, L, i-1)
аргумент поиска меньше, чем значение элемента K 1 ; q n – вероятность того, что аргумент поиска больше, чем K n . Тогда цена дерева поиска C будет определяться следующим образом:где – уровень узла j , а – уровень листа K .
Дерево поиска называется оптимальным , если его цена минимальна. То есть оптимальное бинарное дерево поиска – это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных.
Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска, которое будет далеко от оптимального. Еще один подход состоит в выборе корня k таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением p k .
Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка O(n 2) . Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.
Сбалансированные по высоте деревья
В худшем случае, когда дерево вырождено в линейный список , хранение данных в упорядоченном бинарном дереве никакого выигрыша в сложности операций по сравнению с массивом или линейным списком не дает. В лучшем случае, когда дерево сбалансировано, для всех операций получается логарифмическая сложность , что гораздо лучше. Идеально сбалансированным называется дерево , у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1.
Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении или удалении элементов может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. В 1962 году два советских математика : Г.М. Адельсон-Вельский и Е.М. Ландис – ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления и/или удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным. Дерево считается сбалансированным по АВЛ (сокращения от фамилий Г.М. Адельсон-Вельский и Е.М. Ландис), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное по АВЛ дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано по АВЛ.
При операциях добавления и удаления может произойти нарушение сбалансированности дерева . В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.
Рассмотрим такие преобразования. Пусть вершина a имеет правый потомок b . Обозначим через P левое поддерево вершины a , через Q и R – левое и правое поддеревья вершины b соответственно. Упорядоченность дерева требует, чтобы Pмалым правым вращением ( рис. 40.3 малое левое вращение .
Рис. 40.3.
Пусть b – правый потомок вершины a , c – левый потомок вершины b , P – левое поддерево вершины a , Q и R – соответственно левое и правое поддеревья вершины c , S – правое поддерево b . Тогда Pбольшим правым вращением ( рис. 40.4). Аналогично определяется симметричное ему большое левое вращение .
Рис. 40.4.
Схематично алгоритм добавления нового элемента в сбалансированное по АВЛ дерево будет состоять из следующих трех основных шагов.
Шаг 1. Поиск по дереву.
Шаг 2. Вставка элемента в место , где закончился поиск , если элемент отсутствует.
Шаг 3. Восстановление сбалансированности.
Первый шаг необходим для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным. Третий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.
#include "stdafx.h"
#include
Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:
Шаг 1. Поиск по дереву.
Шаг 2. Удаление элемента из дерева.
Шаг 3. Восстановление сбалансированности дерева ( обратный проход).
Первый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена. Третий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости. Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, т.е. порядка log n вершин. Таким образом, алгоритмы поиска, добавления и удаления элементов в сбалансированном по АВЛ дереве имеют сложность, пропорциональную O(log n) .
Деревья цифрового (поразрядного) поиска
Методы цифрового поиска достаточно громоздки и плохо иллюстрируются. Рассмотрим бинарное дерево цифрового поиска. Как и в деревьях, рассмотренных выше, в каждой вершине такого дерева хранится полный ключ , но переход по левой или правой ветви происходит не путем сравнения ключа-эталона со значением ключа, хранящегося в вершине, а на основе значения очередного бита аргумента. Реализация цифрового поиска происходит поразрядно (побитово).
Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 – по правой. Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется следующий бит аргумента и т.д.
В двоичном дереве поиск одних элементов может происходить чаще, чем других, то есть существуют вероятности поиска k -го элемента и для различных элементов эти вероятности неодинаковы. Можно предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищут чаще, будут находиться ближе к корню дерева.
Пусть даны вероятностей , , где –вероятность того, что аргументом поиска является элемент; – вероятность того, что аргумент поиска лежит между вершинами и ; – вероятность того, что аргумент поиска меньше, чем значение элемента ; – вероятность того, что аргумент поиска больше, чем . Тогда цена дерева поиска C будет определяться следующим образом:
,
где – уровень узла j , а – уровень листа K .
Дерево поиска называется оптимальным , если его цена минимальна. То есть оптимальное бинарное дерево поиска – это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных.
Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска, которое будет далеко от оптимального. Еще один подход состоит в выборе корня k таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением .
Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка . Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.
Построение и анализ алгоритмов
Лекция 4Динамическое программирование
Оптимальные деревья поиска
16.02.2016
Динамическое
программирование
1
Пример 3. Оптимальные деревья поиска
См. начало в Лекции 3.См. также раздел 2.8
пособия «Деревья кодирования и поиска»
16.02.2016
Динамическое
программирование
2
Оптимальные деревья поиска
Ранее при рассмотрении БДП, как правило,предполагалось, что для поиска различные ключи
предъявляются с равной вероятностью.
Пусть теперь заранее известно, что некоторые ключи
предъявляются чаще других.
Тогда расположение «частых» ключей ближе к
корню дерева сократит время их поиска и, возможно,
среднее время поиска (по разным предъявлениям
ключей).
16.02.2016
Динамическое
программирование
3
Пример дерева поиска из трёх элементов a1 < a2 < a3 .
a3I
a2
III
a3
II
a1
a1
a2
a3
a1
a2
IV
a1
V
Пример дерева
поиска из трёх
элементов
a1 < a2 < a3 .
a1
a3
a2
a2
a3
Рис. 2.9. Все различные расширенные БДП из трёх элементов a1 < a2 < a3
16.02.2016
Динамическое
программирование
4
Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .
Заданы вероятности предъявления элемента x дляпоиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .
Дерево
Варианты значений, и
Стоимость
= 1/3
= 3/6
= 4/7
= 5/8
= 1/3
= 2/6
= 2/7
= 2/8
= 1/3
= 1/6
= 1/7
= 1/8
Значения стоимости при заданных, и
I
3 + 2 +
6/3
14/6
17/7
20/8
II
2 + 3 +
6/3
13/6
15/7
17/8
III
2 + + 2
5/3
10/6
12/7
14/8
IV
+ 3 + 2
6/3
11/6
12/7
13/8
V
+ 2 + 3
6/3
10/6
11/7
12/8
Среднее (по всем предъявлениям x) число сравнений (стоимость) в
случаях успешного поиска как функция переменных, и,
16.02.2016
Динамическое
программирование
5
Постановка задачи
Поиск будет осуществляться среди набора данныхa1, a2, …, an–1, an.
Пусть последовательность упорядочена:
a1 < a2 < … < an–1 < an .
A1, …, An- события, соответствующие вариантам
успешных исходов поиска,
т. е. Ai: (x = ai) для i 1..n,
B0, …, Bn - события, соответствующие вариантам
неудачных исходов поиска,
т. е. Bi: (ai < x < ai+1) для i 0..n.
Здесь для упрощения записи событий B0 и Bn добавлены
фиктивные элементы a0 = и an+1 = + , которые не
должны использоваться в алгоритме.
16.02.2016
Динамическое
программирование
6
Все эти 2n + 1 событий (исходов поиска)
n
(Ai)1
n
(Bi) 0
могут быть упорядочены:
B0 < A1 < B1 < A2 < … < Bn – 1 < An < Bn.
Заданы вероятности (или частоты) этих событий:
pi = P (Ai) для i 1..n, и qi = P (Bi) для i 0..n.
При этом i 1..n pi + i 0..n qi = 1.
События Ai соответствуют внутренним узлам
расширенного дерева поиска, а события Bi – внешним
узлам (листьям) расширенного дерева поиска.
16.02.2016
Динамическое
программирование
7
Постановка задачи (продолжение)
Тогда среднее число (математическое ожидание)сравнений при поиске можно записать в виде
n
n
i 1
i 0
где l (x) – уровень узла x (или длина пути от корня до
узла x) в БДП.
Здесь уровень узла определён так, что l (корень) = 0.
Итак, задача состоит в том, чтобы по заданным весам
pi 1n и qi 0n
построить БДП, минимизирующее значение C0,n .
16.02.2016
Динамическое
программирование
8
Постановка задачи (продолжение)
Такое дерево называют оптимальным БДП.Есть ли сходство этой задачи с задачей построения
оптимального префиксного кода?
В чём сходство, в чём различие?
Ответ.
16.02.2016
Динамическое
программирование
9
10.
Очевидное решение поставленной задачи состоит впереборе всех структурно различных бинарных деревьев
с n узлами и выборе дерева с наименьшей стоимостью
C0,n .
Однако поскольку (см. лекции про БДП) число bn
структурно различных бинарных деревьев с n узлами есть
bn
4n
n 3 / 2
, то этот способ вряд ли будет иметь практическую
ценность.
Оказывается, приемлемое по количеству вычислений
решение данной задачи может быть получено методом
динамического программирования.
16.02.2016
Динамическое
программирование
10
11. Конец повторения прошлой лекции
16.02.2016Динамическое
программирование
11
12. Построение оптимальных деревьев поиска
Дано:1)набор элементов a1 < a2 < … < an–1 < an .
2) набор весов
n
n
pi 1 и qi 0
1) i 1..n pi + i 0..n qi = 1.
Требуется: по заданным весам построить БДП,
минимизирующее значение C0,n.
n
n
i 1
i 0
С0, n pi (l (Ai) 1) qi l (Bi),
16.02.2016
Динамическое
программирование
12
13. Идея
Пусть имеется оптимальное дерево.Согласно принципу оптимальности, лежащему в
основе метода динамического программирования,
левое и правое поддеревья этого дерева в свою
очередь также должны быть оптимальны.
16.02.2016
Динамическое
программирование
13
14. Идея
Tij -поддерево БДП из элементов(при 0 i j n).
ai 1 , ..., a j
Tij БДП{ai 1, ..., a j }
ak
aj
a i 1
Bi
Bj
корнем поддерева может быть любой из элементов, т. е. k i +1..j.
16.02.2016
Динамическое
программирование
14
15. Обозначения
Пустьl = l(rij)- уровень корня rij поддерева Tij в дереве T0,n
L(X) - уровень узла, соответствующего событию X, в
поддереве Tij . (L(rij)=0)
Тогда l(X) = L(X) + l, где X {Bi, Ai+1, …, Bj}.
l(X)
l = l(rij)
rij
L(X)
16.02.2016
Динамическое
программирование
15
16. Вклад поддерева Tij в стоимость C0,n
jk i 1
j
j
pk (l (Ak) 1) qk l (Bi)
k i
j
k i 1
k i 1
j
pk (L(Ak) l 1) qk (L(Bi) l)
k i
j
j
pk (L(Ak) 1) qk L(Bi) (
k i
k i 1
j
pk qk) l Cij wij l ,
k i
где
j
Cij
k i 1
j
pk (L(Ak) 1) qk L(Bi),
k i
j
wij
k i 1
j
pk qk .
k i
Cij - стоимость поддерева Tij.
wij - вес поддерева Tij.
wij wi, j 1 (p j q j)
16.02.2016
Динамическое
программирование
16
17. Идея: структура дерева + принцип оптимальности
akaj
a i 1
Bi
Bj
Рис. 2.10. Структура расширенного поддерева Tij
Сij min {Сi,k 1 Сk , j (wi,k 1 wk , j pk)}
i k j
16.02.2016
Динамическое
программирование
17
18. Преобразование
Сij min {Сi,k 1 Сk , j (wi,k 1 wk , j pk)}i k j
wi,k 1 wk , j pk wij
+
wij не зависит от структуры поддерева Tij
Сij min {Сi,k 1 Сk , j } wij
i k j
16.02.2016
Динамическое
программирование
18
19.
1) Cii = 02) разности индексов k – 1 i и j – k в слагаемых
Ci,k 1 и Ck,j меньше, чем разность индексов j – i в Cij.
3) L = j – i , L=0..n
16.02.2016
Динамическое
программирование
19
20. Таблица (аналогия с задачей о перемножении цепочки матриц)
l=0Т(0, 0)
Т(1, 1)
Т(2, 2)
Т(3, 3)
…
l=1
Т(0, 1)
Т(1, 2)
Т(2, 3)
…
Т(n 2, n 1)
l=2
Т(0, 2)
Т(1, 3)
…
Т(n 3, n 1)
Т(n 2, n)
…
…
…
…
…
l = n –2
Т(0, n 2) Т(1, n 1) Т(2, n)
l = n –1
Т(0, n 1)
l=n
Т(0, n)
Т(1, n)
Т(n 1, n 1) Т(n, n)
Т(n 1, n)
Tij:
wij=
Cij=
Numij=
arg min {Сi ,k 1 Сk , j } Num
i k j
16.02.2016
Динамическое
программирование
20
21.
for (i =0; iтаблицы
w[i][ j] = w[i] + (p[j]+q[j]);
c[i][j] = + ;
for (k =i +1 ; k< j-1; k++) {
s = c[i] + c [k][j];
if (s c[i][j]){
c[i][j] = s;
num[i][j] = k
};
n 2/2 элементов
}
памяти и n 3/3
c[i][j] = c[i][j] + w[i][j]; выполнений тела
внутреннего цикла
}
}
16.02.2016
Динамическое
программирование
21
22.
См. пример в файле «2_08_ОДП.doc»С.67,68-…
16.02.2016
Динамическое
программирование
22
23. Построение БДП по таблице значений num
BinT MakeOptBST (int i, j){
int k; ElemBinT root;
BinT L, R;
k = num; root = a[k];
if (i < k 1) L = MakeOptBST (i, k 1);
else L = NULL;
if (k < j) R = MakeOptBST (k, j);
else R = NULL;
return ConsBT (root, L, R);
} //MakeOptBST
со стартовым вызовом T = MakeOptBST (0, n).
16.02.2016
Динамическое
программирование
23
24. Модификация Д.Кнута ri,j 1 rij ri +1,j
Модификация Д.Кнутаri,j 1 rij ri +1,j
ri, j 1
Bi
Ai+1 Bi+1
rij
…
ri +1, j
Aj 1 Bj 1 Aj
Bj
Рис. 2.14. Соотношение между корнями поддеревьев оптимального БДП
Вместо k = (i +1) .. j
16.02.2016
k = num .. num
Динамическое
программирование
24
25. См. с.72
Так в ранее рассмотренном примерена последнем шаге при вычислении C0,4
вместо рассмотрения четырёх кандидатов на
роль корня дерева (см. с.70)
ak (k = 1, 2, 3, 4)
можно ограничиться лишь двумя (a1 и a2),
поскольку
num k num,
а num = 1 и num = 2.
16.02.2016
Динамическое
программирование
25
26.
КОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
16.02.2016
Динамическое
программирование