Полная версия

Главная 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.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>