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

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

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

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

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

(til,"1 pintП (У1,—-, Уп).

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

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

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

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

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

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

Обозначим.

Обозначим.

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

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

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

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

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

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

Обозначим.

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

для i = l, n — 1.

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

и

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

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

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

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

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

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

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

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

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

Пусть х = (ui, vi,…, и_п, v_n)? X_intn — произвольный запрос.

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

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

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

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

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

Рассмотрим следующую задачу поиска: для произвольного запроса х = (ui, Vi,…, ti_n, v_n)? Xi_nt_n найти в множестве М задаваемого соотношением (4.24), точку, ближайшую справа к точке щ. Эта задача (обозначим ее 7¹) соответствует первой задаче о близости, в которой в качестве библиотеки взято множество М в качестве множества запросов взята проекция множества Л"¹ на ось tti, т. е. отрезок [0,1], а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности p^l,1(ui), задаваемой соотношением (4.35) и являющейся ни чем иным, как функцией плотности вероятности координаты щ запросов, принадлежащих множеству X¹.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Он имеет не более к (к +1)/2 листьев, которым взаимно однозначно сопоставлены пары из У¹. Этот граф позволяет для любого запроса х = jUnyVn) G X находить пару (у⁷, у⁷⁷) G У¹ такую, что у⁷ — ближайшая справа к txi точка из М а у⁷⁷ — ближайшая слева к Vi точка из Му, у если, конечно, такая пара существует, т. е. по сути позволяет находить множество точек V²(yy⁷⁷) С V, которые удовлетворяют первой паре неравенств из (4.17).

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

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

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

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

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

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

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

Поэтому рассмотрим следующую задачу поиска: для произвольного запроса х = (ui, t/i,… , u_n, v_n) 6 Х²(у, z) найти в множестве М²(у, г)_} являющегося проекцией множества V²(y, z) на вторую координату и задаваемого соотношением (4.24), точку, ближайшую справа к точке U2- Эта задача (обозначим ее J²(y, z)) соответствует первой задаче о близости, в которой в качестве библиотеки взято множество М²(у,-z), в качестве множества запросов взята проекция множества Х²(у, z) на ось U2, т. е. отрезок [ 0,1], а вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности P*y_Z)(ui), задаваемой соотношением (4.35) и являющейся не чем иным, как функцией плотности вероятности координаты t*2 запросов, принадлежащих множеству X²(y_yz).

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

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

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

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

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

И Т[иЪ^{у'^г)) < 2.

Возьмем произвольный лист о! графа Пусть ему соответствует точка у' € М²(у, z).

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

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

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

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

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

на У2, поскольку граф Um^^{y, z}^^y должен решать задачу I²,(y, z).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

находить вектор у" ¹ = (у}, у, -., у" У? ^х) € У^п 1 такой, что у[ — ближайшая справа к щ точка из М*(у*^_1), а у'₂ — ближайшая слева к Vi точка из М (у^г~¹) (г = l, n — 1), если, конечно, такой вектор существует. Если же такой вектор не существует, то ответ на запрос будет пуст, т. е. процесс поиска прервется, не доходя листьев. Если напомнить, что каждый вектор у*"^п воспринимается как обозначение множества Vⁿ(y^n₁), то граф Uⁿ~^l позволяет находить для любого запроса х подмножество точек множества V, которые удовлетворяют первым п — 1 парам неравенств из (4.17).

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

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

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

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

Пусть ему приписан вектор у%~¹ = (у, у^ •••, уГ"¹ > У? ~¹)> который является обозначением множества Р^п(у2^-1) — Построим для проекции этого множества на последнюю координату у_п граф U_a, решающий одномерную задачу интервального поиска, которую обозначим I_Q. Поскольку в вершину, а попадают только запросы из множества Х_а = -^^п(у?^-1), определяемого соотношением (4.45), то функция плотности вероятности для задачи 1_а будет иметь вид p"_n_i (u_n, t>_n),.

У а

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

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

У а

Так как для любого у € М^п(у2~¹) величина Р_а{0(у, pint)) равна условной вероятности события 0(у, р"_п«п) при условии события Х_а, где у — такая запись из Vⁿ(y%~¹), что ее последняя координата равна у, то.

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

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

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

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

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

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

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

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

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