Алгоритмы - построение и анализ (1021735), страница 85
Текст из файла (страница 85)
Имеется заданная последовательность К = (/сы йз,..., 1с„), состоящая из и различных ключей, которые расположены в отсортированном порядке (так что lсз < Йз < « )с„). Из этих ключей нужно составить бинарное дерево поиска. Для каждого ключа 1с, задана вероятность р; поиска этого ключа. Кроме того, может выполняться поиск значений, отсутствующих в последовательности К, поэтому следует предусмотреть и+ 1 фиктивных ключей (Но, Ны..., Н„), представляющих эти значения. В частности, 4> представляет все значения, меньшие йы а е'„— все значения, превышающие 1с„. Фиктивный ключ 4 (г = 1, 2,..., и- 1) представляет все значения, которые находятся между Ц и Ц+н Для каждого фиктивного ключа 4 задана соответствующая ей вероятность дь На рис.
15.7 показаны два бинарных дерева поиска для множества, состоящего из п = 5 ключей. Каждый ключ к, представлен внутренним узлом, а каждый фиктивный ключ 4 является листом. Поиск может быть либо успешным (найден какой-то ключ Ц), либо неудачным (возвращается какой-то фиктивный ключ 4), поэтому справедливо соотношение и п (15.15) Вероятности, соответствующие внутренним узлам р; и листьям дн приведены в табл. 15.1.
Поскольку вероятность поиска каждого обычного и фиктивного ключа считается известной, можно определить математическое ожидание стоимости поиска Глава 15. Динамическое программирование 427 ,М. ,Г М ~ ф« ф 'А«« ~.','« 'я ) м,~ а) б« Рис. 15.7. Два бинарных дерева поиска для множества из 5 злемевтов Таблица 15.1. Вероятности поиска ключей в узлах бинарного дерева 1 2 3 4 5 0 0,05 0,10 0,20 0,05 0,05 О, 10 0,15 0,10 0,10 0,05 0,05 по заданному бинарному дереву поиска Т. Предположим, что фактическая стои- мость поиска определяется количеством проверенных узлов, т.е. увеличенной на единицу глубиной узла на дереве Т, в котором находится искомый ключ.
Тогда математическое ожидание стоимости поиска в дереве Т равно Е 1Стоимость поиска в Т~) = ~ (г1ерМТ (к;) + 1) р«+ «=1 + ,'« . (~ерй«т (А) + 1) % «=О п =1+~~, '(ер11тй) р*+ «ьц +~' ~1ергЛт(А) % «=О (15.16) где величина Нерглт () обозначает глубину узла в дереве Т. Последнее равенство следует из уравнения (15.15). В табл. 15.2 вычисляется математическое ожидание стоимости поиска для бинарного дерева, изображенного на рис.
15.7а. Наша цель — построить для данного набора вероятностей бинарное дерево поиска, математическое ожидание стоимости поиска для которого будет Часть 1Ч. Усовершенствованные методы разработки и анализа 428 Таблица 15.2. Вычисление математического ожидания стоимости поиска Глубина Вероятность Вклад Узел 2,80 Всего минимальным. Такое дерево называется оптимальным бинарным деревом поиска. На рис.
15.76 показано оптимальное бинарное дерево поиска для вероятностей, заданных в табл. 15,1. Математическое ожидание поиска в этом дереве равно 2.75. Этот пример демонстрирует, что оптимальное бинарное дерево поиска — это не обязательно дерево минимальной высоты. Кроме того, в оптимальном дереве ключ, которому соответствует максимальная вероятность, не всегда находится в корне. В данном случае вероятность имеет самую большую величину для ключа й5, хотя в корне оптимального бинарного дерева расположен ключ йг. (Минимальная величина математического ожидания для всевозможных бинарных деревьев поиска, в корне которых находится ключ 145, равна 2.85.) Как и в задаче о перемножении цепочки матриц, последовательный перебор всех возможных деревьев в данном случае оказывается неэффективным.
Чтобы сконструировать бинарное дерево поиска, можно обозначить ключами йы йг,..., 1с„узлы бинарного дерева с г4 узлами„а затем добавить листья для фиктивных ключей. В задаче 12-4 было показано, что количество бинарных деревьев с п узлами равно й (4"/пзбг), так что количество бинарных деревьев, которые надо проверять при полном переборе, растет экспоненциально с ростом и. Не удивительно, что эта задача будет решаться методом динамического программирования. й1 йг Йз К4 К5 4) Из пг пз ~14 о5 0,15 0,10 0,05 0,10 0,20 0,05 0,10 0,05 0,05 0,05 0,10 0,30 0,10 0,15 0,20 0,60 0,15 0,30 0,20 0,20 0,20 0,40 Глава 15.
Динамическое программирование 429 Этап 1: структура оптимального бинарного дерева поиска Чтобы охарактеризовать оптимальную подструктуру оптимального бинарного дерева поиска, исследуем его поддеревья. Рассмотрим произвольное поддерево бинарного дерева поиска.
Оно должно содержать ключи, которые составляют непрерывный интервал Ц,...,/с для некоторых 1 < ю' < 1 < п. Кроме того, такое поддерево должно также содержать в качестве листьев фиктивные ключи г/ -~ ~ г//. Теперь можно сформулировать оптимальную подструктуру: если в состав оптимального бинарного дерева поиска Т входит поддерево Т', содержащее ключи /г;,..., /сс/, то это поддерево тоже должно быть оптимальным для вспомогательной подзадачи с ключами й,,..., й и фиктивными ключами г/; м...,г/ . Для доказательства этого утверждения применяется обычный метод "вырезания и вставки". Если бы существовало поддерево Т", математическое ожидание поиска в котором ниже, чем математическое ожидание поиска в поддереве Т', то из дерева Т можно было бы вырезать поддерево Т' и подставить вместо него поддерево Т". В результате получилось бы дерево, математическое ожидание времени поиска в котором оказалось бы меньше, что противоречит оптимальности дерева Т.
Покажем с помощью описанной выше оптимальной подструктуры, что оптимальное решение задачи можно воссоздать из оптимальных решений вспомогательных задач. Если имеется подлерево, содержащее ключи /т,..., й,, то один из этих ключей, скажем, й, (з < г < 1) будет корнем этого оптимального поддерева. Поддерево, которое находится слева от корня й„, будет содержать ключи /г„...,й„~ (и фиктивные ключи г/; ы...Н, ~), а правое поддерево— ключи й,+ы...,/с/ (и фиктивные ключи г/„...,г/ ).
Как только будут проверены все ключи Й„(где г < г < 1), которые являются кандидатами на роль корня, и найдем оптимальные бинарные деревья поиска, содержащие элементы Ц,..., й„~ и /г„+ы..., к/, мы гарантированно построим оптимальное бинарное дерево поиска. Стоит сделать одно замечание по поводу "пустых" поддеревьев. Предположим, что в поддереве с ключами Ц,...,/с в качестве корня выбран ключ /с,. Согласно приведенным выше рассуждениям, поддерево, которое находится слева от корня /со содержит ключи Ц,..., Ц и Естественно интерпретировать эту последовательность как такую, в которой не содержится ни одного ключа. Однако следует иметь в виду, что поддеревья содержат помимо реальных и фиктивные ключи.
Примем соглашение, согласно которому поддерево, состоящее из ключей /с;,...,/г; ы не содержит обычных ключей, но содержит один фиктивный ключ г/; н Аналогично, если в качестве корня выбран ключ /с/, то правое поддерево не содержит обычных ключей, но содержит один фиктивный ключ Н . Часть )У. Усовершенствованные методы разработки н анализа 430 Этап 2: рекурсивное решение ю(г, т') = ~) р!+ ~~) дь (15.
17) [=с-1 Таким образом, если к„— корень оптимального поддерева, содержащею ключи Й,,..., ЙЗ, то выполняется соотношение е [г, Я = рт + (е [г, т — Ц + ю (г, т — 1) ) + (е [т + 1, Я + и (т + 1, у) ) . Заметив, что и (г, 7) = ю (г, т — 1) + р„+ ю(т + 1, у), выражение для величины е [г, 7] можно переписать так: е [г, 7'] = е [г, т — Ц + е [т + 1, Я + ю (г, у) . (15.18) Рекурсивное соотношение (15.18) предполагает, что нам известно, какой узел /с„используется в качестве корня.
На эту роль выбирается ключ, который приводит к минимальному значению математического ожидания стоимости поиска. С учетом этого получаем окончательную рекурсивную формулу: е[с,7'] = 91-! при у' =1 — 1, ш!и (е [с, т — Ц + е [т + 1, у] + и (г, 7)) при 1 < Я (15.19) с<тьэ Теперь все готово для рекурсивного определения оптимального решения. В качестве вспомогательной задачи выберем задачу поиска оптимального бинарного дерева поиска„содержащего ключи Ц,...,/сз, где 1 > 1, у < и и у > с' — 1 (если у = 1 — 1, то фактических ключей не существует, имеется только фиктивный ключ с(с 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
