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

Сложность информационного графа.

Прежде чем вычислять сложность ИГ [/*, докажем одно вспомогательное утверждение.

Пусть 0 некоторая вершина некоторого ИГ U. Скажем что подграф U' графа U является зависимым от /?, если он содержит вершину /?, является связным, состоит только из таких вершин а ИГ ?/, что любая цепь, ведущая из корня ИГ U в вершину а, проходит через вершину 0 и содержит все ребра ИГ С/, исходящие из вершин V.

Так, например, если вершина 0 является корнем связного ИГ V, то ИГ U будет зависимым от 0. А для произвольной вершины 0 любой зависимый от 0 граф по крайней мере содержит все ребра, исходящие из вершины 0.

Договоримся через Р(АВ) обозначать условную вероятность события А при условии осуществления события В.

= Р(В|Х').

Пусть X — множество запросов с заданным на нем вероятностным пространством (X, сг, Р). Пусть X'о. Вероятностным пространством, порожденным множеством X', назовем вероятностно* пространство (Ха Р'), где а' = 6 <г. В С X'}, Р' — такая вероятностная мера на что для любого В € <т' имеем Р'(В) =

Лемма 51. Пусть Р некоторая вершина некоторого ИГ U над базовым множеством, функции которого определены на множестве запросов X. Пусть (X, а, Р) — вероятностное пространство над X. Пусть X' = Nip$. Пусть (Х <т Р') — вероятностное пространство, порожденное множеством X'. Пусть U' — зависимый от Р подграф ИГ U. Пусть Т' — сложность ИГ U' (как отдельного ИГ с корнем в вершине Iв) для вероятностного пространства (Х а Р'). Тогда сложность U' как подграфа ИГ U для вероятностного пространства (X, а, Р) равна T(U') = Р(Х') • Г.

Доказательство. Рассмотрим произвольную вершину а подграфа U'. Из определения зависимого подграфа следует, что N С С N(p0 = XСледовательно,

Откуда сразу следует утверждение леммы.

Вычислим сложность ИГ U*.

Пусть Р — некоторая вершина ИГ U*. Чтобы сократить этажность формул договоримся обозначать JV(/?) = NV6.

Введем следующие множества вершин ИГ U*:

Обозначим через Tq (g = 1,2,..., М) суммарную сложность ребер ИГ Uq за исключением ребер, исходящих из вершин из множества В4. Через Tq(x) (q = 1,2, ...,М) обозначим сложность ИГ Uq на запросе х минус количество вычисленных переключателей, приписанных вершинам из множества В4.

Покажем по индукции, что

%ЛЯ Любого X G Xint2- Базис индукции: q = 1.

Из соотношений (4.67), (4.78) и (4.79) легко следуют следующие /тверждения

Поскольку из корня ИГ U* растет ИГ Uj^i 0 i, сложность которого оценивается соотношением (4.68), вершинам приписаны переключатели <$, из вершин 0” исходят ИГ р v зависимые от в" и сложность которых оценивается соотношением (4.69), а из вершин Оу исходят ребра с предикатом тождественная 1, то с учетом (4.97) согласно лемме 51 имеем

и для любого хXint2

Индуктивный переход. Пусть q € {2,..., М} и утверждение индукции выполняется для q - 1. Обозначим

Из соотношений (4.72)-(4.74), (4.80), (4.81), (4.83) и (4.84) легко следуют следующие утверждения

Поскольку из вершин т??-1 и 7?-1 исходят ИГ Ufq ,_i ,_j, слож-

ность которых оценивается соотношением (4.68) и зависимые от этих вершин, из вершин $~1 исходят ИГ Uf4 ,_i ,_i, а из вершин —

ИГ Ul9j /9 сложность которых оценивается соотноше-

нием (4.69) и которые зависимы от своих корневых вершин, из каждой вершины из множества исходит ребро с предикатом тождественная 1, ведущее в вершины i9?, а из каждой вершины из множества исходит ребро с предикатом тождественная 1, ведущее в вершины /??, то с учетом (4.98) согласно лемме 51 имеем

и для любого х Е Xint2 выполняется

При q = М нам надо делать на одно вычисление меньше, так как в ИГ Um нет вершин типа tff*, т. е.

для любого х Е Xint2- Обозначим

Из (4.73), (4.75)-(4.77), (4.82) непосредственно проверяется справедливость следующих утверждений

Пусть Е #13, тогда для некоторых q, 5, г, j из вершины (3 исходит

ИГ Uq , зависимый от вершины В. Обозначим A»ij

Учитывая, что при попадании в вершину из В2 мы вычисляем один предикат, приписанный ребру, исходящему из этой вершины, а при попадании в вершину из В мы вычисляем один переключатель, приписанный этой вершине, имеем

Согласно лемме 51 и (4.70) для данной вершины р

Согласно (4.99) для любого запроса мы можем попасть не более чем в одну вершину из #gU#i2, следовательно при этом мы в худшем случае выполним 2 + log2 к вычислений плюс перечисление ответа. Согласно (4.100) для каждого q = 2,...,М и любого запроса мы можем попасть не более чем в одну вершину из В4 U Вт и не более чем в одну вершину из Вц ив каждом из этих случаев мы выполним не более чем 2 + log2 к вычислений плюс перечисление ответа. Тем самым для любого запроса хX{nt2

Тем самым, теорема 52 полностью доказана.

Понятно, что данный метод может быть обобщен для п-мерной задачи интервального поиска для произвольного п.

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