![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Оптимальные деревья поиска. Эффективность их применения. Алгоритм построения оптимального дерева поиска.Во всех наших рассуждениях по поводу организации деревьев поиска до сих пор исходили из предположения, что частота обращения ко всем вершинам одинакова, т. е. все ключи с одинаковой вероятностью рассматриваются как аргументы поиска. Если нет других, то такое предположение является разумным. Но встречаются ситуации, когда есть информация о вероятности обращения к отдельным ключам. Обычно для таких ситуаций характерно постоянство множества ключей, т. е. в дерево не включаются новые ключи и не исключаются старые. Структура дерева остаётся неизменной Типичный пример – сканер транслятора, определяющий не относится ли каждое слово исходного текста программы к классу ключевых для данного языка программирования. Статистические измерения для 100 программ могут дать точную информацию об относительных частотах появления отдельных ключей. Пусть Условимся, что корень находится на уровне 1. Тогда средняя длина (среднее значение) пути всего дерева представляет собой сумму всех путей от корня к каждой вершине, умноженной на вероятность обращения к этой вершине.
где h k – уровень вершины k. Цель – минимизировать среднее значение l ср. Пример. Задано множество ключей {k i} {1 , 2 , 3}, n = 3, Количество бинарных деревьев, которые можно построить из n узлов вычисляется по формуле: Приблизительное равенство верно при n ³ 10.
a)
b)
c)
При данном распределении вероятностей лучшим является вырожденный вариант ( вариант а ). Сканер транслятора требует ставить задачу в более общих условиях, ведь слова, встречающиеся в исходном тексте не всегда являются ключевыми. Обнаружение, что данное слово не является зарезервированным, можно считать обращением к некоторой специальной вершине. Если известна вероятность g j того, что аргумент поиска х находится между двумя ключами k j и k j + 1 , эта информация существенно трансформирует структуру дерева оптимального поиска. Обобщим задачу: учтём неудачный поиск. Средняя длина пути в этом случае
Специальная вершина обозначается квадратом и существует для всех пустых поддеревьев. Все эти специальные вершины являются внешними, остальные узлы – внутренними. hi – уровень внутренних вершин, который начинается с 1.
Эту среднюю длину пути Р называют ценой дерева поиска, т. к. она представляет некоторую меру поиска ожидаемых затрат. Дерево поиска, имеющее минимальную для всех деревьев, заданных множеством ключей {k i} и вероятностями pi и g j, где будет находиться специальная вершина, называется оптимальным деревом. Вместо вероятностей pi и g j мы будем использовать счётчики частоты обращений. Введём переменные ai – число поисков с аргументом x = k i; b j - число поисков с аргументом х , лежащим между ключами k j и k j + 1. b 0 – число поисков с аргументом x < k 1 b n – число поисков с x > k n
Учитывая, что число возможных конфигураций из n вершин растёт экспоненциально, задача построения оптимального дерева методом перебора является безнадёжной. Воспользуемся принципом: любое поддерево оптимального дерева оптимально. Этот принцип подсказывает вычислительную процедуру, с помощью которой находится всё большие и большие оптимальные поддеревья, таким образом дерево растёт от листьев к корню. В основе этого алгоритма лежит следующее уравнение P = P L + W + P R , W – общее количество поисков, вес дерева P L – взвешенная длина пути левого поддерева P R – взвешенная длина пути правого поддерева. Пример. Р = 8*1 + 5*2 + 3* 3 = 5*1 + 3*2 + 8 + 5 + 3 P = P L + W
P L W Пусть теперь T i j - оптимальное поддерево , состоящее из вершин k i + 1 , k i + 2 , … , k j и частот a i + 1 , a i + 2 , … , a j ; b i , b i + 1 , … , b j T o n - всё дерево W o n - вес всего дерева P o n - взвешенный путь всего дерева W i j - общее число поисков для этого поддерева P i j - взвешенный путь для поддерева ( i j ) 0 £ i < j £ n При начальных условиях Wii = bi, 0 £ i £ n T i i имеет только специальные вершины. P i i = 0, 0 £ i £ n W i j = W i j – 1 + a j + b j, 0 £ i < j £ n O( n 3 ) - сложность вычисления P i j .
|