OPTIMAL INFORMATION-GRAPH MODEL ORGANIZATION INCLUSIVE SEARCH IN DESCRIPTOR SEARCH ENGINES

Full Text

Введение. В общем случае включающий поиск встречается всегда, когда элементы информационного массива задаются множеством свойств (в частности, свойствами наличия дескриптора в описании документа), причем необходимо перечислить в этом массиве элементы с определенным набором свойств задаваемым запросом. В нашем случае описанием объекта файловой системы может служить: название, время резервирование, тип файла и т.д. Особенностью алгоритма включаю щего поиска является то, что его использование не подразумевает обязательное упорядочивание базы данных системы резервного копирования по какому-либо признаку. Это полезное свойство можно использовать для организации непрерывности резервирования и восстановления в случае сбойных ситуаций без дополнительных временных затрат и привлечения дополнительных ресурсов по памяти при упорядочивании файловой истории после записи каждого объекта. Задача включающего поиска Предположим, что мы осуществляем поиск в дескрипторных поисковых системах, то есть информационный массив состоит из документов, описанных множеством ключевых слов (дескрипторов) [1]. В свою очередь, запрос задает некоторую совокупность дескрипторов, и необходимо перечислить все документы, содержащие в своем описании все дескрипторы, входящие в запрос. Такой тип называется типом включающего поиска. Занумеруем некоторым образом множество всех дескрипторов (тезаурус). Каждому документу сопоставим запись, представляющую собой булев вектор длины равной мощности тезауруса, в /-ой компоненте которого стоит «0» (ноль) в том и только в том случае, когда /-ый дескриптор входит в описание данного документа. Запросы будем описывать аналогичными векторами, то есть в /-ой компоненте запроса будет стоять «0», если /-ый дескриптор входит в запрос. Теперь дадим определение типа включающего поиска. Для этого рассмотрим следующий тип задач поиска: Sbool=^B",B”,t,<T,P^, где В” - единичный я-мерный куб, то есть В” = {(о^,: ає {0,1}; (і = 1,и)}, Ъ >- - отношение поиска на Вп хВп, определяемое следующим соотношением: ь _ (х],...,хп)у(у],...,уп)ох1>у1, i = l,n, х„у, є {0,1}, где / - номер дескриптора. Таким образом, каждый компонент запроса не меньше соответствующей компоненты записи, или если в /-ой компоненте запроса стоит 0 (то есть /-ый дескриптор входит в запрос), то в /-ой компоненте записи тоже должен стоять 0 (то есть запись должна содержать /-ый дескриптор); <г - алгебра подмножеств В”, пред ставляющая собой множество всех подмножеств В" ; Р - равномерная вероятностная мера на сг,, то есть такая мера, что для любого хеВп выполнено Р(х) = l/2" и для любого Ас.Вп выполнено Р(Л) = |Л|/2И. Задачи информационного поиска (ЗИП), принадлежащие данному типу, есть разновидность задач, именуемых задачами включающего поиска, поэтому тип Sbool называется типом включающего поиска, а задачи, принадлежащие этому типу, - задачами включающего поиска. Рассмотрим функцию Ка \Х—> {0,1} , такую, ь что NK = {хеХ:хУа}, то есть характеристическую функцию (ХФ) записи а. Множество всех конъюнкций ХФ всех записей из X обозначим через M. Таким образом Af = Jv^(x):fl<eJT Подмножество вершин предикат ного информационного графа (ПИГ) U назовем характерным, если существует такая запись а, m что V ФЛ=Ка- Если в ПИГ U существует цепь, ведущая из корня в какую-либо вершину характерного подмножества, такая, что проводимость этой цепи равна Ка , то эта цепь называется главной для данного подмножества. Пусть U - произвольный ПИГ над базовым множеством F = (М,0'). Пусть B - произвольное характерное подмножество ПИГ U. Тогда в ПИГ U существует главная цепь множества B [2]. Заметим, что У, _Фа = X ъ = К , где L.r(y) -множество всех листьев, которым соответствует запись у, а значит, Ьи{у) есть характерное множество. Таким образом, справедливо следующее утверждение. Пусть I = (^X,V,>^j - задача типа Sbool. Пусть U - ПИГ над базовым множеством F = (M,0}, разрешающий ЗИП I. Тогда для любой записи у є V в графе U существует главная цепь. Назовем гранью единичного я-мерного куба Вп множество {(«!,...,«„) є В" : a. =av...,ak =егк}, при этом число п — к называется размерностью этой грани. Весом набора а = (а15.называют число его координат равных 1. Множество вершин куба, имеющих вес к, называется k-ым слоем куба Вп и обозначается Вк. Номером набора а назовем число ИЬЁ2" <*.■ І=1 «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 43 Будем считать, что наборы в слое упорядочены по убыванию номеров. Множество, состоящее из m первых наборов k-го слоя, будем называть начальным отрезком длины m этого слоя. Формула х°1 &х°2 &...&х“г, где & - знак конъюнкции, ак є {0,1}, х? = xk , х[ = xit, ікє{1,2,...,п}, к = 1,2,...,г, (г>1,и>1) , называется конъюнкцией над множеством переменных X” = {х1,х2,...,хп}, а число r - длиной этой конъюнкции. Если xt Ф xik при j фк, то конъюнкция называется элементарной. Элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Множество элементарных монотонных конъюнкций от n переменных будем обозначать через К". Функцию тождественная единица будем считать элементарной монотонной конъюнкцией длины 0, то есть будем считать, что она входит в множество К", кроме того, добавим тождественную единицу и в множество переменных X". Две элементарные монотонные конъюнкции пересекаются по переменным, если в формулах, описывающих эти конъюнкции, встречаются одинаковые переменные. Функция алгебры логики /(дс15...,хп) называется монотонной, если для любых двух наборов а и /3 из В” таких, ь что аУ/З, имеет место неравенство f («) > f (Д). Дизъюнкция элементарных монотонных конъюнкций есть монотонная функция. Множество монотонных булевых функций от n переменных будем обозначать через М”. Рассмотрим произвольную запись уєВп. Нетрудно заметить, что если {ц —ік} есть множество номеров координат вектора у равных 1, то характеристическая функция записи является элементарной монотонной конъюнкцией X „(х1,...,хп) = х,&...&хі y,t Таким образом, согласно [3], каждое из базовых множеств (мп,0^, (кп,0^ и (Хи,0^ является полным для типа Sbool, а значит, множество U(I,F) ИГ, разрешающих задачу включающего поиска, не пусто. Следовательно, тип Sbool полностью удовлетворяет необходимым условиям, и, значит, для любой ЗИП I типа Sbool существует оптимальный ПИГ над любым из базовых множеств {м”,0^, {кп,0^ и {хп,0^. Оценка сложности включающего поиска Оценим сложность включающего поиска. Для этого рассмотрим теорему Краскала-Катоны, переформулировав ее в терминах ИГ модели [4]. Теорема Краскала-Катоны. Пусть В”т - m-ый слой куба В" и AczB”. Пусть R(A) = {aeB”m+1:(3j3BA:atj3)}. Тогда минимум достигается, если A - начальный отрезок слоя В^, причем в этом случае R(A) -начальный отрезок слоя Вп^. Если АєВ", то 4 і і обозначим 0(А,у) = 0(у,У). уеА Приведем следствие из теоремы Краскала-Каь тоны. Пусть AczB^, тогда \0(A,h)\ достигает минимума, если A - начальный отрезок слоя 5” . Пусть I - ЗИП типа Sbool.. Пусть U разрешающий ЗИП I ПИГ над базовым множеством F = {Мп,0^ . Тогда существует такое разбиение библиотеки V на непересекающиеся части, что - каждая часть содержит записи одного веса, и этот вес назовем весом части; - каждой части веса m > 0 и мощности t можно поставить в соответствие такую совокупность ребер графа U, что сумма сложностей ребер из этой совокупности не меньше чем t • 21~т, причем образы различных частей при этом соответствии не пересекаются. Доказательство приводится в [5]. Следовательно, можно получить следующие оценки сложности включающего поиска. Нижняя оценка. Пусть 1 = [вп,У,>~^ - ЗИП типа Sbool. Пусть базовое множество имеет вид F = (^М”,0^, где М" - множество монотонных булевых функций. Тогда T{I,F)>2 ^P(O(y,h))~t0, ysV где tQ - число записей веса 0 в библиотеке V (^{0,1}). Таким образом, полученная нижняя оценка практически в два раза лучше мощност-ной нижней оценки. Верхняя оценка. Пусть I = (^Bn,V,>2j - ЗИП типа Sbool. Пусть базовое множество имеет вид F = (Kn,0^, где К" - множество монотонных элементарных конъюнкций. Пусть |^|=£ и т -такое число, что 2С™ <k< 2С™+1. Тогда т Т(1,Р)<\ + ^2ыСп + 2-тк. і=і Это говорит о том, что существуют библиотеки, для которых нижняя оценка асимптотически неулучшаема. «Инфокоммуникационные технологии» Том 11, № 1, 2013 44 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. Если базовое множество имеет вид F - (F,0), где F с Мп и К” с F, то существуют такие I = (Bn,V,± типа bool b что T(I,F) = 2 XP(Ofe))(l + 0(l)). yeV Приведенная нижняя оценка включающего поиска в два раза лучше мощно стной нижней оценки. В случае когда базовое множество состоит из множества переменных X”, удается найти такие задачи, для которых была получена нижняя оценка, большая по порядку, чем мощност-ная нижняя оценка. Доказательство этого факта проходит только в предположении древовиднос-ти графа, поэтому для начала рассмотрим, являются ли оптимальные ИГ над библиотеками баз данных резервного копирования древовидными в общем случае. Недревовидность оптимальных ИГ включающего поиска в общем случае Рассмотрим информационные графы над двумя базовыми множествами: базовым множеством (Xй,0) , которое будем называть базовым множеством переменных, и базовым множеством (кп,0^, которое будем называть базовым множеством элементарных монотонных конъюнкций. Для каждого из этих базовых множеств доказано существование таких задач включающего поиска, для которых удалось найти недревовидные ПИГ, которые по сложности проще любого древовидного ПИГ. Рассмотрим сначала два свойства ПИГ над Хп,0) или (Кп,0) [6]. 1. Пусть U произвольный ПИГ над базовым множеством (^Хп,0^ или (кп,0^, разрешающий некоторую задачу типа Sbool. Тогда любое ребро ПИГ U имеет сложность, не меньшую, чем 2“”. 2. Пусть U произвольный ПИГ над базовым множеством (Х",0'j или (кп,0^, разрешающий некоторую задачу I типа Sbool и имеющий вид дерева, в некоторой главной цепи записи которого встречаются два разных ребра, которым приписан один и тот же символ. Тогда граф U не может быть оптимальным для рассматриваемой задачи [5]. Рассмотрим графы над базовым множеством (Хп ,0^ и покажем существование такой ЗИП типа 5Ы, которая имеет недревовидный оптимальный ПИГ. Если п>9 и базовое множество есть множество переменных ^Х",0^, то существует такая ЗИП типа £w, для которой любой оптимальный ПИГ над (Х",0) не является деревом [7-8]. Очевидно, что данное утверждение соответствует рассматриваемому нами случаю в системе резервного копирования. Базовое множество элементарных монотонных конъюнкций. Будем рассматривать графы над базовым множеством (К",0) и покажем, что существует такая ЗИП типа Sbool, которая имеет недревовидный оптимальный ПИГ. Заметим, что ЗИП 1Х, приведенная в предыдущем подпункте, не дает желаемого результата для базового множества элементарных монотонных конъюнкций. В самом деле, подсчитаем сложность графа U0, изображенного на рис. 1, но уже понимая (как и везде далее в этом подпункте) под ребром, которому приписан символ конъюнкции, не цепочку ребер а именно одно ребро с нагрузкой в виде этой конъюнкции. Итак, Г([/0) = 2 + 4-і + (-|г--іг) + 2 4 2 2li -Л_Л =_1_х ^Ll+m+2) і^І+м+І < _|_ 2j+m+^_2m_1 + 2/+2_1) +2 (: і/+®+1 п21+т+2 Сложность графа U2, изображенного на рис. 2, будет равна гГҐТТ \ _О і 4 _ 1 ґг)21+т+2 . nfl+m+Ъх 1 \и2) ~ А +22l+m+l откуда T(U0)-T(U2) =2^+1-(2'+m+'-2m-42,+2 -1). Очевидно, что T(U0)>T(U2) для любых l, m > 0. «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 45 Покажем два полезных свойства. 1. Пусть U произвольный ПИГ над базовым множеством (кп,0^, разрешающий некоторую задачу типа Sbool, такой, что в нем есть две главные цепи, которые не пересекаются ни с какими другими цепями и которые соответствуют записям, имеющим, по крайней мере, две общие переменные. Тогда граф U не может быть оптимальным. 2. Пусть U произвольный ПИГ над базовым множеством (кп,0^, разрешающий некоторую задачу типа Sbool, такой, что в нем есть вершина, отличная от корня, с полустепенью исхода 1. Тогда ПИГ U не может быть оптимальным. Если n > 26 и базовое множество есть множество элементарных монотонных конъюнкций {Кп>0^, то существует такая ЗИП типа Shnn,, для которой любой оптимальный ПИГ над (К",0^ не является деревом [7]. Древовидность оптимальных ИГ включающего поиска в классе бесповторных сетей Было показано, что оптимальные графы над базовыми множествами (хп,0^ и (К",0^, разрешающие ЗИП типа Sbool, в общем случае не являются древовидными. Однако существует особый класс ИГ разрешающих ЗИП типа Sbool, для которых была доказана их древовидность. Это так называемые бесповторные графы. Под бесповторными графами понимается ПИГ над базовым множеством (хп,0^ или над базовым множеством (кп,0^, в которых для любой цепи нагрузки любых двух различных ребер этой цепи не пересекаются по переменным [9]. Пусть F одно из двух базовых множеств {Кп,0) или {Хп,0^, тогда для любой ЗИП I типа Sbool граф над базовым множеством F, являющийся оптимальным в классе бесповторных графов для задачи I, имеет вид дерева [10]. Алгоритмы включающего поиска Рассмотрим метод решения задачи включающего поиска, имеющий три модификации в зависимости от выбранного базового множества: множества монотонных булевых функций (^М",0^, множества элементарных монотонных конъюнкций (кп,0^ и множества базовых переменных (х”,0^. С помощью этого метода получены оценки функций T(k,Sbool,{F,0)) и T(k,Sbool,{F,0)), где Fs{Mn,K",X”}. Кроме того, получена асимптотика логарифма среднего значения сложности данного метода. В данном разделе предлагаются три алгоритма, которые позволяют для произвольно взятой библиотеки V с: В" строить информационные графы над базовыми множествами (мп,0), (кп,0^, (хи,0), разрешающие ЗИП I = l^B”,V. Эти алгоритмы будем обозначать соответственно Рх, Р Р 2 ’ 3 ’ Поскольку в задаче включающего поиска ь множество Вп и отношение фиксированы, то будем считать, что алгоритм Pt (г = 1; 2; 3) применяется к библиотеке V и результатом его применения является разрешающий задачу I = (вп ,VИГ, который обозначим через W). П оскольку ИГ P;(V) существенно будет зависеть от порядка следования элементов в библиотеке V, то будем считать, что библиотеки - упорядоченные множества. Каждый ИГ P^V) (i = 1; 2; 3) будет иметь вид дерева, и мы, используя в дальнейшем термин «дерево», будем подразумевать некоторую его укладку, причем будем считать, что в каждой вершине среди ребер, исходящих из данной вершины, задан некоторый порядок следования, и первое по порядку ребро будем называть самым левым, а последнее - самым правым, и соответственно будем определять понятия «левее», «правее». Будем говорить, что функция f покрывает функцию g, если NgcNf. Пусть f g - элементарные монотонные конъюнкции. Пересечением конъюнкций f и g назовем конъюнкцию переменных, принадлежащих как f, так и g, и обозначим ее через f ел g. Таким образом, пересечение f и g есть минимальная по числу элементов в характеристическом множестве элементарная монотонная конъюнкция, покрывающая и f, и g. В случае, когда все переменные f отличны от переменных g, будем говорить, что пересечение f и g пусто. Через f\g обозначим конъюнкцию переменных, принадлежащих f, но не принадлежащих g. Обозначим через 0 набор, состоящий из всех нулей, то есть 0 = (0,...,0). Пусть нам дана упорядоченная библиотека V. Обозначим V' = V \ {0} = {уі,у2,—,ук} ■ Индуктивно опишем процесс построения ИГ P2(Vr). Базис индукции. ^(О^}) состоит из одного ребра, начало которого является корнем ИГ, а конец - листом, которому приписана запись Уі, и этому ребру приписана функция X »■ Индуктивный переход. Пусть построен ИГ Р2{{У\ .Уы})’ 0‘ = 2;3 ... А:). Будем перестраивать его, чтобы он стал допустимым для библиотеки {уу ... yt}, следующим образом. «Инфокоммуникационные технологии» Том 11, № 1, 2013 46 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. I. Корень ИГ Р2({У\,—,Уі-\}) объявим в качестве текущей вершины р. Объявим § = X у II. Будем слева направо просматривать ребра, исходящие из вершины р, до тех пор пока не найдем ребро, пересечение нагрузочной функции которого с функцией g не пусто. 1. Если для всех ребер пересечение их нагрузочных функций с g пусто, то из вершины Р выпускаем новое ребро с нагрузочной функцией g, конец ребра объявляем листом и приписываем ему запись Уі, и на этом завершаем работу - ИГ построен. Здесь, как и везде далее, новое выпускаемое ребро становится самым правым в пучке на данный момент. 2. Если же нашлось ребро с нагрузочной функцией f такой, что пересечение f и g не пусто, то: а) если f = g, то конец этого ребра объявляем листом и приписываем ему запись Уі, и на этом завершаем работу - ИГ построен; б) если f Ф g и f = f r\g, то конец этого ребра объявляем текущей вершиной Р, объявляем g = g\f и идем на шаг II; в) если же f ф f ng, то изменим нагрузку рассматриваемого ребра на f C\g. Пусть конец этого ребра обозначен через Р', отцепим ветвь, растущую из Р', выпустим из Р' новое ребро и прицепим отцепленную ветвь к концу нового ребра (если вершина /?' была листом, то листом вместе с его нагрузкой становится конец нового ребра) и приписываем новому ребру функцию f\(f Г\ g), после чего если f = g, то объявляем вершину р’ листом, приписываем ей запись yt, и завершаем работу, иначе из вершины Р' выпустим еще одно ребро с нагрузкой g \ (/ n g), конец последнего ребра объявляем листом, приписываем ему запись yt и на этом завершаем работу - ИГ Р2{{Уі—Уі}) построен. Теперь если УФУ', то выпустим из корня P2(V) еще одно ребро, и пусть оно будет самым правым, исходящим из корня. Припишем данному ребру функцию тождественную «1», а конец ребра объявим листом и припишем ему запись « 0 ». Полученный ИГ и будет Р2 (У) . Заметим, что P2(V) есть ИГ над базовым множеством (кп,0) и, кроме того, нагрузка ребер в P2(V) однозначно определяет нагрузку листьев. Поэтому далее мы часто не будем упоминать о нагрузке листьев. Обозначим X ь = \Х ь . Теперь легко опи- V,> ysV у£. сать ИГ .fJ(F). Возьмем вершину и объявим ее корнем, выпустим из нее ребро, которому припишем функцию X » j а из конца ребра выпустим ветвь, идентичную Ру(У). ИГ РХ(У) построен. Очевидно, что Ру(У) есть ИГ над базовым множеством (АГ,0). Опишем процесс построения ИГ Р3(У'). Базис индукции. Если в нашем случае Zyb_=Xh-...-X. (l<iy<...<it<n), то і»3({Уі}) представляет собой ориентированную цепочку из t ребер, причем начало цепочки есть корень ИГ, конец цепочки - лист с записью ух, а у’-му ребру цепочки (j = 1, 2, ..., t) приписана функция xt . Индуктивный переход. Пусть построен ИГ Ръ{{Ух,-,У,-х)), (/' = 2,3,...,к). Будем перестраивать его, чтобы он стал допустимым для библиотеки {Уі,—,Уі}, следующим образом. I. Корень ИГ і^({у1,...,.у,_1}) объявим в качестве текущей вершины Р . Объявим g — X Ь . II. Будем слева направо просматривать ребра, исходящие из вершины Р, до тех пор, пока не найдем ребро, которому соответствует переменная, покрывающая g. 1. Если для всех ребер, исходящих из Р, переменная, соответствующая ребру, не покрывает g, то из вершины Р выпускаем новую цепочку ребер, аналогичную цепочке, описанной в базисе индукции, такую, чтобы конъюнкция переменных, приписанных ребрам цепочки, была равна g, конец цепочки объявляем листом, приписываем ему запись Уі и завершаем работу - ИГ Рі{{У\—Уі}) построен. Здесь первое ребро новой цепочки становится самым правым, исходящим из р. 2. Если же нашлось ребро с нагрузочной функцией Xj, покрывающей g, то если g^xt, то конец этого ребра объявляем текущей вершиной Р , объявляем g = g\Xj и идем на шаг II, иначе конец рассматриваемого ребра объявляем листом, приписываем ему запись yt и завершаем работу - ИГ ^({^....у,-}) построен. Теперь если V ФУ', то выпустим из корня Р3 (V') еще одно ребро, и пусть оно будет самым правым, исходящим из корня. Припишем данному ребру функцию, тождественную 1, а конец ребра объявим листом и припишем ему запись О. Полученный ИГ и будет P3(F). Легко заметить, что по построению каждого из ИГ Рг(У), Р2(У) , Р3(У) к произвольной записи у є V ведет цепочка ребер, проводимость которой равна X * ■. Отсюда согласно [11] каждый из ИГ Pt(V), P2(V), P3(V) допустим для библиотеки V. Рассмотрим теперь верхние и нижние оценки сложностей графов P^V), P2(V) и P3{V). Через W* обозначим множество упорядоченных библиотек из Вп мощности к. Понятно, что «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 47 К1=4’Где 4 - число размещений из n элементов по к. Обозначим через Т(Рпк,п) максимальную из сложностей ЗИП над всеми упорядоченными библиотеками мощности к, то есть Т(Рпк,п) = тах.Т(РХУ)), а через TtfXn) - VeWH среднюю сложность ЗИП над библиотекой мощности к: £ T{pt(y)) Т(Р1,к,л) = ^Г1Г.-, і = 1; 2; 3. \щ Поскольку все Pf(V) (і - 1; 2; 3) являются деревьями, то далее часто вместо термина «ИГ» будем использовать термин «дерево». Следом вершины Р в дереве D назовем поддерево дерева D, содержащее все ребра, исходящие из вершин, принадлежащих пути, соединяющему корень дерева D с вершиной Р. Левым следом вершины р в дереве D назовем поддерево дерева D, которое состоит из принадлежащих следу вершины р ребер, которые в дереве D находятся не правее ребра, принадлежащего пути, соединяющему корень дерева D с вершиной р . Библиотекой вершины р в дереве D назовем множество записей, приписанных листьям, достижимым из вершины р. Вершина дерева называется проходной, если из нее исходит одно ребро. Рассмотрим некоторые полезные свойства деревьев P2(V) и P3(V). Пусть V - произвольная библиотека, D = i?(F) (і = 2',3) , тогда это дерево обладает следующими свойствами. 1. Для любой вершины р дерева D пересечение любых двух нагрузочных функций, соответствующих ребрам, принадлежащих левому следу вершины р, всегда пусто. 2. Функции фильтров любых двух различных вершин в D различны. 3. В дереве P2(V) каждая проходная вершина является полюсом. Эти свойства достаточно очевидно следуют из алгоритмов построения Р2(V) и P3(V). Напомним, что сложностью вершины Р в ИГ называется вероятность множества запросов, проходящих в вершину Р , или, иными словами, сложность вершины Р равна Р(Л^). Высотой вершины в дереве назовем длину пути, ведущего из корня в данную вершину. Пусть D - некоторое дерево, h - натуральное число. Через r(D,h) обозначим число вершин дерева D, находящихся на высоте h. Обозначим Ц={Р,(Г):УеЖ„к}, / = 1; 2; 3. Вершину ИГ назовем внутренней, если она не является полюсом. Пользуясь определениями деревьев Pt(V) (i = 1; 2; 3), несложно показать справедливость следующих утверждений: Для любой вершины, находящейся на высоте h в любом дереве DeDf (г' = 2;3), ее сложность не более чем 2~н. Для любого дерева DeDt,i = 2;3, r{D^)<Cl+\, и для любого he {2... п} справедливо r(D,h)<Ch„. Пусть DgD2, tj - число листьев в дереве D, находящихся на высоте j (j є {1,...,и} ). Тогда для любого Ае{0...и-1} справедливо r{D,n-h)<j^V-htn_j. j=о Рассмотрим верхнюю и нижнюю оценки для алгоритмов P(V) и P2(V). Обозначим F2 — [кп,0^. Если k(n) и m(n) такие числа, зависящие от n, что к(п) —> <х>, т{п) - о{п) при п —> оо , то для i- !;2: 1- При С:1=о(к), к<Стп-. П*А^)~П^,М)~21-т*. 2. При С™ <к< 2С™: 2-m{k + C:)<f(k,Sbool,Fi)< <f(Pi,k,ri)<2l~mk(l + о(1)). 3.При к = 0(С"), к > 2С™: 2-m{k + C:)<f{k,Sbool,Ft)< <т,к,п)<2х-т(к+с:\\+о{\)). Таким образом, для задач включающего поиска удалось получить нижнюю оценку в два раза лучшую, чем мощностная нижняя оценка. Кроме того, было доказано существование задач, для которых эта нижняя оценка асимптотически не улучшаема.

About the authors

V. E Ljalin

Email: velyalin@mail.ru

S. A Maltzev

Email: rshavas@mail.ru

V. P Taranucha

Email: kra_dept@istu.ru

D. R Shishov

Email: d1men27@mail.ru

References

Supplementary files