Фоновый алгоритм решения двумерной задачи о доминировании

В качестве примера использования введенной выше модели приведем исследование быстрого фонового алгоритма двумерной задачи о доминировании, т. е. ЗИП типа 5^от> в случае, когда п = 2. Полученный для этой задачи алгоритм для большинства библиотек будет давать среднюю временную сложность, отличающуюся от среднего времени перечисления ответа на константу, и требовать линейных затрат по памяти. Отметим, что обычный, не фоновый, алгоритм с аналогичной временной сложностью требует квадратичных затрат по памяти.

Пусть т — некоторое натуральное число и.

Отметим, что если — переключатель, определяемый соотношением (3.15), то Пусть.

— базовое множество, где Gi, G2, i⁷! определяются соотношениями (3.15)—(3.17) при п = 2.

Пусть на Xdom задано вероятностное пространство (Xdom-> <�т, Р) и вероятностная мера Р определяется функцией плотности вероятности р (х, у) такой, что р (х, у) ^ с.

В данном разделе предлагается некий алгоритм Л построения информационных графов, который по заданной двумерной задаче о доминировании / = (Xdom, Vi Pdom) строит информационный граф .4.(7), разрешающий задачу 7. Опишем этот алгоритм.

Мы будем решать задачу о доминировании путем последовательного решения нескольких задач о близости (ЗоБ) из раздела 2.3, которые допускают мгновенное в среднем решение.

Для этого разобьем библиотеку V на слои V,…, V/ следующим образом:

Здесь число / — это первый момент, когда Vi U • • • U V = V Неформально множества Vможно описать так. Слой Vi есть множество минимальных точек множества V. Слой V2 есть множество минимальных точек множества V Vi, и т. д. Понятно, что все точки в одном слое несравнимы.

Очевидно, к -f * • • + ki = к и VJ П Vj = 0, если i ф j.

Будем считать, что точки в каждом слое V* (i = 1,1) упорядочены в порядке возрастания первой координаты, т. е.

а это, как нетрудно видеть, означает, что.

Поэтому можно считать, что для каждого слоя задано отношение линейного порядка, основанное на сравнении первых координат. Наличие этого отношения позволяет нам опираться на вторую ЗоБ. Обозначим

Очевидно, р (х) ^ с.

Также легко заметить, что Р (А™ х [0,1]) ^ ^ для любого т из N и любого г 6 {1,т}.

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

Построим теперь граф U = А (1), разрешающий двумерную задачу о доминировании I.

Возьмем вершину /Зо и объявим ее корнем графа U. Выпустим из Ро граф U аналогичный графу U^ из раздела 2.3 и разрешающий вторую задачу о близости по первой координате для Vi, используя переключатели из множеств G и G2, причем в качестве параметра т возьмем Hi = ]c|Vi|[ = ]cA:i[.

Пусть — листья графа U¹. Им приписаны записи у}¹" • • • Объявим эти вершины обычными внутренними вершинами графа U и уберем приписанные им записи. Выпустим из них по одному ребру и припишем этим ребрам предикаты где * =.

= а концы этих ребер объявим листьями графа U. Назовем их.

an,…, aiki и припишем им записи у¹¹,…, у¹*¹.

Теперь из каждого листа аи (г = 2, к) выпустим ребро, ведущее в лист и припишем ему номер 1.

Возьмем новую точку $, из каждого листа (г = 2, к), проведем в нее ребро и припишем ему номер 2.

Объявим листья ан (t = 2, к) точками переключения и припишем им переключатели д_{2 > у}м-1. А из листа ап проведем ребро в вершину и припишем ему предикат f

Этот построенный граф между вершинами 0о и 0 обозначим U¹.

Теперь из вершины 0 выпустим граф (7², аналогичный уже построенному графу U но для множества и проведем для него все предыдущие построения. Эту процедуру мы проведем / — 1 раз и получим / - 1 последовательно соединенный граф О¹ (г = 1, / — 1).

На 1-м шаге берем точку ft_i и выпускаем из нее граф U¹ как и на предыдущих шагах. Пусть ,…, а®_Л| — листья графа U. Им приписаны записи у}¹,…, yj*'. Объявим эти вершины обычными внутренними вершинами графа U и уберем приписанные им записи. Выпустим из этих вершин по одному ребру и припишем этим ребрам предикаты /2,^,_у" (* = 1, а концы этих ребер объявим листьями графа U. Назовем их ап,…, а/*, и припишем им записи г/¹,… , y^lkl.

Теперь из каждого листа ац (г = 2, &/) выпустим ребро, ведущее в лист a^i-i, и припишем ему предикат /₂ > (г = 2, &/).

Этот последний граф с корнем в вершине 0i- обозначим U¹.

Таким образом, мы получили граф А{1) с к листьями над базовым множеством Т.

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

Пусть нам дано множество V = {у …, у^п}, в котором мы должны производить поиск. Сначала разобьем его на слои, в которых можно задать отношение линейного порядка и слои упорядочим по возрастанию в том смысле, что если для некоторого запроса х € Xd_om существует у € Vji х pdom У и j > 1, то для любого г € {l₉j — 1} существует у' 6 Vii х pdom У'• Теперь поиск по произвольно взятому запросу х = производится следующим образом.

По очереди для каждого слоя Vj будем находить такую запись у = = (уьУг), что уi — ближайшее слева к х. Затем проверим условие У2 ^ хг и в случае успеха выдадим у в ответ. Тогда, просматривая справа налево, начиная с у, записи y^s из данного слоя, будем проверять условие у| ^ Х2 и выдавать запись в ответ. После первого невыполнения этого условия переходим к следующему слою.

Эту процедуру будем повторять до тех пор, пока ответ для очередного слоя не окажется пуст или если будут просмотрены все слои. Тогда прекратим работу.

Оценим сложность этого алгоритма.

Поскольку на каждом слое точки упорядочены по первой координате, то для поиска такой записи у = (уьуг) в слое, что у — ближайшее слева к х можно использовать мгновенное решение задачи о близости, которое обеспечит в среднем время не больше 2 при линейных затратах памяти. Далее пока в слое имеются точки, удовлетворяющие запросу, ответ на запрос пополняется с каждым тактом. На следующем слое ситуация повторяется. Таким образом, если время обработки пользователем элемента ответа больше 2, то фоновая сложность данного алгоритма не больше 2, т. е. равна среднему времени ожидания первого элемента ответа. К сожалению, это только правдоподобные рассуждения, и существуют такие библиотеки, для которых это утверждение не справедливо, что подтверждается следующими теоремами.

Теорема 41. Пусть I = (XdomjV, Pdom) — двумерная задача о доминировании, где V = А; и все точки в множестве V различны, Т — базовое множество, определяемое соотношениями (3.15)—(3.17), (3.23)-(3.26). Пусть на Xdom задано вероятностное пространство (Xdomi&)P), ^ вероятностная мера Р определяется функцией плотности вероятности р (х, у) такой, что р (х, у) ^ с. Тогда, если время обработки пользователем любой записи из ответа не меньше чем т ^ 3, то

Доказательство. Покажем, что граф U = А (1), описанный выше, разрешает двумерную задачу о доминировании. Для этого докажем, что для любой записи у^г G V

где — лист, которому приписана запись у

Граф С/-⁷ построен таким образом, что если у* € Vj, то для любого.

справедливо у} ^ Х. Так как в каждый лист ведет либо предикатное ребро с приписанным предикатом либо переключательное ребро с тем же условием, то.

Осталось показать, что для любой записи у¹ Е V

то есть, для любого запроса х = (Х, Х2) G 0(уPdom) справедливо ?>аДя) = 1, или, иными словами, для любого запроса х, такого, что хPdom J/ существует проводящая на запросе х цепь из корня в лист а".

Доказательство проведем индукцией по числу задействованных слоев.

Базис индукции. Пусть у^г G V, т. е. существует такой номер s, что у' = у^ь.

Пусть у³ — ответ графа U решающего вторую ЗоБ, на запросе х. Следовательно, существует проводящая ориентированная цепь, ведущая из корня в вершину и у>_ао (х) = 1.

Так как Х2 ^ у₂³ ^ У₂³ > ^то Jг ^ (^х) = 1 ^и для любого ?: s < j' <

< j справедливо Х > у³ и х₂ ^ у^а ^ у'^{3 -1} ^ у³ Откуда следует, что значение переключателя д ' ij'-i, приписанного вершине на запросе х равно 1. Следовательно, проводимость цепи, ведущей от.

< до Qj, равна 1 и y?_ai(x) = 1;

Шаг индукции. Пусть теперь у' € Vj, где j > 1, т. е. существует такой номер s, что у¹ = Покажем, что.

В (J — 1)-м слое существует такая запись ^1,5, что y*^s pdom У^{3 1,3} иначе у¹ принадлежала бы слою Vj-.

По предположению индукции существует ориентированная цепь, ведущая в i_j3, проводимость которой на запросе х равна 1. Покажем, что f_aj__{х 9}t>ctj_e(z) = 1. Здесь и далее f_ap — функция проводимости из вершины, а в вершину /3.

Так как все вершины I' = 2, fcj, переключательные и из них ребра ведут либо в либо в fij-u а из вершины ведет ребро в /%-!, то = 1.

Pj-1 — корень графа U решающего вторую ЗоБ, и у{^к — ответ этого графа на запросе х. Тогда существует ориентированная цепь, ведущая в вершину а®*/, проводимость которой равна 1.

Так как х₂ ^ у³₂ ^ yif и для любого n! s < п' < к' справедливо xi > у{^п и х₂ ^ у³₂^а ^ у³₂'^{п _1} ^ у₂^п, то g j_fi/_i (x) = 1. Следовательно, проводимость цепи, ведущей от оР-_к, до acj_s, равна 1 и.

Учитывая произвольность у мы получим, что граф U решает задачу I = (X_dom, V, p_dom)•.

Оценим сложность графа U = Л (/). Для этого введем вспомогательную функцию /(/), которая определена на No = N U {0}.

где R = т — 3, и оценим сложности каждого из графов U' (i = 1,/).

Согласно теореме 19 из раздела 2.3, T (U^l) ^ 2. Поскольку для любого запроса в графе U¹ делается по сравнению с графом U¹ не более чем одно лишнее вычисление (сравнение по второй координате), то Тф (и^г) ^ 3.

Рассмотрим произвольный граф U¹ (г = 2,/).

Обозначим

где ТП{ = ]cfcj[, А™* определяется соотношением (3.22). Понятно, что.

rrij.

Е hi = ^ki-

J=1.

Рассмотрим произвольный запрос х. Ясно, что если х? Х то Тф (Цх) = 0. Пусть х € для некоторого j € {1,т*}. Тогда проводимость корня графа U* равна 1 на запросе х. Пусть и — запас времени, имеющийся при приходе запроса х в корень графа U в течении которого пользователь будет обрабатывать записи, полученные на предыдущих шагах. Понятно, что и ^ т — 1, так как мы попадаем в корень графа U* из некоторого листа после вычисления одного переключателя или предиката. Далее после попадания запроса х в корень графа II^х до момента попадания в некоторый лист пройдет 2 + log₂{lij + 1) тактов времени, после чего мы либо определяем, что записей в ответе больше нет, либо включаем новую запись в ответ. Таким образом, если 2 + log₂(hj + 1) < tx, то Тф (Цх) = 0, а иначе T^(Ux) = 2 + log₂(/jj + 1) — и. Следовательно,.

откуда.

тп, Оценим теперь сверху? /(*"?)• Обозначим.

;=i.

Покажем, что при t • 2 ^я ^ к < (? + 1)-2^я справедливо: Доказательство проведем индукцией по t.

Базис индукции. Если t = 0, то к < 2^я и утверждение выполнено. Шаг индукции. Пусть утверждение справедливо при всех I ^ t. Проверим его для / = t + 1.

т

Пусть k = li, причем будем считать, что числа U упорядочены «=1.

по возрастанию, т. е. /1 ^ h ^ ^ /т;

Если li < 2^я, то для любого i = l, m имеем U < 2^я и г (к, т) = 0. Если s • 2^я ^ li < (s -f 1)2^Я, где s ^ 1 — целое, то.

Тогда Следовательно,

Утверждение индукции доказано.

Так как, если к ^ t ? 2^я, то t <^, следовательно, Значит,.

причем, если к{ < 2^я, то Тф (С/*) = 0. Таким образом,.

где I' — число слоев, не считая первого, у которых ki ^ 2^я Отсюда, поскольку I' ^ (к — 1)/2^я, получаем.

Осталось подсчитать объем графа U.

Поскольку, как было показано в теореме 19 из раздела 2.3, объем каждого из графов U* (j = 1,1)

где rij — количество листьев графа С/-⁷, то.

Поскольку помимо ребер графов U³ (j = 1,/) с каждым листом связано не более трех ребер, то

Тем самым, теорема 41 доказана.

Результат этой теоремы есть по сути перестраховка на самый худший случай, т. е. на такую библиотеку, что при выходе на каждый очередной слой мы будем иметь минимальный запас времени, но при этом на каждом слое имеется нужное количество записей. Следующий результат говорит, что этот самый плохой случай в принципе почти реализуем. Этот результат так же, как и предыдущий относится к алгоритму построения информационных графов А, описанному выше.

Теорема 42. Пусть вероятностная мера Р на Х^от определяется функцией плотности вероятности р (х, у) такой, что р (х, у) ^ с. Пусть время обработки пользователем любой записи из ответа не больше чем t и т = max (i, 3). Тогда существует такая двумерная задача о доминировании I = (Х^_от, V, pdom), что для графа Л (1), построенного по алгоритму, А для ЗИП I, справедливо

^{где 01 =} З3' ^{k =} l^Vl;

Доказательство. Пусть.

Выберем такое X™ = А™ х [0,1] (j? {1,ш}), что Р (Х™) ^ 1/т. Понятно, что такое X™ существует.

/41.

Рассмотрим библиотеку V — [J Vi, где V* — различные слои,.

«=1.

причем |Vi| = 1, |Vi| = г при i 6 {2,1 + 1} и, если I <1 то |V//+i| = к — — 1 — l • г, кроме того, если обозначить.

то выполнены следующие условия:

и если I < то

где е и 6 малые величины, которые мы уточним в дальнейшем.

Понятно, что библиотеку, удовлетворяющую этим условиям, можно подобрать.

Обозначим.

Нетрудно заметить, что

и что для любого i € 1,/' + 1 выполняется X* Э X'.

Отсюда, если взять е < ^ и 6 < то.

где d > 1/3 — константа.

Возьмем произвольный запрос х G X'.

Легко видеть, что JU (/)(^X) ⁼ {у¹*^: * = 1,/ + 1}. Отсюда сразу следует, что для любого г € {2, / -4−1} запас времени, имеющийся при приходе запроса х в корень графа U в течении которого пользователь будет обрабатывать записи, полученные на предыдущих шагах, будет равен и ^ т — 1, и, следовательно, Тф (их) ^ 1.

Отсюда следует, что.

где ci — некоторая константа.

Тем самым теорема 42 доказана.

На первый взгляд результаты теорем 41 и 42 говорят не в пользу описанного алгоритма, но надо понимать, что эти результаты получаются на очень невероятных специальных библиотеках и есть все основания полагать, что для обычных массовых библиотек данный алгоритм будет давать хороший результат, а именно в среднем время ожидания будет равно константе, и это при линейных затратах на память.

В пользу этого говорят следующие рассуждения. Как было показано в предыдущих теоремах, плохой для алгоритма является такая библиотека, в которой на слое большинству запросов, удовлетворяет одна запись. Понятно, что в типичном случае это свойство не может выполняться, и, значит, в большинстве слоев будет по несколько записей, удовлетворяющих запросам. Но каждая дополнительная подходящая запись в слое дает ощутимый запас времени, который можно использовать на следующих слоях, причем, чтобы этот запас исчерпать надо, чтобы следующий слой большей частью попал в один отрезок и мощность этой части должна быть экспоненциальна от величины запаса, или же надо, чтобы на большом количестве следующих слоев запас не накапливался.

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

Итак, справедлива следующая лемма.

Лемма 46. Пусть библиотека V* получается как выборка к независимых одинаково равномерно распределенных па квадрате [0,1] х х [0,1] случайных величин. Пусть S? — есть математическое ожидание числа записей в первом слое библиотеки Vk. Тогда

и при к —> оо

Доказательство. Найдем среднее количество точек в первом слое. Отметим, что разбиение библиотеки на слои не зависит от положения записей на квадрате, а зависит только от их взаимного расположения, причем, можно предположить, что все точки из библиотеки имеют различные абсциссы и ординаты, т. е.у[фу{ при i ф j и у ф у при х ф j. Так как, если две точки имеют одинаковую координату, то они принадлежат разным слоям, то мы можем, не нарушая взаимного расположения точек из библиотеки, немного сместить одну из этих двух точек и добиться того, что обе координаты будут разными.

Рассмотрим некую библиотеку.

Будем считать, что все точки библиотеки занумерованы в порядке возрастания ординат, т. е. у < у < • • • < у2 •.

Найдем рекуррентное соотношение для величины S.

Запись (2/1,У2) попадет в первый слой, если для любого номера j G {l, fc — 1} справедливо у > у*, т. е. эта точка имеет наименьшую абсциссу. Это может произойти с вероятностью и если эту точку отбросить, то останется библиотека мощности (& —1) и для нее среднее количество точек в первом слое есть величина Sj_c_₁. Если же найдется j такое, что у{ < yf, то эта запись не попадет в первый слой, а это произойдет с вероятностью *, и достаточно рассмотреть величину 5?__г Таким образом, получим соотношение Тогда

Остается заметить, что при к —> оо,.

Тем самым, лемма доказана.

Эта лемма косвенно еще раз подтверждает «хорошесть» описанного фонового алгоритма решения двумерной задачи о доминировании. В самом деле, тот факт, что в первом слое в среднем In к точек, с учетом того что первый слой самый нижний, приводит к тому, что для большинства запросов в первом слое будет содержаться порядка In к точек, удовлетворяющих запросу, и, следовательно, чтобы исчерпать запас времени, образующийся на первом слое, мы должны в следующем слое иметь порядка к точек или в последующих порядка In к слоях этот запас неуклонно исчерпывать за счет специфики расположения точек (например, как в теореме 42). Понятно, что ни та, ни другая ситуация не типичны. Хотя первая из ситуаций «хороша» для алгоритма, поскольку сразу приводит к константному в среднем времени ожидания. О тех же запросах, которые будут содержать в первом слое мало точек, удовлетворяющих этому запросу, можно сказать, что в типичной ситуации эти запросы будут «зацеплять» малое число слоев, и, следовательно, иметь малое среднее время ожидания.