Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 20
Текст из файла (страница 20)
Так, ожидаемое количество сравнений для бинарного дерева равно 2оо+Зр~+Зо1 стйрт+Заэ+рз+оз. Назовем это значение ценой дерева, а дерево с минямальной ценой — оптимальнмле. При таком определении требование, чтобы сумма всех р и е была равна 1, излишне — мы можем искать дерево с минимальной ценой с любой данной последовательностью весов (ры, ре; Оо, -, че). В разделе 2.3.4.5 мы изучали процедуру Хаффмана (Нпйпап) для построения деревьев с минимальной взвешенной длиной пути, однако этот метод требовжт, чтобы все р были нулевыми, и, кроме того, в построенном этим методом дереве внешние узлы с весами (оо,..., о„) обычно не располагались в правильном порядке с точки зрения симметричного обхода. Следовательно„нам надо поискать другие подходы к решению этой задачи.
Нас спасет то, что все подлеревья оптимального дерева оптимальны. Например, если (15) представляет собой оптимальное дерево для весов (Рв, рг, Рз,' суо, чв, йг, гуз), то его левое поддерево должно быть оптимально для (рв, рг, 'Чо, вув чг)' любое Улуч" шение поддерева должно приводить к улучшению дерева в целом. Данный принцип предлагает вычислительную процедуру, которая систематично ищет все ббльшие и бблылие оптимальные полдеревья. Мы использовали эту же идею в разделе 5А.9 для построения схем оптимального слияния; общий подход, известный как "динамическое программирование", будет рассмотрен в разделе 7.74.
Пусть с(в,у) — цена оптимального полдерева с весами (Рвэв, -,Р~", вув, °,Чу) и пусть во(в,у) = Ревв + +ру + дв+ + ду — сумма этих весов (очевидно, что с(в, у) и и(в,,у) определены для О < в < у < п). Поскольку минимально возможная цена дерева с корнем ® равна во(в, у) + с(в, Ус-1) + с(к, у), получим с(в,в) = О, с(в, у) = во(в,у)+ шуп (с(в, Й-1) +с(й,у)) при в <~. (16) в<в<, Через В(в,у) при в < у обозначим множество всех к, для которых достигается минимум в (16); это множество определяет корни оптимальных поддеревьев.
С помощью уравнений (16) можно вычислить с(в, у) для у — в = 1г 2,..., п; имеется примерно -'пг таких значений, а операция минимизации выполняется примерно для -'пз значений к. Это означает, что мы в состоянии определить оптимальное дерево за 0(ввз) единиц времени с использованием 0(пг) ячеек памнти. При оценке времени работы свойство монотонности позволяет уменьшить степень при п. Пусть т(в, у) означает элелвент множества В(в, Я., нет необходимости в вычислении всего множества В(в', у) — достаточно одного его представителя.
Найдя т(в, у — 1) и т(в'+1, у) и используя результат упр. 27, мы всегда можем полагать, что т(в, у-1) < в (в, у) < т(в+1, у) (17) при неотрицательных весах. Это ограничивает поиск минимума всего лишь т(в'+1, у) — т(в,у — 1) + 1 проверяемыми в (16) значениями ус вместо у — в. Общий объем работы при у — в = д оценивается как (т(в+1„у) — т(в, у — 1) + 1) = т(п — гу+1, п) — т(О, гу — 1) + п — д + 1 < 2п, так что общее время работы уменьшается до 0(пг). Детально эта процедура рассматривается в описании алгоритма К. Алгоритм К (Поиск опшималвнмх бинарнввх деревьев поиска). Даны 2п+1 неотрицательных веса (рв,...,р„; до,...,д„). Алгоритм строит бинарные деревья У(в',у), имеющие минимальную цену (в определенном ранее смысле) для весов (рве-в, ° °, Р~", дв,..., ду).
Вычисляются три массива, а именно с(в,у], О < в < у < п, цена В(в,,у): т(в,,у], О < в < у < п, корень 4(в, у); во(в,Я, О < в < у < п, общий вес в(в, у). * Имеется в виду раздел нз планируемого автором тома 4. — уурвм. веуме. Результаты работы алгоритма определяются массивом г: при 1 = у г(е, у) пуст; в противном случае левое поддерево — 1(1, г[1', Я-1), а правое поддерево — Ф(г[е, Я, у).
К1. [Инициализация.] Для 0 < 1 < и установить с[е, Ц е- О, ш[т,1[ е- д; и ю[(,Я ею[1,у-Ц+ру+В при у =1+1,...,н. Затем для1 < у' < пустановнтьс[у — 1,Я+- в[у-1,Я и г[у-1,Я е- у. (Эти действия определяют все оптимальные деревья из одного узла.) К2. [цикл по ~Ц Выполнить шаг КЗ для д = 2,3,...,и, затем остановить работу алгоритма. КЗ. [Цикл по Д (К атому моменту уже определены оптимальные деревья с менее чем Н узлами. На данном шаге определяются все оптимальные деревья с И узлами). Выполнить шаг К4 для у = о, Н+ 1, ..., и,. К4.
[Поиск с[т',Я, г[(,Я.) Установить 1+- у — 4, затем— с[е,Я е- ю[(,Я+ пни„(ьз 0<ей,рецй[с[1,1с-Ц+ с[й,Я) и присвоить г[1,Я значение й, для которого достигается минимум. [В упр, 22 доказывается, что г[е,,у -Ц < г[1+1, Я.) $ Рис. 1Ь. Оптимальное бинарное дерево поиска для указателя КЧ~1С.
В качестве примера алгоритма К рассмотрим рис. 15, основанный на приложении индексирования «кеу-ноге(-1п-соптех1" (ключевое слово в контексте — К%1С). Заглавия всех статей в первых десяти томах уопгпа1 оГ гпе АСЛХ были рассортированы таким образом, чтобы каждому слову каждого заголовка соответствовала одна строка. Впрочем, некоторые слова наподобие ТНЕ и Е00яТ10Н были признаны неинформативными и не вошли в указатель. Эти специальные слова и частота их появления обозначены внутренними узлами на рис. 15.
Обратите внимание на то, что заглавие наподобие "Оп 1Ье во!пг1оп оу ап ецпат)оп (ог а сегса!п пен ргоЫеш" ("О решении уравнения для некоторой новой задачи") оказывается настолько неинформативным, что вовсе не попадает в указатель! Идея указателя К%1С описана в работе Н. Р, (пйп, Ашег.
Воспшепсасюп 11 (1960), 288-29о, а сам указатель полностью приведен в работе %. %. Уо~к1еп, ХАСМ 10 (1963), 583-646. При подготовке уюзателя К%1С к сортировке нам, возможно, понадобилось бы воспользоватьси бинарным деревом поиска, чтобы проверить, должно ли определенное слово быть внесенным в указатель. Другие слова, попадающие в алфавитном порядке между неиндекснруемымн словами, показаны в виде внешних узлов на рис. 15. Так, в заглавиях статей,ИСК за 1954 — 1963 годы встретилось ровно 277 слов, расположенных по алфавиту между словами РВОВОЕМВ и ЖПЛТ1ОМ.
На рис. 15 показано оптимальное дерево, полученное согласно алгоритму К при и = 35. Вычисленные для у = 1,2,...,35значеиияг(О,Я равны (1,1,2,3,3,3,3,8,8,8, 8,8,8,11,11,...,П,21,21,21,21,21,21); значения г(1,35] для ( = 0,1,...,34 равны (21,21,...,21.25,25,25,25,25,25,26,26,26,30,30,30,30,30,30,30,33,33,33,35,35). Ь) Рис. 16.
Оптимальные бинарные деревьв поиска, основанные иа половине данных, которые представлены на рис. 15: (а) без учета внешних частот; (Ь) без учета внутренних частот. "Промежуточные частоты" 9 оказывают существенное влияние на структуру оптимального дерева; на рис. 16, (а) показано оптимальное дерево, которое было бы 7юлучеио при всех д,, равных нулю. Точно так же важны и внутренние частоты р„на рис. 16,(Ь) представлено оптимальное дерево при рп равных нулю. При полном наборе частот дерево, изображенное на рнс. 16, требует в среднем только 4.16 сравнений; деревья на рис. 16 требуют 4.69 и 4.55 сравнений соответственно. 359 299 ь 199 Ь о 5 Поскольку для алгоритма К необходимы время и пространство, пропорциональные п2, его использование непрактично при больших и, Конечно, при очень больших и мы можем отказаться от использования бинарных деревьев и подумать о других методах поиска, которые будут рассмотрены нами немного позже.
А пока предположим, что надо найти оптимальное (илн почти оптимальное) дерево при больших значениях и. Мы видели, что идея вставки ключей в порядке уменьшения частот приводит к получению в среднем неплохих деревьев; впрочем, они могут оказаться и очень плохими (см. упр. 20), так как веса 91 при таком методе построения не используются. Еше один подход состоит в выборе корня А таким образом, чтобы максимальный вес поддерева и~ах(ш(0, 77 — 1), в(й, и)) был настолько мвл, насколько зто возможно. Такой подход также может оказаться плохим (при выборе в качестве корня узла с малым значением рь). Впрочем, теорема М, приведенная ниже, показывает, что полученное в результате дерево будет не так уж далеко от оптимального. Новее успешная процедура может быть получена путем комбинирования описанных методов, как было предложено В.
А. Волкером (%. А. Жа))сег) н К. К. Готлибом (С. С 6ос)1еЬ) (6гарЬ Тйеогу алд Сошрпгупя (Аеас)еппс Ргевв, 1972), 303 — 323). Попытайтесь уравнять "левые'" и "правые" веса, однако будьте готовы переместить корень на несколько шагов вправо или влево для поиска узла с относительно большим ры На рис. 17 показана "разумность" предложенного метода: если начер- 5Л ь 5,9 о х 4.9 ~$ 4.8 4,7 $ 4.6 ф 4.5 4Л 4.3 йв 4,2 4Л Й 4.9 3 5 7 9 11 13 15 !7 49 21 23 25 27 29 34 33 3 Рис.
17. Поведение цены как функции корня й. тить график с(0, Ус-1) + с(й, и) как функции от Ус для данных КЖХС (см. рнс. 15), то увидим, что результат весьма чувствителен к величине Ре Такой метод "сверху вниз" можно использовать при больших и для выбора корня и дальнейшей работы с левыми н правыми поддеревьями. При получении достаточно малого подцерева возможно применение ацгоритыа К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
