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

Оценки В-сложности задачи о доминировании.

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

Теорема 40. Если I = (A’</om, V, pdom) — п -мерная задача о доминировании, тп.е. задача типа Sdom, Т — базовое множество, содержащее характеристические функции всех записей из V, то Т(1,Т) =

= т

Математическая модель фоновых алгоритмов поиска.

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

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

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

Отсюда видно, что к алгоритмам для работы в фоновом режиме предъявляются другие требования, по сравнению с обычными алгоритмами. Для фоновых алгоритмов особенно важна способность быстро получать первый элемент ответа, тогда как все остальные можно получать не так быстро, за отрезки времени, приблизительно равные времени обработки одного элемента ответа пользователем алгоритма.

Заметим также, что в задачах, в которых предполагается, что ответ содержит только один элемент, понятие фонового алгоритма теряет смысл.

В данном разделе предлагается математическая модель, предназначенная для исследования сложности фоновых алгоритмов поиска.

Результаты данного раздела в основном были опубликованы в [33].

В качестве модели фоновых алгоритмов поиска предлагается использовать информационные графы (ИГ), но сложность ИГ предлагается вводить по-другому, так, чтобы она отражала сложность фоновых алгоритмов.

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

Для того, чтобы описать эту процедуру, сделаем следующие предположения:

• будем считать, что каждому ребру мы можем временно приписывать номер, который назовем путевым;

• можем отмечать вершины некоторым образом;

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

Теперь мы можем перейти к описанию процедуры обхода графа (/, которая представляет собой линеаризацию во времени процесса поиска при помощи графа U. Входными данными процедуры обхода В будут информационный граф U и запрос х G X. Выходными данными — упорядоченное множество J записей, входящих в ответ на запрос х, и последовательность Т моментов появления записей в ответе.

Итак, пусть нам даны ИГ U и запрос х, тогда процедуру обхода В можно описать следующим образом.

1. (Инициализация процесса обхода)

(a) Сотрем со всех вершин отметки.

(b) Объявим текущей вершиной корень графа U.

(c) Обнулим счетчик времени t = 0.

(d) Присвоим счетчику путевых номеров значение тп = 1.

(e) Присвоим начальное значение множествам J и Т J = 0 и Г = 0.

(f) Перейдем к пункту 2.

2. (Прямой ход)

(а) Если текущая вершина — непомеченный лист графа (/, то

i. заносим в конец множества J запись, принадлежащую текущей вершине;

ii. заносим в конец множества Т значение счетчика времени t

iii. переходим к пункту 2(b).

(b) Отмечаем текущую вершину.

(c) Бели текущая вершина есть точка переключения, то:

i. вычисляем значение переключателя, приписанного текущей вершине, на запросе х (пусть это значение равно п)

ii. увеличиваем на 1 значение счетчика времени: t = t + 1;

iii. если среди ребер, исходящих из текущей вершины, нет ребра с номером п, то переходим к пункту 3;

iv. если конец ребра с номером п отмеченная вершина, то переходим к пункту 3;

v. ребру с номером л, исходящему из текущей вершины, приписываем путевой номер т, объявляем конец этого ребра текущей вершиной, присваиваем т = m-fl и возвращаемся к пункту 2.

(d) Если текущая вершина не является точкой переключения,

то:

i. если из текущей вершины не исходит ни одно ребро или из нее исходит ребро, имеющее путевой номер, и это ребро последнее по порядку следования в пучке текущей вершины, то идем к пункту 3;

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

iii. присваиваем выбранному ребру путевой номер т;

iv. вычисляем приписанный выбранному ребру предикат на запросе х (пусть его значение равно п);

v. увеличиваем на 1 значение счетчика времени: t = t + 1;

vi. если n = 0, то возвращаемся к пункту 2;

vii. если конец выбранного ребра отмеченная вершина, то возвращаемся к пункту 2;

viii. если п = 1, то объявляем конец выбранного ребра текущей вершиной, присваиваем т = т 4-1 и возвращаемся к пункту 2.

3. (Обратный ход)

(a) Если из текущей вершины исходит ребро, имеющее путевой номер, то стираем с ребра этот номер.

(b) Уменьшаем значение счетчика путевых номеров: т = т — 1.

(c) Если т = 0, то заносим в конец множества Т значение счетчика времени и завершаем работу процедуры.

(d) Если m > 0, то, значит, существует ребро, входящее в текущую вершину и имеющее путевой номер т, выбираем его.

(e) Объявляем текущей вершиной начало выбранного ребра.

(f) Если текущая вершина является точкой переключения, то возвращаемся к пункту 3.

(g) Иначе возвращаемся к пункту 2.

Легко видеть, что данная процедура обхода позволяет посетить все вершины, функции фильтров которых принимают значение 1 на запросе х. Значит, на выходе алгоритма мы получаем множество J = {у*,,..., yim }, совпадающее с ответом Л(х) графа U на запрос х, и множество

где U — время появления в ответе г-ой записи (г = l,m), tm+i — время работы процедуры, выраженное в количестве вычисленных предикатов и переключателей. При желании определить его более точно надо сопоставить каждому предикату и переключателю число, равное времени его вычисления. Тогда время работы процедуры будет равно сумме времен вычисления всех переключателей и предикатов. Можно также учитывать время обратного хода, изменяя соответствующим образом значение счетчика времени на шаге 3 процедуры. Но в данной работе мы рассматриваем лишь приближение к реальному времени вычисления, т. е. мы пренебрегаем всеми затратами времени, кроме вычисления предикатов и переключателей, причем считаем, что каждый из них вычисляется за время, равное одному такту.

Введем теперь сложность графа U так, чтобы она отражала сущность фонового алгоритма.

Пусть нам даны ИГ ?/, запрос х, а также некоторый субъект, которого назовем пользователем. Пусть на обработку г-ой записи ответа пользователю требуется время Tj, г = 1 , т. Предполагаем, что Ti,T2,... ,тт — независимые одинаково распределенные действительные случайные величины. Тогда за сложность графа U целесообразно принять не все время работы процедуры ?m+1, а только то время, которое пользователь тратит “впустую”, ожидая появления очередной записи. Обозначим эту величину через T(U} х, Ti,..., тш).

Рис. 3.22. Моменты появления элементов ответа и интервалы “раздумий”

Рассмотрим пример, изображенный на рис. 3.22. В этом примере ответ содержит 3 записи. Пользователь находится в состоянии ожидания трижды: сначала в ожидании первой записи в течение t тактов времени, затем в ожидании второй записи в течение ?2 (?1 +Ti) и, наконец, в ожидании завершения работы алгоритма (чтобы убедиться, что больше записей в ответе нет) в течение ?4 — (?2 + т2 + тз). Таким образом, в этом примере

T(U, х, Ti, т2, т3) = ?1 + ?2 - (?1 + П) + ?4 - (?2 + т2 + т3) = ?4 - Ti — т2 - т3.

Этот пример иллюстрирует следующий очевидный факт: если tj — это последний момент времени, перед которым пользователь находился в состоянии ожидания, то

Или это можно записать иначе:

Функция Т(?/, х,Ti,..., rm) является случайной величиной, как измеримая функция от случайных величин ri,... ,тт. Тогда мы можем определить сложность графа U на запросе х как математическое ожидание этой случайной величины Т((/, х, т,..., тт), т. е.

По аналогии с леммой 1 из главы 1 справедлива следующая лемма.

Лемма 45. Если базовое множество Т измеримое, то для любого ИГ U над базовым множеством Т функция Тф(С/,х), как функция от х} является случайной величиной.

Доказательство. Доказательство леммы полностью аналогично доказательству леммы 33 с единственным отличием, что обозначение Гп {Uу 7ц, х) заменяется на Тф ([/, х).

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

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

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

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

где 1А(1уТ) — множество всех ИГ над базовым множеством Ту разрешающих ЗИП I.

Число

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

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

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