Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 45
Текст из файла (страница 45)
Пусть т„— значение й, при котором достигается минимум в (4,72). Можно ограничить поиск т„намного меньшим интервалом, т. е. уменьшить число оценочных шагов / — с. Это основано на следующем наблюдении; если мы нашли корень тп оптимального поддерева Тьь то ни добавление к дереву справа какого-либо узла, ни удаление его самого левого узла 4.4, Дрввоввдмьи структуры 266 ьщда не смогут сдвинуть этот корень влево. Это свойство можно представить как г; 1, (гп(ггы (4.73) по шраннчивает поиск возможных значений го диапазоном г, ь,.,, гвььг и дает общее число элементарных шагов О1л'), Теперь можно построить алгоритм оптимизации со вс:мп деталями.
Мы используем следующие определения 7 — оптимальные деревья, состоящие из узлов с ключамн 1с и ..., Ь,: а,: частота поиска Ь,. 2 Ь,: частота поиска аргумента х, лежащего между лг и )г;ы. 3 ю,:весТи, 4. рл: взвешенная длина пути в Тп. 5 г„: индекс корня Ти. Гслп дан 1уре 1паех=б..и мы описываем следующие массивы: а: аггау[1 ., и] о1 1лгеясг,' Ь: аггау[1лИсх] о1' ш1вувг1 р,ич аггау[нп1ег, Ьи1вх] оГ т1сяег; г: агга у[як)ех, 1лг1ех] оГ тг)ел (4.74) В случае Л = 1 мы имеем дело с деревьями, состоящими из одного узла, который, разумеется, является корнем (рис. 4.38): $ог:=О 1о и — 1 г[о Ьеи)п 1:= г+ 1; р[1, 1];= р[1, г]+ р[1, 1]; г[1, Д:=1 (4.76) епд Предположим, что вес юч получен из а и Ь очевидным спосо.
бом (см. 4,71), Рассмотрим теперь ш как аргумент процедуры, которую мы должны написать, а г будем считать ее результатом, так как г полностью описывает структуру. Перемени)ю р могкио рассматривать как промежуточный результат. Начиная рассмотрение с наименьших возможных поддеревьев, т, е. ие содержащих вообще никаких узлов, мы переходим ко все большим и ббльшим деревьям. Обозначим ширину 1 — 1 поддерева Ти через Ь. Тогда мы можем простым способом найти значения ри для всех деревьев с Ь = О согласно (4.72): $ог 1:= О (о а г(о р[1, 1]:= ге[1, 1] (4.75) 4.
Динамические ииформаяиоиние структуры Заметим, что т обозначает левую, а 1 — правую границу индексов в рассматриваемом дереве Тн. Для случаев Ь ~ 1 мы используем оператор цикла с параметром Ь, принимающим значения от 2 до и, причем случай Ь = п перекрывает все дерево уо „. В каждом случае минимальная длина пути рн и соответствующий индекс корня гн определяются простым ет) т ) Рве.
4.38. Оитнмальное дерево е одним узлом. оператором цикла с параметром; индекс Ь принимает значения на интервале, заданном в (4.73): ог Ь:=2 то п до аког ~':=0 го п — Ь до Ьея!п 1:=1+ Ь; 14. 77) «найти т и т!п= миттнмум(р[с, т — 1]+ р[т, 1]1 для всех т, таких, что г[г, 1 — !]-..т~~г[г'+ 1, 1]»; р[1, /]:= тн!и+ю[! 1]! г[! 1]:=т ецио Детальное описание оператора, заключенного в кавычки, можно найти в программе 4.6. Средняя длина пути в 7с,ь теперь определяется коэффициентом ро „/юс, „, а его корень ес~ь узел с индексом го, „.
Из алгоритма (4.77) видно, что затраты на определеш.е оптимальной структуры имеют порядок 0(пз), объем необходимой памяти составляет также 0(п'). Это неприемлемо, если п очень велико. Поэтому крайне желательны алгоритмы с большей эффективностью. Один из них — алгоритм, разработанный Ху и Таккером [4,5], который требует только 0(п) обьема памяти н 0(п 1одп) вычислений.
Но он подходит только для случаев, когда ключи имеют нулевую частоту (а, = 0), т. е. когда учитываются только неудачные случаи поиска. Другой алгоритм, таиже требующий 0(п) единиц памяти и 0(п.1одп) вычислений, был описан Уолкером 44, древовидные структуры 267 и Готлибом [4.11). Однако с помощью этого алгоритма мож. но построить не оптимальное, а лишь почти оптимальное дерево. Поэтому он может основываться на эвристических принципах.
Основная идеи следующая: Предположим, что узлы (настоящне и специальные) распределены па линейной шкале с весами, соответствующими ь х частотам (илп вероятностям) обращения. Найдем узел, ближайший к «центру тяжести». Этот узел называется пентрондом и имеет индекс л л — „'(Еь, -«2 ь ь,), (4.78) 4.4.10. Изображение древовидной структуры Теперь мы перейдем к сопутствуюшей задаче: как сформировать выходной файл, который изображает структуру дерена в достаточно ясной, графической форме, если в нашем распоряжении имеется только обычное печатающее устройсс во) Иначе говоря, мы хотели бы нарисовать дерево, печатая кльочн в виде узлов и соединяя их соответственно горизонтальнььмп п вертикальными линиями. у!а устройстве построчной печати, нходные данные которо:о представляются в виде текстового файла, т.
е. в вида . оследовательностп символов, мы можем «двигаться» лишь строго последовательно слева направо и сверху вниз. Поэтому кажется разумным вначале построить представление дереви, которое близко соответствует его топологической структуре. Затем иа следующем этапе нужно упорядоченно отобразить эту картину на печатаемую страницу и вычислить точные координаты узлов н дуг. 'Тля решения первой задачи мы можем воспользоваться нашим опытом работ с алгоритмами формирования дерева, и поэтому мы без колебаний выбираем рекурсивное решение рекурсивно поставленной задачи.
Мы строим функцию, назы- округленный до ближайшего целого. Если все узлы имеют одинаковый вес, то корень искомого оптимального дерева очевидным образом совпадает с центроидом и — как нам представляется — в большинстве случаев будет находиться в близком соседстве с центрондом. Тогда на ограниченном интервале ищется локальный оцтпмум, после чего эта же пропедура применяется к двум полученным поддеревьям. Вероятность того, что корень находится очень близко от центроида, возрастает с увеличением размера дерева и, Как только поддеревья достигают «обозримого» размера, нх оптимум можно определять с помощью описанного выше точного алгоритма. е. Динамические инфармацианные структуры ваемую !тее, подобную той, которая использовалась в программе 4,3.
Параметры ! и ! ограничивают значения индексов узлов, которые принадлежат дереву, Его корень определяется как узел с индексом гп. Но прежде всего нам нужно ойисать тип переменных, представляющих узлы. Они должны содер. жать две ссылки иа поддеревья и ключ узла. Для целей, которые будут обсуждаться на следующем этапе, нводятся также два дополнительных поли, называемые роз и (тпй. Описания типов показаны в (4.79), и процедура-функция включена в программу 4.6.
(уре те! = — н!пос(е; пойе =гссогг! йейс а((а; рорд !тпероз!'!топ; (4.79) (е(!, гтрй!, !тпй: ге! епд Отметим, что эта процедура подсчитывает число формируемых узлов с помощью глобальной переменной-счетчика Ф. й-му узлу присваивается й-й ключ, а поскольку ключи упо, ядочены в алфавитном порядке, й, умноженное на постоянный масштабный коэффициент, дает горизонтальную координату каждого ключа; это значение сразу запоминается вместе с остальной информацией. Заметим также, что мы отказались от соглашения, что ключи являются целымп числами, н счпт таем, что онн относятся к типу а(!а, означающему массивы символов определенного (максимального) размера, на которых задан алфавитный порядок.
Чтобы ясно представить себе, что мы теперь получили, рассмотрим рис. 4,39, Если дано множество из п кл!очей и вычисляемая матрица тп, то операторы й:= О; гоо!:= !гее(О,п) сформируют связанную древовидную структуру с горизонтальными позициями узлов, содержа!помпея в их записях, и вертикальными позициями, неявно заданными их уровне!! в дереве. Теперь мы можем перейти к следующему этапу: отображснио дерева на страницу. В этом случае мы должны продвигаться строго последовательно от уровня корня вниз.
На каждом шаге обрабатываешься один пяд (уровень) узлов. Но каким образом мы находим узлы, лежащие в одном ряду? Для этой цели, а именно связывания их!ее!С узлов, находи. шихся на одном уровне, ранее мы ввели поле записи, называемое (!пй. Устанавливаемые связи показаны пунктирными линиямн на рнс. 4.39. На каждом этапе работы предпотщ гнется наличие цепочки, связывактшсй! узлы, ко!орые нужно напечатать в одном горизонтальном ряду. Мы называсм эту 4.4. Древовидвыв структура цепочку с1!ттеп!' (текущей). Рассматривая каз1сдый узел, мы определяем его потомков (сслн они имеются) и связываем их во вторую цепочку, которую мы называем веха (следующей), Когда мы продвигаемся на один уровень вниз, цепочка Вех( становится цспочкон ситтеи1, а т!ех~ присваивается знаюнпе и!!.
тоо1 самоон ш и! м1 Ы1 п~1 Ы! 1'пс. !.М, псрсао, парпсопщщос с помощью программы 4.6. Подробно этот алгоритм описан в программе 4.6. Следу!о. шне замечания могут прояснить некоторые моменты: 1. Списки (цсгочки) уз,1ов, находящихся на одном уровне, форх1пруются слева направо, в результате самын левый узел оказывается последним. Поскольку узлы дол!кны печататься в порядке появления, список нужно инвертировать, Это пропсход:1т в тот момент, когда цепочка пест' стано антс 9, цспоч ко!1 си ггелй 2, Строка. в которой печатаются ключи (глащшя строка), содержит также горизонтальные !асти вдуг» (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
