НИКИТИН А. Е.
Научный руководитель – А. В. ТРУСОВ
Московский инженерно-физический институт (государственный университет)
АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА ОПТИМАЛЬНОГО ПОИСКА
Исследуется проблема построения дерева оптимального поиска для вершин с весами. Предлагается эвристический алгоритм для решения задачи.
При попытке построения дерева полным перебором количество различных деревьев поиска для заданного числа вершин n растет экспоненциально. ирт [1] отмечает немаловажное свойство оптимальных деревьев поиска: каждое их поддерево оптимально, что позволяет сразу же сократить затраты по количеству операций до 
Алгоритм решения, описанный Д. Кнутом [2], сокращает эти затраты до 
по количеству операций и 
по затратам памяти. Однако данные алгоритмы могут быть неприемлемы для действительно больших n (порядка десятков тысяч). Возникает потребность в более эффективных алгоритмах.
Алгоритм, предложенный Ху и Таккером, предусматривает точное решение упрощенной задачи. В решении не учитывается частота поиска ключевых слов, то есть фиксируются только неудачные попытки поиска. Оценки алгоритма – 
по количеству операций и 
по затратам памяти.
Другой подход заключается в решении задачи приближенными, эвристическими методами, не упрощая ее постановку. К подобным решениям относится алгоритм Уолкера и Готлиба, основанный на нахождении "центра тяжести" исходного набора ключей с соответствующими весами. Оценка сложности данного алгоритма аналогична оценке для алгоритма Ху и Таккера.
Предлагаемое решение также является эвристическим и также имеет оценки 
на количество операций и 
на потребности в памяти. Пусть необходимо построить дерево поиска из n ключей 
, отсортированных по возрастанию. Каждому ключу поставлена в соответствие величина 
– количество поисков ключа 
.
Идея алгоритма заключается в следующем: для каждой вершины вычисляется величина
(1)
где
, 
(2)
а функция 
должна отражать структуру левого и правого поддеревьев при выборе i-ой вершины в качестве корня. Примем за 
среднюю высоту идеально сбалансированного дерева из k вершин. Выберем оптимальную корневую вершину по минимальному значению 
:
(3)
и повторим данную процедуру для левого и правого поддеревьев 
-ой вершины. Несмотря на, казалось бы, существенное пренебрежение при определении 
, сравнение с точным алгоритмом при малом количестве вершин показало отклонение величины взвешенной длины пути в среднем не более чем на 1%.
Существует предложение о расширении алгоритма на случай, учитывающий неудачные поиски. Для этого расширим множество ключей следующим образом: 
, 
с нечетными индексами соответствуют псевдоключи неудачных поисков 
с соответствующими им количествами запросов. По формуле (3) 
теперь ищем только среди четных i. Эффективность такого подхода по сравнению с другими методами, однако, пока должным образом не исследована.
В данный момент ведется работа по проверке эффективности алгоритма при большом (несколько сотен) и очень большом (тысячи и десятки тысяч) количестве вершин. Также проводится теоретическая оценка максимального отклонения взвешенной длины пути для дерева, построенного по предложенному алгоритму, от оптимального.
Литература
Н. Вирт Алгоритмы и структуры данных – Невский диалект, СПб, 2001. Knuth D. A. Optimum Binary Search Trees. – Acta Informatica, 1, №1(1971), 14-25.
