Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

Мгновенное решение.

Пусть где Fi определяется соотношением (4.1). Справедлива следующая теорема.

Теорема 49. Пусть ЗИП I = (Xint>Vyрш) — одномерная задача интервального поиска, т. е. задача типа Sint, ~ базовое

множество, определяемое соотношениями (4.13)-(4.16) и Я(/)==

= P(0(y,pi„t)). Тогда, если функция плотности вероятности

yev

р(х), определяющая вероятностную меру Р, ограничена константой с, то

Доказательство. Пусть V = {yi,...,y*}, причем у ^ ••• ^ ^ Ук, т. е. К — множество, упорядоченное в порядке неубывания своих элементов.

Нижняя оценка следует из теоремы 4.

Построим ИГ, на которой достигается верхняя оценка одномерной задачи интервального поиска.

Возьмем точку, объявим ее корнем графа и обозначим 0о- Выпустим из корня два ребра, одно из которых будем считать левым, а другое правым. Конец левого ребра обозначим 0, а конец второго —- 02-

Пусть m — некоторый параметр, значение которого определим позже.

Припишем корню переключатель y_>m(u, v) из множества G3. Левому ребру припишем 1, а правому 2.

Выпустим из вершины 0 первое дерево бинарного поиска для библиотеки V, описанное в разделе 2.2.1, но только нагрузку переключательных вершин мы будем брать из множества G2, а вместо предикатов /=>а использовать предикаты Xa,pint ^ ^1- Обозначим это дерево через D.

Для удобства дальнейшего изложения назовем множество переключательных ребер дерева D переключательной частью дерева D, а множество предикатных ребер — предикатной частью дерева D.

Обозначим лист, которому соответствует запись у*, через а* (г = 1,к). Из каждого листа а, (г = 1, А: — 1) выпустим ребро, ведущее в лист а*+1, и припишем ему предикат Xyt+upint ^ ^1-

Это множество из 1)-го ребра назовем правосторонней концевой цепью.

Теперь из вершины 02 (напомним, что это вершина, в которую ведет правое ребро, исходящее из корня) выпустим m — 1 ребро, припишем им числа от 1 до т — 1, объявим 02 точкой переключения и припишем ей переключатель y.>mG (напомним, что т — введенный ранее параметр). Отметим, что из 02 мы выпустили именно тп — 1 ребро, хотя переключатель у.>тп может принимать т значений.

Конец ребра, исходящего из вершины 02 и имеющего номер г, обозначим 0.

Введем множество номеров 5 = {si,..., sm_i} такое, что Sj — номер записи из V такой, что ySi ближайшая слева запись к точке г/m (г = 1,т — 1), а если такой записи не существует, то Si = 0.

Возьмем к новых точек, объявим их листьями и обозначим а,... ,а'к. Каждому листу а* (г = 1 ,к) припишем запись у* (тем самым каждая запись у* будет приписана двум листьям — а» и а{).

Из каждого листа а (г = 2,к) выпустим ребро, ведущее в лист а{_и припишем ему предикат Xy<_i € ^1*

Это множество из (fc-l)-ro ребра назовем левосторонней концевой цепью.

Теперь для каждой вершины проделаем следующие действия. Если Si ф 0, то из выпустим ребро, ведущее в лист а'3{, и припишем ему предикат Xyt.,pintF. Если Si < к, то из выпустим ребро, ведущее в лист a3.+i, и припишем ему предикат Ху,<+ьР<п* € ^1-

Это множество ребер, исходящих из вершин (i = l,m — 1),

назовем правой предикатной частью.

Полученный таким образом ИГ обозначим через Uq.

Покажем, что граф Uq решает одномерную задачу интервального поиска I = (Хш, V,pint).

Каждая запись у* € V соответствует ровно двум листьям графа Uq, т.е. LUo(yi) = {<**,<*•}. Так как 0{y,pint) = Nxv,Pint и так как в каждый лист а* и а ведут только ребра, которым приписаны предикаты xy, то

Тогда согласно теореме 1 достаточно показать, что

для любого yi € И, или, что то же самое, показать, что для Vx 6 6 О (уi, pint) либо 4>ai(x) = 1, либо (ра[(х) = 1, т.е. из корня либо в лист aj, либо в лист а существует проводящая цепь.

Пусть как и ранее Ла = {х = (и, v): 0 ^ v - и ^ а}.

Возьмем произвольную запись yi Е V.

Рассмотрим сначала случай, когда х = (u, v) Е А/т П 0(yi, pint)- Это означает, что v — и < 1/тид^у*^г/.

Покажем, что из корня в лист а* существует проводящая цепь.

В рассматриваемом случае y_>m(x) = 1 и проводимость ребра (A,0i) будет равна 1.

Отметим, что проводимость ребра (Д>э?г) будет равна 0.

По аналогии с теоремами 13 и 19 нетрудно заметить, что в дереве D (растущем из вершины Р) существует проводящая цепь, ведущая из в такой лист ay, что запись у,, ближайшая справа к и точка из V, принадлежащая отрезку [и, v] (такая точка существует, так как у» € [и, г>]). Таким образом, справедливо и ^ yj ^ yi ^ v. Отсюда легко видеть, что часть правосторонней концевой цепи, ведущая из у, в у*, является проводящей.

Таким образом, мы показали наличие проводящей на запросе х цепи, ведущей из корня в лист or*.

Отметим также, что а'{ (х) = 0, так как в лист aj можно попасть только через ребро (Дь/Ъ)» проводимость которого на запросе х, как мы уже отмечали, равна 0.

Рассмотрим теперь случай, когда т. е. vи ^ 1 /га и u ^ yi О-

В этом случае 9-,™(х) — 2 и проводимость ребра (fio>Pi) будет равна 0, а проводимость ребра (Дь/Зг) равна 1.

Пусть j € {1, m — 1} — такой номер, что j/m — ближайшая справа к и точка. Легко видеть, что д.,т(х) = j.

Так как vи ^ 1/тп, то точка j/m принадлежит отрезку [гх, г»].

Рассмотрим два случая.

1) Ух j/m.

Тогда и ^ yi ^ у3. ^ v, так как t/ej. — ближайшая слева к j/m запись из библиотеки V. Отсюда следует, что проводимость ребра, ведущего из /?'• в лист а!а. равна 1. Осталось заметить, что проводимость части левосторонней концевой цепи, ведущей из a'3j в aj, также будет равна 1, так как 0 ^ у» ^ y8j ^ v.

Отметим также, что в этой ситуации ipai (х) = 0, так как в лучшем случае мы попадем в вершины правосторонней концевой цепи в точке -которая в этой цепи находится после точки а*.

2) yi > j/m.

Тогда и < Vsj+i ^ Vi ^ v. Отсюда следует, что проводимость ребра, ведущего из /?'• в лист о^+ь равна 1, и проводимость части правосторонней концевой цепи, ведущей из ocSj+ в а*, также равна 1 на запросе х.

Аналогично предыдущему случаю а' (х) = 0.

Тем самым, мы показали, что для Утд 6 V и Vx G X: х pint Vi в графе существует проводящая на запросе х цепь, ведущая из корня в какой-либо (но ровно в один) из листьев oti и а.

Что и доказывает, что граф Uq решает задачу I.

Подсчитаем сложность графа Uo.

Рассмотрим сначала произвольный запрос х G Ai/m.

В этом случае

Здесь первое слагаемое соответствует вычислению переключателя g-tm в вершине Ро- Второе слагаемое дают переключатели, входящие в единственную проводящую цепь, пролегающую через переключательную часть дерева D. Третье слагаемое соответствует вычислению одного или двух предикатов, соответствующих предикатным ребрам из предикатной части дерева D, растущим из вершины, в которую ведет проводящая цепь. Четвертое слагаемое соответствует вычислению предикатов, соответствующих ребрам, исходящим из листьев, записи которых входят в ответ (по одному на каждую запись).

Рассмотрим случай, когда х € ХАц/ш.

Тогда

Здесь первое слагаемое соответствует вычислению переключателя <7_, второе — переключателя д.}ГП из вершины /?2, третье — вычислению одного или двух предикатов, приписанных ребрам, исходящим из той вершины /?'•, в которую ведет проводящее ребро из 02- И, наконец, четвертое слагаемое, как и ранее, соответствует вычислению предикатов, соответствующих ребрам, исходящим из листьев, записи которых входят в ответ. Как мы показали ранее, для любой записи г/*, вошедшей в ответ, ровно у одного из листьев а* и а. функция фильтра будет равна 1, и, следовательно, каждой записи соответствует ровно одно ребро и соответственно ровно один вычисленный предикат.

Подсчитаем сложность графа Uq:

Поскольку граф Uq решает задачу /, то и следовательно, используемое выше равенство

доказывается простой сменой порядка суммирования.

Подсчитаем объем графа U$:

Здесь первое слагаемое соответствует ребрам, исходящим из . Второе слагаемое есть количество ребер в дереве D. Третье и четвертое слагаемые соответствуют ребрам из правосторонней и левосторонней концевых цепочек. Пятое слагаемое — это ребра, исходящие из вершины 02- И, наконец, шестое слагаемое не меньше чем число ребер, исходящих из вершин 0[ (г = 1 ,т).

Возьмем в качестве параметра т = 2 с [log2 А;] и получим

что и доказывает утверждение теоремы 49.

Дадим неформальное описание алгоритма, приведенного выше.

Пусть нам дано множество У = {уь •.. ,У*}, в котором мы должны производить поиск. Сначала упорядочим его в порядке возрастания. Если известна оценка сверху с функции плотности вероятности появления запросов, то в качестве параметра т возьмем т = 2c[log2fc], если же с неизвестна, то вместо нее можно взять любое число, например, с = 2. Затем для У построим множество номеров 5 = = {si,...,5m_i}, описанное выше. Отметим, что оно строится только однажды. Теперь поиск по произвольно взятому интервалу-запросу х = (и, v) производится следующим образом.

Сначала вычисляется длина запроса х.

Если она меньше чем 1/т, то в множестве У бинарным поиском находится ближайшая справа к точке и запись. Далее, начиная с этой записи, просматриваются слева направо все записи из К и сравниваются с правым концом запроса — точкой v до тех пор, пока очередная запись не станет больше v. Тем самым в этом случае, помимо перечисления ответа, производится порядка log2 к действий.

Если v — и ^ 1/т, то с помощью функции д. получаем номер j точки j/m, попадающей в интервал [и, г;]. Затем, начиная с записи с номером 5j, просматриваем справа налево записи из У и сравниваем с левым концом запроса — точкой и. Как только очередная запись окажется меньше и, мы, начиная с записи с номером 5j + l, просматриваем слева направо записи из У и сравниваем с правым концом запроса — точкой v до тех пор, пока очередная запись не станет больше V. Тем самым, в этом случае мы, помимо перечисления ответа, производим 4 лишних действия (сравниваем I» — и с 1/т, вычисляем функцию у.,т, делаем 1 лишнее действие, идя справа налево, и 1 лишнее действие, идя слева направо).

Осталось заметить, что параметр m подобран так, что средняя сложность первого случая не превышает 1, если известна оценка сверху функции плотности вероятности, и не превышает некоторой константы, если эта оценка точно не известна.

И, наконец, заметим, что данный алгоритм требует дополнительную память порядка log2 к, чтобы хранить множество S.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы