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

Cтраница 2

Задача минимизации (13.4) при условиях (13.5), (13.6) и составляет исходную математическую модель для выбора оптимального дерева трубопроводной сети на ее избыточной схеме. Такой переход опирается на построение частичной функции Пагранжа и использование ее для проведения аналитической оптимизации по группе переменных. Данный прием описан в книге [21] на примере конкретной задачи. [16]

На рис. 20.8 в части ( Ь) собрана некоторая статистика по производительности 32-процессорной системы, примененной к оптимальному дереву быстрой сортировки. На уровне L0 этого дерева один процессор, выполняя этот алгоритм, строит две части. На уровне Lt добавляется еще один процессор. [17]

Иллюстрация к теореме. Корень оптимального дерева заключен между корнями двух ранее построенных деревьев. [18]

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

Обозначим значения, заключенные в первой и второй фигурных скобках правой части вышеприведенной формулы, относящейся к поддереву t ( i j) оптимального дерева, через w ( i j) и c ( i j) соответственно. [20]

Таким образом, мало того, что мы избегаем вычисления вероятностей по измеренным частотам, мы еще и выигрываем от использования в наших построениях оптимального дерева целых чисел. [21]

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

Теперь соответствующую процедуру на алгол е - 60 мы приведем без дальнейших комментариев, предупредив толь - ко, что up [ i ] - это дуга, ведущая в i в оптимальном дереве, а массив / должен по техническим причинам иметь ( т 1) - ю компоненту. [23]

Цифровой поиск отличается в важном отношении от всех других методов, описанных в этой главе: для данного множества имен существует только одно дерево цифрового поиска; таким образом, нет вопроса о построении оптимального дерева. Любой статистический анализ среднего времени поиска зависит только от допущений о содержимом таблицы. Для методов, в которых мы рассматриваем сравнение имен как элементарную операцию, любое множество п имен ведет себя так же, как и любое другое ( в предположении, что все перестановки этого множества равновероятны; см. разд. В деревьях цифрового поиска различные множества имен приводят к борам разного вида и, в частности, длины имен оказывают важное влияние на время поиска и память, необходимую для боров. Анализ и эксперименты только подтверждают естественное заключение о том, что в таблице с п именами над алфавитом из с символов поиск требует в среднем приблизительно logcn шагов с с исходами на каждом шаге. [24]

Конечно, в случае, когда ключи вводятся в дерево в случайном порядке, нет ничего невозможного в том, чтобы перестраивать дерево, которое было составлено до этого момента, и заново строить полностью сбалансированное или оптимальное дерево. Однако если учесть требуемые для этого затраты времени и оперативной памяти, то станет ясно, что, за исключением отдельных особых случаев, это практически нереально. Рассмотрим свойства случайных деревьев, построенных по методу вставки узлов без изменения ранее образованной структуры дерева. [25]

Это значит, что из внутренних узлов кодового дерева хотя бы один должен быть неполным. Но в оптимальном дереве, как отмечалось, неполные узлы могут принадлежать лишь последнему этапу, относиться к последнему выбору. Без ухудшения дерева можно так переставить сообщения, относящиеся к словам максимальной длины, что: 1) неполным будет лишь один единственный узел и 2) сообщения, относящиеся к этому узлу, будут иметь самую меньшую вероятность. [26]

Соответствующий алгоритм поиска оптимального дерева на исходной схеме состоит из следующих основных операций. [27]

Матричное представление алгоритма построения оптимального дерева снизу вверх. [28]

Поддеревья, обведенные пунктирной линией, являются оптимальными деревьями, построенными на ранних этапах алгоритма. Хотя в этом примере имеется единственное оптимальное дерево, в общем случае единственность не имеет места. [29]

Для деревьев бинарного поиска, сбалансированных по сумме весов, существуют более точные результаты. Пусть Оп - взвешенная длина пути оптимального дерева бинарного поиска для нормированного распределения частот Q Pi 2a; ) и пусть Wn - взвешенная длина пути сбалансированного относительно сумм весов дерева бинарного поиска. [30]

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