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

Сложность информационных графов

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

Предполагается, что эта процедура хранит в своей (внешней) памяти структуру ИГ U. Входными данными процедуры является запрос. Выходными данными является множество записей.

Пусть на вход процедуры поступил запрос х. Вводим понятие активного множества вершин и вносим в него в начальный момент корень ИГ U и помечаем его. Далее по очереди просматриваем вершины из активного множества и для каждой из них проделываем следующее:

• если рассматриваемая вершина — лист, то запись, приписанную вершине, включаем в ответ;

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

• если рассматриваемая вершина предикатная, то просматриваем по очереди исходящие из нее ребра и вычисляем значения предикатов, приписанных этим ребрам, на запросе х. Концы ребер, которым соответствуют предикаты со значениями, равными 1, если они непомеченные, помечаем и включаем в множество активных вершин;

• исключаем рассматриваемую вершину из активного множества.

Процедура завершается но исчерпании активного множества.

Заметим, что если ИГ разрешает задачу /, то множество, полученное на выходе процедуры, будет содержать все те и только те записи библиотеки (?/), которые удовлетворяют запросу х. То есть, полученная процедура решает ЗИП I = (X, V,p), где V = ((/), и, значит, является алгоритмом поиска.

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

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

Отметим, что в большинстве работ, посвященных исследованию сложности алгоритмов поиска, под сложностью алгоритма понимается время поиска в худшем случае [56, 70, 86, 113, 115, 116, 118, 119, 125, 126, 144, 147, 149-152, 165, 178, 179, 183, 212, 216), и в сравнительно редких случаях (см., например, [50, 56, 120, 124, 143, 184,

186, 188, 190, 199, 210]) исследуется среднее время поиска, хотя для задач поиска, используемых в базах данных, для которых характерны массовость и многократность, исследование среднего времени поиска представляется более актуальным. Некоторое объяснение крена в сторону изучения сложности в худшем случае можно найти в цитате из [86, с. 20]: “К сожалению, анализ поведения в среднем значительно более сложная вещь, чем анализ худшего случая, по двум причинам: во-первых существенные математические трудности возникают, даже если удачно выбрано исходное распределение; во-вторых, часто с трудом достигается согласие в том, что именно выбранное распределение является реальной моделью изучаемой ситуации. Вот почему преобладающее большинство результатов связано с анализом худших случаев.”

Определим понятие сложности ИГ на запросе.

Будем считать, что время вычисления любого переключателя из G примерно одинаково и характеризуется числом а, а время вычисления любого предиката из F — числом Ь.

Пусть нам дан некий ИГ U и произвольно взятый запрос х ? X.

Сложностью ИГ U на запросе х назовем число

Величина T(U,x) характеризует время работы описанной выше процедуры поиска, сопоставленной ИГ U, поскольку T(U,x) равно количеству переключателей, вычисленных данной процедурой при подаче на ее вход запроса х, умноженное на а, плюс количество вычисленных предикатов, умноженное на 6.

Сложность ИГ можно вводить двумя способами. Во-первых, как максимальную сложность на запросе

(здесь мы берем шах, а не sup, так как Т(?/, х) принимает целые значения, и, значит, sup всегда достигается). Эта величина характеризует время поиска в худшем случае соответствующим ИГ алгоритмом и ее будем называть В-сложностью ИГ (верхней сложностью). Эта величина исследуется в большинстве работ, посвященных проблемам сложности задач поиска.

Во-вторых, можно вводить сложность ИГ как среднее значение сложности ИГ на запросе, взятое по множеству всех запросов. С этой целью введем вероятностное пространство над множеством запросов X, под которым будем понимать тройку (X, сг, Р), где а — некоторая алгебра подмножеств множества X, Р — вероятностная мера на <т, т. е. аддитивная мера, такая, что Р(Л*) = 1.

В связи с тем, что мы ввели вероятностное пространство над множеством запросов, уточним понятие типа. А именно, под типом

будем понимать тройку 5 = (Х> Y, р), считая, что множество запросов X рассматривается вместе со своим вероятностным пространством (X, <т, Р). В тех же случаях, когда мы хотим явно выделить рассматриваемое вероятностное пространство над X, мы будем представлять тип пятеркой S = (X, У, р, <т, Р).

Скажем, что базовое множество Т = (F, G) измеримое, если алге-

л

бра а содержит все множества ЛГ/, где / G F U G.

Справедлива следующая лемма.

Лемма 1. Если базовое множество Т = (F, G) измеримое, то для любого ИГ U над базовым множеством Т функция T(U,x), как функция от х, является случайной величиной.

Доказательство. Нам необходимо доказать, что для любого ИГ U над базовым множеством Т и любого действительного числа г множество {хбХ: T(U, х) < г} € <7.

Покажем, что G И(У)) —> G <т).

Пусть р G 7l(U). Пусть Ср — множество всех ориентированных цепей ИГ U, ведущих из корня в вершину р. Пусть С — некоторая цепь, а с — некоторое ребро. Через в(с) обозначим проводимость ребра с.

Нетрудно видеть, что

Учитывая, что N/vp = Nf U Ng, Nf^g = Nf П Ng, имеем Введем следующее обозначение:

Тогда, как нетрудно видеть,

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

Далее всюду будем предполагать, что базовое множество измеримо.

Сложностью ИГ U назовем математическое ожидание величины Т(С/, я), т. е. число

Если (/?, а) — ребро ИГ, то сложностью этого ребра назовем число • Ь • Р— если (/?, а) — предикатное ребро;

аP(NVfi)/il>p — если это ребро переключательное.

Если 0 — вершина ИГ, то число Р(Л^) назовем сложностью вершины 0.

Нетрудно показать, что сложность ИГ равна сумме сложностей ребер ИГ. В самом деле

Далее всюду будем предполагать, что а = b = 1.

Пусть нам дан ИГ U.

Объемом Q(U) ИГ U назовем число ребер в ИГ U.

В качестве примера мы можем подсчитать сложность ИГ (/, изображенного на рис. 1.5. Легко видеть, что Q(U) = к и T(U) = fc, т. е. объем графа минимально возможный, а время максимальное. Это и не удивительно, так как ИГ U соответствует переборному алгоритму поиска.

Пусть нам дана некая ЗИП Юложпостью задачи I при базовом множестве Т и заданном объеме q назовем число

где U(l, Т) — множество всех ИГ над базовым множеством Т, разрешающих ЗИП /.

Соответственно В-сложностью задачи I при базовом множестве Т и заданном объеме q назовем число

(здесь мы берем min, а не inf, так как T(U) принимает целые значения, и, значит, inf всегда достигается).

Число

назовем сложностью задачи I при базовом множестве Т.

Соответственно В-сложностью задачи I при базовом множестве Т назовем число

Если к — натуральное число, 5 — тип задач поиска, то обозначим

Будем исследовать функции, характеризующие сложность класса ЗИП Z(fc,5), такие как функции Шеннона:

(в первом случае мы берем max, а не sup, так как Т(1,Т) принимает целые значения, и, значит, sup всегда достигается) и как средние значения:

где среднее значение берется по всем ЗИП I G Z(fc, S).

Если существует такой ИГ UU(I, Т), что T(U) = T(/,Z*), то ИГ U будем называть оптимальным для ЗИП I. Соответственно

^*4.

если T(U) = Т(/, Т), то ИГ U будем называть В-оптималъным для ЗИП I.

Можно привести пример такой ЗИП и такого базового множества, для которых не существует оптимального ИГ.

Пусть X = Y = [0,1] и на X задана равномерная вероятностная мера. Пусть отношение поиска есть отношение для действительных чисел. Пусть библиотека состоит из одной записи V = {3/4}. Пусть базовое множество имеет вид Т = {/% 0), где

Рассмотрим ЗИП I = (X, V, ^). Поскольку

то Хз/4,> = Гдля любого а 6 (0,1/2). Рассмотрим ИГ (7а, состоящий из двух последовательно соединенных ребер, начало первого из которых есть корень ИГ, а конец второго — лист, которому приписана запись первому ребру соответствует предикат /^, а второму — f

Нетрудно видеть, что T(Ua) = 1 4- а 4- 1/4 = 5/4 -На. Очевидно, что Т(1,Т) = inf{T(UQ): а ? (0,1/2)} = 5/4, но не существует ИГ, чья сложность равна 5/4.

Скажем, что некая вершина ИГ достижима из корня на запросе хX или просто достижимая па запросе х € X, если функция фильтра этой вершины на запросе х равна 1.

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

• ребро исходит из недостижимой вершины,

• ребро является предикатным и входит в корень или в недостижимую вершину,

• ребро является предикатным и не принадлежит ни одной цепи, ведущей из корня в какой либо лист,

• ребро является переключательным, и начало этого ребра не принадлежит ни одной цепи, ведущей из корня в какой либо лист,

• ребро является переключательным, и число, приписанное этому ребру, больше максимально возможного значения переключателя, соответствующего началу этого ребра,

• начало и конец ребра совпадают.

В противном случае ребро называем существенным.

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

Теорема 3 (о существовании оптимальных графов). Если множество запросов X конечно, то для любой ЗИП I = (X,Y,p) и любого базового множества Т = (F, G) такого, что U{I,F) ф 0, существует оптимальный ИГ над базовым множеством Т.

Доказательство. Заметим, что из за конечности множества X множества F и G конечны. В самом деле, если |Х| = т, то число предикатов, определенных на X не больше, чем 2т. Следовательно, |F| ^ 2т. Так как область значений любого переключателя есть начальный отрезок натурального ряда, то любой переключатель над X принимает не более т значений, следовательно |(2| < тт.

Для произвольного ИГ U обозначим через N(U) подграф графа U, состоящий из ребер, имеющих ненулевую сложность.

Возьмем произвольный ИГ Uq € ?V(/, Т). Обозначим W = {U € € T(U) ^ T(C/0)h М' = {АГ(Г/): U в U'}. Очевидно, что

Для доказательства существования оптимального ИГ для ЗИП / нам достаточно показать конечность множества ЛЛ

Пусть |F U G — п. Пусть М — множество, состоящее из тождественно нулевого предиката и всех предикатов, полученных из предикатов множества F U G с помощью операций конъюнкции и дизъюнкции. Понятно, что М ^ min(2m, 22 ). Обозначим М' = {/ 6 М: Р(N/) >0}. Пусть min Р(N/) = г. По определению г > 0. Поскольку для любого ИГ над Т функции фильтров вершин принадлежат множеству М, то сложность любого предикатного ребра ИГ над Т либо нулевая, либо не меньше чем г, а сложность любого переключательного ребра с ненулевой сложностью не меньше чем r/m. Отсюда в любом ИГ из множества ЛЛ число ребер не больше чем T(Uq) • т/г.

Так как из конечности множеств F и G следует конечность числа различных нагрузок ИГ, то, значит, множество Л/7 конечно.

Что и доказывает теорему.

Упражнения

1.17. Пусть X = {1,2,..., N}y 5 = (X, X, =, Р, а) — тип поиска идентичных объектов, где о — 2х, Р — равномерная вероятностная мера, т.е. для любого хX выполняется Р(х) = 1/N.

1. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.6.

2. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.7.

3. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.8. Для базового множества и ЗИП, приведенных в упражнении 1.8, постройте информационный граф со сложностью, не большей, чем 1.48.

4. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.9, если N = 100. Для какого значения параметра m сложность будет минимальна. Для какого значения параметра m В-сложность будет минимальна. Для какого значения параметра m объем будет минимальным.

1.18. Если X = {1,2,...,7V} инаХ задана равномерная вероятностная мера, то посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.10.

1.19. Пусть на множестве запросов X = [0,1] задана равномерная вероятностная мера. Посчитайте сложность, В-сложность и объем информационного графа, полученного при решении упражнения 1.11.

1.20. Пусть на множестве запросов X»n* = {(u,v) : 0 ^ и ^ v ^ 1} задана равномерная вероятностная мера. Посчитайте сложность, В-сложность и объем информационного графа, изображенного на рис. 1.1.

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