Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 [ 87 ] 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

цогда не смогут сдвинуть этот корень влево. Это свойство jJojKHO представить как

л/-!<. /<i+l./. . (4.73)

ограничивает поиск возможных значений диапазоном **. ri+i.j и дает общее число элементарных шагов

п1п) Теперь можно построить алгоритм оптимизации со рсемй Деталями. Мы используем следующие определения J-.. - оптимальные деревья, состоящие из узлов с ключами

1 аг- частота поиска ki.

2 6/: частота поиска аргумента х, лежащего между к/ и ki+i.

3. Wij-- вес Тц.

4. рц: взвешенная длина пути в Г,/. Б. щ: индекс корня Tij.

Если дан

type index =Q. .п мы описываем следующие массивы:

1а: апй^[\. .п\о1 integer; I Ъ: unuy[index\oiinteger;

I p,w: an y{index,index\ol integer; Н-)

i /: array[zWex,M?t/ex] of/Wex

редположим, что вес wij получен из а и 6 очевидным способом (см. 4.71). Рассмотрим теперь w как аргумент процедуры, которую мы должны написать, а г будем считать ее результатом, так как г полностью описывает структуру. Переменную р можно рассматривать как промежуточный результат. Начиная рассмотрение с наименьших возможных поддеревьев, т. е. не содержащих вообще никаких узлов, мы переходим Ко все большим и большим деревьям. Обозначим ширину j-i поддерева Тц через h. Тогда мы можем простым способом найти значения ри для всех деревьев с ft = О согласно (4.72):

for / :=0 to rt do p[i, i] := w[i, t\ (4.75)

В случае ft = 1 мы имеем дело с деревьями, состоящими из Одного узла, который, разумеется, является корнем (рис. 4.38):

Ьг г:==0 to п - 1 do

кbegin I; p{i, i\-\-p[U H /]:=/ (4-76)



Заметим, что i обозначает левую, а / - правую границу дексов в рассматриваемом дереве Тц. Для случаев \ используем оператор цикла с параметром h, принимающи значения от 2 до п, причем случай п перекрывает в дерево Го, п- В каждом случае минимальная длина пути й соответствующий индекс корня щ определяются простьщ


Рис. 4.38. Оптимальное дерево с одним узлом.

оператором цикла с параметром; индекс k принимает значения на интервале, заданном в (4.73);

or л := 2 to rt do for /:=0 to n-h do

begin j:=i-{-h; (4.77)

найти m и min = минимум(р[г, m - 1] + p[m, j]) для всех m, таких, что r[i, / - 1] < m < r[r + 1. !] , p[i, j] min + w[i, j]; r[i, j] := m

Детальное описание оператора, заключенного в кавычки, можно найти в программе 4.6. Средняя длина пути в Го, п теперь определяется коэффициентом po,n/wo,n, а его корень есть узел с индексом го, .

Из алгоритма (4.77) видно, что затраты на определение оптимальной структуры имеют порядок 0{п^), объем необходимой памяти составляет также О(п^). Это неприемлемо, если п очень велико. Поэтому крайне желательны алгоритмы с большей эффективностью. Один из них -алгоритм, разработанный Ху и Танкером [4.5], который требует только О ( ) объема памяти и O(rt-logn) вычислений. Но он подходит только для случаев, когда ключи имеют нулевую частоту {ai == 0), т. е. когда учитываются только неудачные случа! поиска. Другой алгоритм, таюке требующий 0{п) еДйНйй памяти и 0( -logrt) вычислений, был описан Уолкероь*



округленный до ближайшего целого. Если все узлы имеют одинаковый вес, то корень искомого оптимального дерева очевидным образом совпадает с центроидом и - как нам представляется - в большинстве случаев будет находиться в близком соседстве с центроидом. Тогда на ограниченном интервале ищется локальный оптимум, после чего эта же процедура применяется к двум полученным поддеревьям. Вероятность того, что корень находится очень близко от центроида, возрастает с увеличением размера дерева п. Как только поддеревья достигают обозримого размера, их оптимум можно пределять с помощью описанного выше точного алгоритма,

4.4.10. Изображение древовидной структуры

(. Теперь мы перейдем к сопутствующей задаче: как сформировать выходной файл, который изображает структуру де-ева в достаточно ясной, графической форме, если в нашем распоряжении имеется только обычное печатающее устройство? Иначе говоря, мы хотели бы нарисовать дерево, печатая ключи в виде узлов и соединяя их соответственно горизонтальными и вертикальными линиями.

На устройстве построчной печати, входные данные которого представляются в виде текстового файла, т. е. в виде последовательности символов, мы можем двигаться лищь Строго последовательно слева направо и сверху вниз. Поэтому Кажется разумным вначале построить представление дерева, которое близко соответствует его топологической структуре, атем на следующем этапе нужно упорядоченно отобразить вту картину на печатаемую страницу и вычислить точные роординаты узлов и дуг.

Для решения первой задачи мы можем воспользоваться Нашим опытом работ с алгоритмами формирования дерева, 5 поэтому мы без колебаний выбираем рекурсивное решение рекурсивно поставленной задачи. Мы строим функцию, назы-

ротлибом [4.11]. Однако с помощью этого алгоритма мож-Q построить не оптимальное, а лищь почти оптимальное де-ggo. Поэтому он может основываться на эвристических прин-liifiax. Основная идея следующая:

Предположим, что узлы (настоящие и специальные) распределены на линейной шкале с весами, соответствующими 0 частотам (или вероятностям) обращения. Найдем узел, б'ЛНЖД-йший к центру тяжести . Этот узел называется центроидом и имеет индекс




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 [ 87 ] 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133