Построение информационного графа

Прежде, чем приступить к построению ИГ над базовым множеством Ту решающего двумерную задачу интервального поиска описанным выше методом, введем вспомогательные блоки, из которых и будем впоследствии строить ИГ.

Пусть [6, d С [0,1) — произвольный интервал.

Пусть Z = {zi,…, zi} — упорядоченное множество действительных чисел из интервала [6, d. Через обозначим ИГ с одной входной вершиной (корнем) и (/ + 1) выходными вершинами (листьями, которые занумерованы слева направо числами 1,…,/ + 1) такой, что функция проводимости между корнем и г-м (г = 1,…,/ + 1) листом имеет вид:

где zq = Ь, Z|+1 = d.

Бели считать, что г-му листу (г = 1 + 1) соответствует точка Zi, то информационный граф U _{b d} позволяет находить точку из множества {zi,…, z/, zj+i = d}, ближайшую справа к U.

ИГ Ud строится по методу, описанному в разделе 2.3.2, с помощью функций из G1 U G3.

Вероятностная мера вероятностного пространства над множеством запросов Ui € [6, d] при условии, что b ^ е ^ v ^ / < 1, в рассмотренной задаче о близости определяется функцией плотности вероятности, задаваемой соотношением (4.62). Поскольку справедливо (4.65), то мы находимся в условиях теоремы 19. Следовательно, если выбрать в качестве параметра алгоритма т = ]с • /[, то выполняется.

для любого х € [6, d).

Пусть Z — {zi,…, z/} — упорядоченное множество действительных чисел из интервала [е, /). Через ?/| _ej обозначим ИГ с одной входной вершиной (корнем) и (/ + 1) выходными вершинами (листьями, которые занумерованы слева направо числами 1,… _yl + 1) такой, что функция проводимости между корнем и i-м (г = 1,…,/ + 1) листом имеет вид:

где zo = 6, zi+1 = е.

Если считать, что t-му листу (г = 1,…,/ + 1) соответствует точка Zi-_h то Uz_ej позволяет находить точку из множества {6 = = zo, z₉…, zi}, ближайшую слева к vi.

ИГ Uz_te, f ^стР^оится аналогично ИГ U^j с помощью функций из С?2 U С74.

Вероятностная мера вероятностного пространства над множеством запросов v € [е,/] при условии, что 0⁶^ и ^ d < 1 и 6 ^ е, в рассмотренной задаче о близости определяется функцией плотности вероятности, задаваемой соотношением (4.63). Поскольку справедливо (4.66), то мы находимся в условиях теоремы 19. Поэтому при т = ]с • /[ выполняется.

для любого х 6 [е, /].

Пусть Z = {zi, Z2,…, z/} — упорядоченное множество действительных чисел из интервала [0,1). Через U обозначим ИГ с одной входной вершиной (корнем) и I выходными вершинами такой, что функция проводимости между корнем и листом с номером i (г = = имеет вид:

Если считать, что г-му листу, г = 1,…, /, соответствует точка z, то U позволяет находить все точки из Z, принадлежащие отрезку ИГ U разрешает одномерную задачу интервального поиска для библиотеки V — Z и множества запросов X = X_int. ИГ U будем строить по методу, описанному в разделе 4.1.5, с помощью функций из G$ U (7б, -Рг;

Если для некоторых 6, с?, е, / G [0,1) таких, что b < d ^ е < / выполняется 6 ^ и ^ d и е ^ ui ^ /, то вероятностная мера вероятностного пространства над множеством запросов определяется функцией плотности вероятности, задаваемой соотношением (4.61). Поскольку выполняется (4.64), то мы находимся в условиях теоремы 49. Следовательно если в качестве параметра алгоритма выбрать т = 2c[log₂ /], то справедливо.

где Р' определяется функцией плотности вероятности (4.61), и для любого х G Xi_nt выполняется.

Приступим к построению информационного графа t/*, решающего двумерную задачу интервального поиска методом, описанным в предыдущем разделе.

Сначала построим ИГ U_q) q = 1,…, М.

Все полюсы графа U_qi q = 1 разделяются на несколько типов.

1. При Цд<�Мв графе U_q есть полюсы j = 2,…, k^ai+'" ^а% на которых реализуются функции.

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

2. При 1 ^ q ^ М в U_q есть полюсы /3?, j = 1,…, fc^ai+•••+"" _f на которых реализуются функции.

При q < М из вершин /?? в дальнейшем будут выпускаться ИГ, находящие в множестве a/j⁺¹ точку, ближайшую слева к V, а при q — М в этих вершинах будет выполняться проверка принадлежности отрезку [½, 172] ординаты точки библиотеки V с абсциссой lj.

3. При 1 ^ q < М в U_q есть полюсы 7?, j = 2,…, fc^ai+ -+^a9 + 1. На них реализуются функции.

Из вершин 7? будут выпускаться ИГ, которые находят ближайшую справа к uj, и ближайшую слева к v точки при условии,.

4. При 1 ^ q ^ М в U_q есть полюсы 5 = 1,…, &^ai+" ^+a«-*¹, i = 2,…, — 1, j = г +1,…,. При q = 1 индексы меняются как 5 = 1, г = 1,…, /:^ai — 1, j = * + &^ai. На них реализуются.

Из вершин JJ. будут выпускаться ИГ, решающие одномерную задачу интервального поиска для ординат тех точек из библиотеки V, абсциссы которых принадлежат интервалу №(s-l)k^ai+i>l (s-l)k^a4+j) —

5. При 1 < q $ М в U_q есть полюсы 77^, % = 2,…, fc^e,+*" ^+ог««¹,, 7 = 1,…, к^а<* — 1, на которых реализуются функции.

Из вершин rfi. будут в дальнейшем выпускаться ИГ, решающие одномерную задачу интервального поиска для ординат тех точек библиотеки V, абсциссы которых принадлежат интервалу P (t-2)*^e*+i+i>^i)*.

6. При 1 < q ^ М в U_q есть полюсы, t = 1,…, fc^a|+‘'^+а««^|, 7 = 2,…, A:^a», на которых реализуются функции.

Из вершин ??• будут в дальнейшем выпускаться ИГ, решающие одномерную задачу интервального поиска для ординат тех точек библиотеки V, абсциссы которых принадлежат интервалу Vi

Строить U_q, q = 1,…, М, будем индуктивно по <7.

Базис индукции. Пусть <7=1.

Возьмем ИГ ₀₁. Он имеет (к^ах +1) концевых вершин. Обозначим их 0i,…, 0*"₁₊₁.

Если М > 1, то вершину 0^ 1+1 переобозначим в 7* ^так как мы попадаем в нее только в том случае, когда.

Если М = 1, то пометим ее символом Выход к вершине, помеченной символом будет означать, что ответ на запрос х = = (ui, vi, U2, V2) пуст. Эта пометка делается только для наглядности описания, на функционирование ИГ она не влияет.

Из каждой вершины 0*, i = 1,…, к^а выпустим два ребра, левому припишем 1, правому — 2, а самой вершине 0* припишем переключатель gfi (х) € G⁴; конец левого ребра обозначим 0, конец правого —.

9". В в мы попадаем только в том случае, когда.

а в 6"  — когда 1}__х < и ^ i_t-, v ^ I]. Поэтому если М > 1, то мы можем переобозначить все 0', в 7/, а 0" — в, г = 2,…, к^ах. Вершину 0| пометим символом Если М = 1, то все 0J, г = 1,…, к^ах, пометим символом Каждую вершину в", г = 1,…, k^ai —1, (включая переобозначенные в 0J) отождествим с корнем ИГ U^_lti ^ _v где.

Информационный граф _lti ц j имеет (k^ai — i + 1) концевых вершин, которые обозначим 0_tJ, i = 1,…, к^а% — 1, j = г,…, k^ai. Понятно, что в вершины 9{j мы проходим только в том случае, когда.

Следовательно, можно переобозначить вершины 9{j, i = 1,…, k^ai — 1, j = г + 1,…, k^ai, в .

Введем новые вершины /3j, j = 1,…, k^ai, и из каждой вц (включая переобозначенные в г = 1 проведем ребро в вершину flj, которому припишем предикат, тождественно равный 1. Очевидно, что.

т.е. ^A(x).

Построенный граф обозначим U. Он изображен на рис. 4.4 для случая М > 1.

Индуктивный переход. Пусть построен ИГ U_q-. Будем строить U_q, достраивая U_q- следующим образом.

Из каждой вершины, г = 2,…, k°^l+•+^a9-i_j выпустим информационный граф U_r4 ,_i _q~_x. Этот граф имеет листьев, которые обозначим •, j = 1,…, Аг^а".

В вершину r'_qij мы попадаем только в том случае, когда.

Рис. 4.4. Информационный граф Ui, М > 1.

поскольку Л/'Д_₁ = (/"-«,/Г¹) = (^_2)*»,+1. ^i-Dfco.+i) — Получаем, что vv. = fij⁴{x) — Следовательно, можно переобозначить с индексами г = 2,…, fc^ai+" '^+a«-¹ = - 1, в ту^.

Из каждой вершины 0*, г = 1,…,&^ai+ выпустим информационный граф U* Этот граф имеет к*** листьев, которые.

?^Л'*" «*"+1.

обозначим Tqtj, 7 = В вершину т''^ мы попадаем только в том случае, когда.

Таким образом, у?_т'^ = fij⁴(x)• Следовательно, можно переобозначить т" — с индексами г = 1,…, fc<*i+—+^e«-i _э j — 2,…, в Л.

Рассмотрим вершины 7?" г = 2,…, fc^ai+" ^,+^a«-¹ + 1. Из каждой такой вершины выпустим информационный граф U_fq ,_i ,_j. Этот.

«‘i-l «*<

граф имеет /г⁰'* листьев. Обозначим их Qqiji j — 1,. Проводимость в эти вершины будет равна.

Из каждой вершины 9_qij, г = 2,…, fc^e«+—+*"-1 + 1,^ = 1,…, — 1,.

выпустим два ребра, левому припишем 1, правому — 2, а самой O_qij припишем переключатель д% (х). Конец левого ребра, выходящего из Q_qij, обозначим 9_qij, конец правого — 0″ -^. Псреобозначим все, г = 2, —, fc*i±+a,_i +1, через 9'_qik*_q.

Если q < М, то переобозначим все 0^_;-, г = 2,…, &<*!+? *+^а«-» 4- 1, j = l,…,/:" ⁴, через 7^_₂)*°"+>+1> так как в 0^ мы можем попасть только в том случае, когда ^__2)fc*,_+i < щ ^ vi < ^__2)lb",_+i+i, то есть, _Wqii = f™2_)k°'+j+i (z) —

При изменении г от 2 до fc°i+" +^a«-i 4−1, j от 1 до А:^а», (г — 2) А:^а" 4- 4- j 4- 1 изменяется от 2 до fc^ai+" ^,+ak^ai+'" +^ая + 1.

Если q = М, то все 0'^-, г = 2,…, fc^a«+—+^a9-i 4- 1, j = 1,…, fc^a,?, пометим символом В вершины 0_qij мы попадаем при условии, что.

Из каждой вершины 9_qij, г=2,…, k^ai+-+"" —ⁱ4-i_j j=l,…, fc^a«-2, выпустим ИГ t/L.,, где.

—2)fc°9 +i+l '**.

Этот информационный граф имеет — j) листьев, которые обозначим tf_jty i = 2,…, A:^a«⁺» 4−1, j = 1,…, *"• -2, * = j 4−1,…, fc^e". Вершины 0″ _i>fcag_₁ переобозначим в ц*- _кая__{х кя}.

В вершину fifj_t мы проходим только в том случае, когда.

Следовательно, = //Д _{J+1 t}(x) и поэтому можно переобозначить вершины fi-j_ty i = 2,. ., fc^ai+ '^+a«-¹ 4- 1, j = l,…, A;^{a — 2, t = j 4- + 2,…, fcQ», через <5,?__llJ+llt.}

Так как (г — 1) изменяется от 1 до k^at+" " ^+a«-¹, (j 4−1) изменяется от 2 до к^ая — 1, t изменяется от (j 4−1) 4* 1 до fc^a», мы получаем все нужные вершины типа ??_рг, 5 = 1,…, fc^Q«+ * ^+a«-i, р = 2,…, A;^a* — 1, г = р4−1,.

Если g < Му то введем новые вершины? = 2,…, fc^ai+«'^+a<*. Из каждой вершины 9_qij, г = 2,…, fc^ai+••+<*"-* 4−1, j = 1,…, fc^a<* — 1, и каждой вершины т’у, г = 2,…, fc^ai+„*^+a“»¹, j = 1,…, /:"* (включая переобозначенные в 17?), проведем ребро в вершину $(j__2)/c^a«+j>i' ^ко» торому припишем предикат, тождественно равный единице. Поскольку проводимость в вершины 9_qij определяется соотношением (4.83), мы имеем, а в вершины r'_qi— — формулой (4.76), то на ^__2)Jtag+J+1 нужную нам функцию, так как.

При изменении г от 2 до fc^a«+—+^a"-» -f 1, j от 1 до к^а<�г, t = (г — — 2)к^а<�г + j + 1 изменяется от 2 до A:^Ql+ ' ^+a", т. е. в нужных нам пределах. Здесь индекс fc^a«+» +^a" + 1 не появляется, поскольку при г = к^аi⁺" +^q9-i + 1 j меняется от 1 до — 1.

Введем новые вершины s = 1,…, А;^а,+ '^+а". Из каждой вершины, г = 2,…, A:^a,+ '^+a«-ⁱ + 1, j = l,…,&^a* — 1, t = = j +1, .(включая вершины, переобозначенные в выпустим ребро в вершину ^_₂)fc^e«+t ^и из каждой вершины т'^, г = = 1,…, k^ai +—+""-«, j = 1,…, (включая переобозначенные в ??•), выпустим ребро в вершину ребрам припишем предикаты, тождественно равные единице.

Учитывая соотношения (4.81) и (4.84), легко заметить, что функция фильтра на введенных вершинах 0] совпадает с нужной нам функцией, задаваемой соотношением (4.73), и s изменяется в пределах от 1 до k^ai^

Тем самым, построение ИГ U_q завершено.

Пусть мы построили информационный граф Um• Теперь, чтобы завершить построение окончательного ИГ U*, решающего задачу нашим методом, нам надо добавить фрагменты, решающие одномерные задачи интервального поиска по вторым координатам («2,^2);

Если q, s, i, j такие натуральные числа, что q 6 {1,…, М}, 5 6 6 {l,…, fc^Ql+-+""-?}, i G {l,…, fc^a-}, j € {i + 1,…, k^a" + 1}, to обозначим.

т. e. A^q_{s i}j состоит из ординат точек библиотеки, абсциссы которых принадлежат интервалу ИГ Um содержит полюсы S^q_{ij }} q = 1,…, М, 5 = 1,…, fc^ai+‘"^+a«-¹, i = 2,…, k^Qq — 1, j = i 4−1,…, k^aq. При q = 1 индексы меняются как 8 = 1, t = 1,…, k^ai — 1, j = i + 1,…, k^ai. В эти полюсы мы попадаем при условии, что.

Из каждого полюса Л? выпустим ИГ U_q, который решает одномерную задачу интервального поиска для запроса (1*2 >^2) среди точек ИЗ A⁴_{s i} -. Листья ИГ U^q, которым соответствуют ТОЧКИ Ур 6 мы объявим листьями окончательного ИГ U* и припишем им записи.

(Ур.Ур) е V.

ИГ Um содержит полюсы ty?., q = 2,…, М, г = 2,…, fc^ei+ *+^e«-i _э .7 = 1,…, — 1, в которые мы попадаем при условии, что

Из каждого полюса выпустим ИГ (Я* • Листья ИГ.

ия^, которым соответствуют точки г/? € _Ла,₊₁, мы объявим листьями окончательного ИГ U* и припишем им записи.

(Ур, 2/р) 6 V.

ИГ Um содержит полюсы ?_t?, q — 2,…, М, г = 1,…,к^а'⁺-+^ая-1 _f j = 2,…, A:^a", в которые мы попадаем при условии, что.

Из каждого полюса С?, выпустим ИГ U_q. Листья ИГ U_q, которым соответствуют точки Ур € А? _1;-, мы объявим листьями окончательного ИГ ?/* и припишем им записи (Ур, Ур) € V.

ИГ U_M содержит полюсы /?^, j = 1,…, fc^ai+" '^+QM, в которые мы попадаем при условии, что

Из каждого полюса 0^ выпустим одно ребро, которому припишем предикат f_y2 6 F2. Конец ребра объявим листом и припишем ему запись {у), у]) € V.

Полученный окончательный ИГ обозначим U*. Он соответствует алгоритму решения двумерной задачи интервального поиска, описанному в предыдущем разделе.