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

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

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

Пусть [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 то Uzej позволяет находить точку из множества {6 = = zo, z9..., zi}, ближайшую слева к vi.

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

Вероятностная мера вероятностного пространства над множеством запросов v € [е,/] при условии, что 0^6^ и ^ 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 = Xint. ИГ U будем строить по методу, описанному в разделе 4.1.5, с помощью функций из G$ U (7б, -Рг-

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

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

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

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

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

типов.

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

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

2. При 1 ^ q ^ М в Uq есть полюсы /3?, j = 1,..., fcai+•••+“« f на которых реализуются функции

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

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

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

4. При 1 ^ q ^ М в Uq есть полюсы 5 = 1,..., &ai+"+a«-*1, i = 2,..., — 1, j = г +1,..., . При q = 1 индексы меняются

как 5 = 1,г = 1,..., /:ai — 1, j = * + &ai. На них реализуются

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

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

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

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

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

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

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

Возьмем ИГ 01. Он имеет (ках +1) концевых вершин. Обозначим их 0i,... ,0*«1+1.

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

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

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

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

а в 6" — когда 1}_х < и ^ it-, v ^ I]. Поэтому если М > 1, то мы можем переобозначить все 0', в 7/, а 0” — в , г = 2,..., ках. Вершину 0| пометим символом

Если М = 1, то все 0J, г = 1,..., ках, пометим символом Каждую вершину в", г = 1,..., kai —1, (включая переобозначенные в 0J) отождествим с корнем ИГ U^lti ^ v где

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

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

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

т.е. A(x).

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

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

Из каждой вершины , г = 2,..., l+•+a9-ij выпустим инфор- мационный граф Ur4 ,_i q~x. Этот граф имеет листьев, которые

обозначим •, j = 1,..., Ага«.

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

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

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

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

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

?Л'< >*» »*«+1

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

в том случае, когда

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

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

»‘i-l »*<

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

Из каждой вершины 9qij, г = 2,..., fce»+—+*«-1 + 1,^ = 1,..., — 1,

выпустим два ребра, левому припишем 1, правому — 2, а самой Oqij припишем переключатель д% (х). Конец левого ребра, выходящего из Qqij, обозначим 9qij, конец правого — 0"-^. Псреобозначим

все , г = 2, — , fc*i+-+a,_i +1, через 9'qik*q.

Если q < М, то переобозначим все 0^;-, г = 2,..., &<*!+? *+а«-» 4- 1, j = l,...,/:"4, через 7^_2)*°«+>+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 до fcai+",+akai+'"+ая + 1.

Если q = М, то все 0'^-, г = 2,..., fca»+--+a9-i 4- 1, j = 1,..., fca,?, пометим символом

В вершины 0qij мы попадаем при условии, что

Из каждой вершины 9qij, г=2,..., kai+-+««-i4-ij j=l,..., fca«-2, выпустим ИГ t/L., , где

—2)fc°9 +i+l ’**

Этот информационный граф имеет — j) листьев, которые обозначим tfjty i = 2,..., A:a»+"4-1, j = 1,..., *“• -2, * = j 4-1,..., fce«. Вершины 0"i>fcag_1 переобозначим в ц*- кая_х к<>я.

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

Следовательно, = //Д J+1 t(x) и поэтому можно переобозначить вершины fi-jty i = 2,.. .,fcai+ '+a«-1 4- 1, j = l,...,A;a — 2, t = j 4- + 2,..., fcQ«, через <5,?_llJ+llt.

Так как (г - 1) изменяется от 1 до kat+""+a«-1, (j 4-1) изменяется от 2 до кая — 1, t изменяется от (j 4-1) 4* 1 до fca«, мы получаем все нужные вершины типа ??рг, 5 = 1,..., fcQ»+ * +a«-i, р = 2,..., A;a* — 1, г = р4-1,..

Если g < Му то введем новые вершины ? = 2,..., fcai+“'+a<*. Из каждой вершины 9qij, г = 2,..., fcai+••+<*«-* 4-1, j = 1,..., fca<* — 1, и каждой вершины т'у, г = 2,..., fcai+”*+a«“1, j = 1,..., /:“* (включая переобозначенные в 17? ), проведем ребро в вершину $(j__2)/ca«+j>i’ ко" торому припишем предикат, тождественно равный единице. Поскольку проводимость в вершины 9qij определяется соотношением (4.83), мы имеем

а в вершины r'qi- — формулой (4.76), то на ^_2)Jtag+J+1 нужную нам функцию, так как

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

Введем новые вершины s = 1,..., А;а,+ '«. Из каждой вершины , г = 2,..., A:a,+ '+a«-i + 1, j = l,...,&a* — 1, t = = j +1, .(включая вершины, переобозначенные в выпустим ребро в вершину ^_2)fce«+t и из каждой вершины т'^, г = = 1,..., kai +—+««-», j = 1,..., (включая переобозначенные в ??•), выпустим ребро в вершину ребрам припишем предикаты,

тождественно равные единице.

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

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

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

Если q, s,i,j такие натуральные числа, что q 6 {1,...,М}, 5 6 6 {l,...,fcQl+-+“«-?}, i G {l,...,fca-}, j € {i + 1,..., ka" + 1}, to обозначим

т. e. Aqs ij состоит из ординат точек библиотеки, абсциссы которых принадлежат интервалу

ИГ Um содержит полюсы Sqij } q = 1,..., М, 5 = 1,..., fcai+‘”+a«-1, i = 2,..., kQq — 1, j = i 4-1,..., kaq. При q = 1 индексы меняются как 8 = 1, t = 1,..., kai — 1, j = i + 1,..., kai. В эти полюсы мы попадаем при условии, что

Из каждого полюса Л ? выпустим ИГ Uq , который решает одно- мерную задачу интервального поиска для запроса (1*2 >^2) среди точек

ИЗ A4s i -. Листья ИГ U^q , которым соответствуют ТОЧКИ Ур 6 мы объявим листьями окончательного ИГ U* и припишем им записи

(Ур.Ур) е V.

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

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

ия ^ , которым соответствуют точки г/? € Ла,+1, мы

объявим листьями окончательного ИГ U* и припишем им записи

(Ур,2/р) 6 V.

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

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

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

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

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

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