Оптимальное дерево

Cтраница 3

Когда процесс заканчивается при i - n, мы имеем искомое оптимальное дерево на п последовательных весах. На рис. 6.4 показано, как этот алгоритм строит оптимальное дерево на четырех именах А, В, С, D с весами узлов 1, 6, 4, 5 соответственно и весами листьев, равными нулю. [31]

На первом этапе осуществляется выбор на исходной избыточной схеме МКС деревьев начального приближения ( ДНП), обладающих характерными свойствами. В качестве других вариантов ДНП берутся: 1) оптимальное дерево ( ОД) ( или несколько деревьев), получаемое в результате решения схемно-структурной задачи с помощью программы СТРУКТУРА ( см. гл. [32]

Улучшение сбалансированности слияния. [33]

На рис. 18.15 внизу частичный настраивающий просмотр выполняется над первыми двумя строками. Форма этого дерева такая же, как и у оптимального дерева на рис. 18.12. Из-за размеров строк число перемещаемых записей иное. [34]

В третьей части вызывается процедура OptTree, она вычисляет дерево оптимального поиска, затем печатается изображение полученного дерева. И наконец, те же самые процедуры используются для определения и печати оптимального дерева, учитывающего лишь частоты употребления служебных слов, другие слова игнорируются. [35]

Оптимальное слияние ( новые строки заключены в скобки. [36]

На рис. 18.13 внизу показана обработка строк от коротких к длинным. Разница между этими двумя слияниями не столь значительна, как между первым сбалансированным слиянием и оптимальным деревом. Возможности оптимального слияния показаны на рис. 18.14. При десяти строках в оптимальном дереве перемещений данных на 15 процентов меньше, чем в сбалансированном. Таким образом, на последнем просмотре необходимо сохранить максимальную степень - это решающий фактор в использовании преимущества длины строк. [37]

Изображение дерева с помощью надлежащих отступов. [38]

В таблице 4.4 и на рис. 4.40 - 4.42 приведены результаты применения прогр. Различия в этих трех рисунках наглядно демонстрируют, что сбалансированное дерево нельзя считать даже приближением к оптимальному дереву, а учет частот других ( не служебных) слов сильно влияет на выбор оптимальной структуры. [39]

Среднюю взвешенную длину пути можно назвать ценой дерева поиска, поскольку она представляет собой некоторую меру для ожидаемых затрат на поиск. Дерево поиска, имеющее минимальную для всех деревьев с заданным множеством ключей kj и вероятностями PJ и qj цену, называется оптимальным деревом. [40]

Алгоритм сложности 0 ( и2) для той же задачи можно найти у Кнута [1971], где содержится также и решение упр. Ху, Таккер [1971] показали, что время О ( я2) и память 0 ( п) достаточны, чтобы построить оптимальное дерево двоичного поиска, в котором данные появляются только на листьях. [41]

Из простой идеи рассмотрения разбиения множества исходов по ветвям дерева решений оказалось возможным получить границы необходимого числа сравнений, эффективный алгоритм построения оптимального дерева для специального случая и ценный эвристический принцип, который применяется к любой задаче о дереве решений. [42]

Более того, поскольку как правило частоты обращения а priori точно не известны, обычно не имеет смысла затрачивать много усилий на построение оптимального дерева. Однако существует эффективный ( с временем и памятью 0 ( п)) эвристический алгоритм для построения деревьев, среднее время поиска на которых близко к среднему времени поиска на оптимальном дереве бинарного поиска, и такой алгоритм имеет практическую ценность. В этом разделе мы обсудим различные примеры эвристических алгоритмов и предложим способы избежать плохие эвристики. [43]

Наконец, рассмотрим те деревья решений, которые используют монету 0 в корне. Для первого сравнения набор исходов будет ( 1 7, 1), в связи с чем все алгоритмы, начинающиеся таким способом, для нас непригодны; набор же исходов ( 3, 3, 3) приводит к оптимальному дереву, показанному на рис. 1.6. Аналогичным образом устанавливается, что для оптимального дерева сравнения в первом от корня ярусе определяются единственным образом. Отсюда мы заключаем, что для задачи о четырех монетах фактически существует только одно оптимальное дерево. [44]

Страницы: 1 2 3 4