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

Многомерная задача интервального поиска

Многомерная задача интервального поиска состоит в поиске в конечном подмножестве n-мерного пространства всех тех точек, которые попадают в n-мерный параллелепипед-запрос. Опишем тип задач поиска, который соответствует n-мерной задаче интервального поиска.

Пусть Утеп = [0,1]п — множество записей и

— множество запросов. Пусть на множестве X{nt п задано вероятностное пространство (Xintnjcr, Р), где Р задается функцией плотности вероятности р(х).

Отношение поиска ршп определено на Xintn х Yintn и задается следующим соотношением:

(til,«1 pintП (У1,---,Уп)

Тогда тип Sintn — {Xintn , Ушп,Pintn,&,P) назовем типом многомерного интервального поиска.

Мгновенное решение многомерной задачи интервального поиска.

Пусть V = {ух,...,у*} — конечная библиотека, элементы которой принадлежат Yintn.

Пусть 5 С V и 1 ^ г'х < • • • < г/ ^ п.

Обозначим через

проекцию множества S на компоненты i,..., г/.

Обозначим

Обозначим

Для каждой пары (у', у") 6 W1 определим множество

Пусть у* = (У1,У2,...,у*1,у?) е Yi (г = 0,п - 1). Здесь и далее под значком у0 будем понимать пустое место или отсутствие значка, так, например, запись р~0 будем понимать как р а запись М1(у°)

как М Обозначим

Будем считать, что каждое из множеств Мг{у*~1) и М*(у*-1) (г = 1,п) упорядочено по возрастанию.

Пусть М — некоторое конечное, упорядоченное по возрастанию множество точек из отрезка [0,1]. Пусть у € М. Пусть у' — точка, предшествующая точке увМ, если у —- не первая точка в М, и у/ = = 0, если у — первая точка в М. Обозначим

Пусть у" — следующая за у точка в М, если у — не последняя в М, и у" = 1, если у — последняя точка в М. Обозначим

Обозначим

где М — некоторое произвольное конечное, упорядоченное по возрастанию множество точек из отрезка [0,1],

для i = l,n — 1.

Скажем, что функция плотности вероятности р(х)у определяющая вероятностную меру Р, обладает свойством специальной ограниченно- сти с константой с для библиотеки V, если для любого г€{1,п-1}, любого у*"1 = (2/1,1/2»** »уГ1>уГ1) е Y'~l и любого у{ е выполняются следующие условия:

и

где у[ — левый конец отрезка Z^.(M*(y*-1)).

Очевидно, что с ^ 1.

Справедлива следующая теорема [30, 32].

Теорема 50. Пусть ЗИП I = (Xintn,V,pintn) — п-мерная задача интервального поиска, т.е. задача типа Sintn, где V = к, Т — базовое множество, определяемое соотношениями (4.37)-(4.43), п ^ 1, R(I) = ^2 Р{О(у, Pintп))- Тогда, если функция плотности yev

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

Доказательство. Одномерный случай, т.е. когда п = 1, доказывается теоремой 49.

Приведем доказательство теоремы 50 при п > 1.

В данном пункте мы воспользуемся для нашей библиотеки V = = {у 1,..., уь} понятиями и обозначениями, определенными в соотношениях (4.18)-(4.36).

Решать задачу будем методом снижения размерности. Покажем, как можно перейти от решения n-мерной задачи интервального поиска к решению (n — 1)-мерной задачи.

Пусть х = (ui,vi,..., ип, vn) ? Xintn произвольный запрос.

Сначала найдем такую пару (т/, у") из У1, что у' — ближайшая справа к щ точка из множества М1 (напомним, что М1 определяется соотношением (4.24) и является проекцией V на первую координату), а у" — ближайшая слева к v точка из Му,, определяемого соотношением (4.25). Если такой пары нет, то ответ на запрос х пуст, если же есть, то мы можем перейти к решению для запроса х! — — {и2, t>2, • • •, un,vn) для (п — 1)-мерной задачи интервального поиска в множестве ПУ2, ",Уп2 у1')), так как множество V2(y у"), определяемое соотношением (4.23), содержит все точки у = (j/i,..., уп)V такие, что ui ^ yi ^ v.

Таким способом мы за п — 1 шаг придем к одномерной задаче интервального поиска, решение которой мы описали ранее.

Опишем ИГ, который решает задачу I описанным выше методом.

Пусть у € М обозначим

для всех i = 2, п.

Рассмотрим следующую задачу поиска: для произвольного запроса х = (ui, Vi,...,tin, vn) ? Xintn найти в множестве М задаваемого соотношением (4.24), точку, ближайшую справа к точке щ. Эта задача (обозначим ее 71) соответствует первой задаче о близости, в которой в качестве библиотеки взято множество М в качестве множества запросов взята проекция множества Л”1 на ось tti, т. е. отрезок [0,1], а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности pl,1(ui), задаваемой соотношением (4.35) и являющейся ни чем иным, как функцией плотности вероятности координаты щ запросов, принадлежащих множеству X1.

Пусть т — параметр, определяющий мощность разбиения множества запросов. Если разбить множество запросов, т. е. отрезок [0,1], на т равных частей, как в примере 1 из пункта о поиске идентичных объектов, то вероятность каждой части будет не больше чем с/т, так как в силу специальной ограниченности plfl(ui) ^ с. То есть, мы находимся в условиях теоремы 19.

Поэтому построим ИГ С/^, решающий первую задачу о близости так, как было описано в доказательстве теоремы 19, где в качестве параметра т возьмем т =]с- |JW11[. Тогда

Заменим в графе U^ переключатель д^ на ш, а все переключатели вида на р} ^ ^, поскольку мы все же хотим, чтобы

решала задачу I1.

Возьмем произвольный лист а графа . Пусть ему соответствует точка у ? М

Мы попадем в лист а при всех запросах х = (ui,vi,...,un,t>n), у которых точка у — ближайшая справа в М1 к щ. Легко видеть, что это запросы из множества Xзадаваемого соотношением (4.44), т. е. У>а(аО = 1 для любого х ? Ху.

Теперь рассмотрим следующую задачу поиска: для произвольного запроса х = ,un,vn) ? Ху найти в множестве М*, задаваемом соотношением (4.25), точку, ближайшую слева к точке v. Эта задача (обозначим ее 7^) соответствует второй задаче о близости, в которой в качестве библиотеки взято множество A7J, в качестве множества запросов взята проекция множества Ху на ось i>i, т. е.

отрезок [у7, 1], где у7 — левый конец отрезка Z*1), задаваемого соотношением (4.26), а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности pj’2(vi), задаваемой соотношением (4.36) и являющейся не чем иным, как функцией плотности вероятности координаты v запросов, принадлежащих множеству Ху.

Так как в силу специальной ограниченности

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

Построим граф U^y, решающий задачу /*. Для этого сначала построим граф, решающий вторую задачу о близости для множества Му (отметим, что Му ф 0), где в качестве параметра га возьмем га = ]c-|M,J|[. Затем заменим в графе {У**у переключатель на у2., а все переключатели вида д<,У0 на у2 <>у/9, поскольку граф U^y должен решать задачу .

Легко видеть, что

и

Объявим а внутренней вершиной и уберем приписанную ей точку у. Отождествим корень графа С/*»у с вершиной а, т. е. граф (/^будет расти из а, причем а не будет полюсом полученного графа.

И, наконец, для каждого листа а' графа С/^у заменим приписанную листу а7 точку у' на пару (у,у7). Эту пару будем воспринимать как обозначение множества V'2(у, у7), заданного соотношением (4.23).

Проделаем такую операцию для каждого листа графа U}п.

Полученный граф обозначим U.

Он имеет не более к(к +1)/2 листьев, которым взаимно однозначно сопоставлены пары из У1. Этот граф позволяет для любого запроса х = jUnyVn) G X находить пару (у7, у77) G У1 такую, что

у7 — ближайшая справа к txi точка из М а у77 — ближайшая слева к Vi точка из Му,у если, конечно, такая пара существует, т. е. по сути позволяет находить множество точек V2(yy77) С V, которые удовлетворяют первой паре неравенств из (4.17).

Так как в графе только 1 активный путь, то

Опишем достаточно подробно и следующий шаг построения графа, решающего многомерную задачу интервального поиска, предполагая, что п ^ 3 (при п = 2 этот шаг не потребуется).

Рассмотрим произвольный лист а графа U1.

Пусть ему соответствует пара (у, z) € Y

Отметим, что V2(y, z) не пусто.

Теперь будем строить граф, который для множества V2(y,z) будет решать (п —1)-мерную задачу интервального поиска, и выпустим этот граф из вершины а.

Заметим, что только запросы из множества Х2(у, z), определяемого соотношением (4.45), попадают в вершину а, т. е.

Поэтому рассмотрим следующую задачу поиска: для произвольного запроса х = (ui, t/i,... ,un,vn) 6 Х2(у, z) найти в множестве М2(у, г)} являющегося проекцией множества V2(y, z) на вторую координату и задаваемого соотношением (4.24), точку, ближайшую справа к точке U2- Эта задача (обозначим ее J2(y, z)) соответствует первой задаче о близости, в которой в качестве библиотеки взято множество М2(у,-z), в качестве множества запросов взята проекция множества Х2(у, z) на ось U2, т. е. отрезок [ 0,1], а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности P*yZ)(ui), задаваемой соотношением (4.35) и являющейся не чем иным, как функцией плотности вероятности координаты t*2 запросов, принадлежащих множеству X2(yyz).

Так как в силу специальной ограниченности

то если разбить множество запросов на тп равных частей, вероятность каждой части будет не больше чем с/m. То есть мы можем воспользоваться алгоритмом, описанным в теореме 19.

Построим граф Um^v,z решающий задачу /2(у, z). Для этого сначала построим граф, решающий первую задачу о близости для множества M2(y,z) (отметим, что М2(у, z) ф 0), где в качестве параметра тп возьмем тп =]с • |М2(у, z)|[. Затем заменим в графе Um^y,z^ переключатель на У2,-,т> а все переключатели вида д^}У0 на У2,^>У/3»

поскольку граф Um^v,z^ должен решать задачу /2(у, z).

Легко видеть, что

И Т[иЪ'г)) < 2.

Возьмем произвольный лист о! графа

Пусть ему соответствует точка у' € М2(у, z).

Мы попадем в лист а' при всех запросах х = (ui,vi,... ,un,vn), у которых точка у' — ближайшая справа в М2(у, z) к ti2- Легко видеть, что это запросы из множества X2, (у, z), задаваемого соотношением (4.46), т. е.

Теперь рассмотрим следующую задачу поиска: для произвольного запроса х = , V,..., ип, vn) € X2, (у, z) найти в множестве М2, (у, z), задаваемом соотношением (4.25), точку, ближайшую слева к точке Vi- Эта задача (обозначим ее /2/(у, z)) соответствует второй задаче о близости, в которой в качестве библиотеки взято множество М2,(у, z), в качестве множества запросов взята проекция множества Л-2, (у, z) на ось V2, т. е. отрезок [у"', 1], где у"' — левый конец отрезка (М2(у, z)), задаваемого соотношением (4.26), а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности P2(yZ)y>(v2)» задаваемой соотношением (4.36) и являющейся не чем иным, как функцией плотности вероятности координаты t>2 запросов, принадлежащих множеству X2,(y,z).

Так как в силу специальной ограниченности

то если разбить множество запросов на m равных частей, вероятность каждой части будет не больше чем с/m. То есть, мы можем воспользоваться алгоритмом, описанным в теореме 19.

Построим граф {/т^У,2^’У, решающий задачу J2,(y, z). Для этого сначала построим граф, решающий вторую задачу о близости для множества M2,(y}z) (отметим, что M2,(y,z) ф 0), где в качестве параметра ш возьмем m = ]с • |М2/(у, z)| [. Затем заменим в графе {у2Ду.*).у ПСреключатсль д^ на У2,-,т> а все переключатели вида д<уУ0

на У2,<,у0> поскольку граф Um^y,z^y должен решать задачу I2,(y,z).

Легко видеть, что

Объявим а' внутренней вершиной и уберем приписанную ей точку у'

Теперь отождествим корень графа Um^y,z^,y с вершиной а/, т. е.

граф Urn'z^'y будет расти из а', причем а' не будет полюсом полученного графа.

И, наконец, для каждого листа а" графа Um^y'z^'y заменим приписанную листу а" точку у" на четверку (у, z, у у").

Проделаем такую операцию для каждого листа графа Um^y'z^

Полученный граф обозначим Uy X.

Объявим а внутренней вершиной, уберем приписанную ей пару } z) и отождествим а с корнем графа ?/22, т. е. граф U2Z будет расти из а.

Проделаем такую операцию для каждого листа графа U1.

Полученный граф обозначим U2.

Граф U2 имеет не более (к(к 4-1)/2)2 листьев, которым соответствуют четверки из множества У2, причем каждая четверка у2 = = (у}, 2/2> У? > 2/г) воспринимается как обозначение множества Vs2), определяемого соотношением (4.23).

Легко видеть, что T(U2) ^ 8 и

Далее из U2 аналогичным образом получим граф U3 и т. д.

На (п — 1)-м шаге мы получим граф Un~ который будет иметь не более (/:(/: + 1)/2)п-1 листьев, которым соответствуют вектора из множества У*”1. Этот граф позволяет для любого запроса

находить вектор у" 1 = (у}, у, -.. ,у" У? х) € Уп 1 такой, что у[ — ближайшая справа к щ точка из М*(у*_1), а у'2 — ближайшая слева к Vi точка из М(уг~1) (г = l,n — 1), если, конечно, такой вектор

существует. Если же такой вектор не существует, то ответ на запрос будет пуст, т. е. процесс поиска прервется, не доходя листьев. Если напомнить, что каждый вектор у*“п воспринимается как обозначение множества Vn(yn_1), то граф Un~l позволяет находить для любого запроса х подмножество точек множества V, которые удовлетворяют первым п — 1 парам неравенств из (4.17).

Легко видеть, что

Теперь осталось сделать последний шаг.

Пусть Л — множество листьев графа Un-.

Рассмотрим произвольный лист а 6 Л.

Пусть ему приписан вектор у%~1 = (у,у^ •••, уГ”1 > У? ~1)> который является обозначением множества Рп(у2-1)- Построим для проекции этого множества на последнюю координату уп граф Ua, решающий одномерную задачу интервального поиска, которую обозначим IQ. Поскольку в вершину а попадают только запросы из множества Ха = -^п(у?-1), определяемого соотношением (4.45), то функция плотности вероятности для задачи 1а будет иметь вид p”n_i (un, t>n),

У а

описанный в соотношении (4.34), и эта функция в силу специальной ограниченности не больше чем с. Граф UQ построим по методу, описанному в предыдущем пункте. Тогда согласно доказанному

Здесь Ра — вероятностная мера на XQ) задаваемая функцией плотности вероятности _, (un, vn).

У а

Так как для любого уМп(у2~1) величина Ра{0(у, pint)) равна условной вероятности события 0(у,р»п«п) при условии события Ха, где у — такая запись из Vn(y%~1), что ее последняя координата равна у, то

Возможность расширения области суммирования связана с тем, что для любой записи у ? V Vn(y”~1) вероятность

Объявим теперь лист а внутренней вершиной, уберем приписанный ему вектор и прикрепим к нему граф Ua.

Проделаем эту операцию для каждого листа графа Un- и полученный граф обозначим Un.

Так как в графе Un- не более + 1)/2)п-1 листьев, то

Легко видеть, что полученный граф Un разрешает задачу /, так как для любого запроса х = (щ, V|,..., ипу vn) с помощью графа Un~x мы находим подмножество точек множества V, которые удовлетворяют первым п — 1 парам неравенств из (4.17), а с помощью графа, растущего из вершины подграфа ?/п-1, соответствующей этому подмножеству, мы выберем из этого подмножества точки, удовлетворяющие и последней паре неравенств из (4.17).

Для того чтобы подсчитать сложность графа С/п, заметим, что для любых а, а' Е Л таких, что а ф а', справедливо

и

Заметим также, что для любого запроса х существует только один активный путь, ведущий к концевым вершинам подграфа C/n_1. Это означает, что для любого запроса х будет активен только один из подграфов Uay и, значит,

И, наконец, поскольку, согласно теореме 4, Т(1,Т) ^ #(/), то теорема полностью доказана.

Заметим, что для двумерной задачи предлагаемый в теореме 50 метод требует затраты по памяти, равных Q(k3), так же как и метод прямого доступа. По сути предлагаемый алгоритм и является модификацией метода прямого доступа, использующей умение очень быстро решать задачи о близости. Таким же образом можно модифицировать другие методы решения задачи интервального поиска, в частности, многоэтапный метод прямого доступа Бентли и Маурера [116], и тем самым снизить затраты памяти.

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