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

Последовательные алгоритмы решения задачи о доминировании.

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

Теорема 39. Пусть ЗИП I = (XdomiV,Pdom)п-мерная задача о доминировании, т. е. задача типа Sdom, где V = к. Пусть Тбазовое множество, определяемое соотношениями (3.15)—(3.18), п ^ ^ 1. Пусть

Тогда, если функция плотности вероятности р(х) ^ с, то

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

Мы рассмотрим отдельно две возможности: одномерную задачу о доминировании и многомерную.

Одномерный случай.

В данном пункте мы рассмотрим одномерную задачу о доминировании, т. е. случай, когда п = 1.

Пусть V = (у1,..., у*}, где у* 6 [0,1], г = 1, к. Будем считать, что записи в V упорядочены в порядке возрастания, т. е.

Остается заметить, что отношение pdom при п = 1 есть отношение линейного предпорядка. Поэтому, как показано в доказательстве теоремы 35, ИГ U, изображенный на рис. 3.20, разрешает ЗИП /, и его сложность равна

а объем равен Q(U) = п.

Рис. 3.20. Граф для одномерной задачи о доминировании

Многомерный случай.

В данном пункте мы рассмотрим многомерную задачу о доминировании, т. е. случай, когда п > 1.

Введем вспомогательные обозначения.

Если V С Ydom, г € [0,1] и 1 ^ *1 < • • • < ii ^ п, то обозначим

Пусть у1 = (уу2,...,у% где i = 0,п - 1. Здесь и далее под значком у0 будем понимать пустое место или отсутствие значка; так, например, запись М1(у°) будем понимать как М

Пусть М — некоторое конечное, упорядоченное по возрастанию множество точек из отрезка [ 0,1]. Пусть у ? М. Пусть у" — следующая за у точка в М, если у — нс последняя вМ,иу" = 1, если у — последняя точка в М. Обозначим

Введем по индукции следующие обозначения. Базис индукции. Обозначим

Шаг индукции. Пусть i € {2,п} и для всех j € {1,1 — 1} определены множества

где yj 1 = (yy2,--.,yi ') - !

произвольный вектор из У71. Пусть уг~1 = (г/1, j/2,.. -, 3/*“1) — произвольный вектор из У*"1. Тогда обозначим

где Zy(M) определяется соотношением (3.19).

Построим по индукции некоторый информационный граф Uq (q 6 {l,n — 1}), который удовлетворяет следующим условиям:

1. Граф Uq имеет (У*7) листьев.

2. Между Yq и множеством листьев графа Uq можно установить взаимно однозначное соответствие, такое, что если листу а граБазис индукции, q = 1.

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

= ]с-|МЧ[.

Заменим в графе U^ переключатель g^ на а все переключатели вида д^У0 на gi,>,y0i где переключатели plt.,m и дг,>,У0 описываются соотношениями (3.15) и (3.16) соответственно. Полученный граф обозначим U. Покажем, что граф U удовлетворяет условиям утверждения индукции.

Так как У1 = М то граф U имеет |У11 листьев и, следовательно, удовлетворяет условию 1 утверждения индукции.

Легко видеть, что в результате смены нагрузки переключательных вершин граф U на множестве запросов X1 решает следующую задачу о близости: он позволяет для произвольного запроса х = (xi,..., xn) G 6 X1 находить такую точку из М которая является ближайшей слева к числу xi, т. е. к первой координате вектора х. Откуда сразу следует, согласно теореме 1, что если у — произвольная точка из М1 (а, значит, и из У1) и а — лист, которому соответствует точка у, то

что и доказывает выполнение условия 2 утверждения индукции. Подсчитаем сложность графа U. Обозначим

Пусть

Тогда так же, как в доказательстве теоремы 19, можно получить, что

Что и доказывает выполнение условия 3 утверждения индукции.

Объем графа U был подсчитан в доказательстве теоремы 19, и он равен

Следовательно, выполняется условие 4 утверждения индукции.

Индуктивный переход. Пусть 1 < q < п и построен граф Uq~ i, удовлетворяющий условиям индукции. Покажем, как можно построить граф Uq.

Возьмем произвольный лист а графа Uq-. Пусть ему соответствует вектор (у1,...,уч~1) из Yq~ Упорядочим по возрастанию множество Мч..., У4'1)- Построим для него граф решающий вторую задачу о близости, так, как было описано в разделе 2.3, где в качестве параметра т возьмем т = ]с • |Мя..., г/*7-1 )| [•

Заменим в графе U^ переключатель g^ на а все переключатели вида на дъ>,У0, где переключатели дч,.,т и дч,>,У(3 описываются соотношениями (3.15) и (3.16) соответственно. Полученный ИГ обозначим Ua.

Уберем нагрузку листа а и объявим его обычной вершиной, после чего отождествим его с корнем графа UQl т. е. Ua будет расти из а.

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

Поскольку множество Y4 строится таким образом, что каждый вектор (у1,..., у9-1) из У9-1 порождает |Мч ..., г/91)] векторов множества У9, и поскольку из каждого листа графа Uq-1, которому соответствует вектор (у1,..., у9-1) из У9-1, выпускается граф, имеющий |М91,. • • > 2/9""1)! листьев, то граф Uq имеет ровно |У9| листьев; тем самым доказано выполнение условия 1 утверждения индукции.

Покажем, что выполняется условие 2 утверждения индукции. Для этого рассмотрим произвольный лист а графа Uq-. Пусть ему соответствовал вектор (у1, • •. ,у9-1) из У9-1. Согласно предположению индукции функция фильтра листа а такова, что пропускает в лист а только запросы из множества Xя ..., у9-1). Легко видеть, что в результате смены нагрузки переключательных вершин граф Ua решает следующую задачу о близости: он позволяет для произвольного запроса а; = (a?i,..., хп) 6 Хя..., у9-1) (поскольку только эти запросы достигают листа а) находить такую точку из Мя..., у9-1), которая является ближайшей слева к числу xq, т. е. к q-й координате вектора х. Откуда сразу следует, согласно теореме 1, что если у — произвольная точка из Мя(у, у9-1) (и, значит, (у1,..., у9-1, у) принадлежит Y4)

и о/ — лист, которому соответствует точка у, то

и листу а' можно сопоставить вектор (у1,..., уя~1уу) из У*7, что и доказывает выполнение условия 2 утверждения индукции.

Подсчитаем сложность графа Uq.

Возьмем произвольный лист а графа Uq-. Пусть ему соответствовал вектор (у1,..., у91) из У9"1. Согласно предположению индукции, только запросы из множества Xя1,... Ууя~1) достигают листа ос. Переобозначим это множество в Ха. Переобозначим множество Мя... Ууя~1) в Ма, а множества Z^i(Mt(y1i.. • ,у*“1)) -bZ“, где

i = lyq — 1. Тогда легко видеть, что

Подсчитаем сложность графа Ua. Обозначим

где т = ]с|Ма|[, D{ определяются соотношениями (3.20). Тогда так же, как в доказательстве теоремы 19, с учетом того, что в а попадают только запросы из Ха, можно получить, что

где V* = Ма П Di. Так как

где через l(Z“) обозначена длина отрезка Z®, то согласно лемме 14

Откуда следует, что и

Теперь заметим, что если а, а7C(Uq-) (т. е. а и а7 — листья графа Uq-i) и а ф а7, то Ха П Ха = 0. Кроме того,

Неравенство (3.21) следует из того, что величина П>=} Равна

объему многомерного параллелепипеда Ха, а сумма объемов всех параллелепипедов Ха не превышает объема параллелепипеда Xjom, то есть 1.

Следовательно,

Таким образом, условие 3 утверждения индукции выполняется. Подсчитаем объем графа UQ.

Следовательно, условие 4 утверждения индукции выполняется. И, значит, нам удалось построить граф Uq) который удовлетворяет всем условиям утверждения индукции.

Строить граф С/, обеспечивающий мгновенное решение многомерной задачи о доминировании /, будем следующим образом. Возьмем граф Un- и рассмотрим произвольный лист а этого графа. Пусть ему соответствует вектор (у1, ..., yn_1) из У"”1. Возьмем множество Vй1,..., уп-1) и переобозначим его в Vе*. Пусть у,- = (у/,..., у") (t = = 1,?), Va = {yi,...,у*}, где записи упорядочены по возрастанию последней координаты. Построим граф изображенный на рис. 3.21. Уберем нагрузку листа а и объявим его обычной вершиной, после чего отождествим его с корнем графа U'a, т. е. U‘а будет расти из а.

Проделаем такую операцию для каждого листа графа ?/n-i и полученный в результате граф обозначим U.

Покажем, что граф U разрешает задачу /.

Пусть ос — произвольный лист графа Un- и пусть ему соответствовал вектор (у1,.. •, уп-1) из Уп . Переобозначим множество

Хп(у---,Уп~1) в Ха.

Возьмем произвольный запрос х = (xi,...,xn) е Xdom. Рассмотрим два случая.

Первый случай: существует такой лист а графа {/п-ь что х G Xе*. Это означает, что запрос х достигнет листа а и ни в какие другие листы графа ?/n-i не попадет, так как для любых различных а', а" € C(Un-1) справедливо Ха П Ха = 0. Из листа а исходит цепочка, вершинам которой сопоставлены записи из множества Vn(y..., yn_1), а это множество есть не что иное, как множество всех записей из V, у которых г-я координата не превышает у* (г = 1, п - 1). То, что х G Ха, означает, что у1 — ближайшая слева точка к х в М у2 — ближайшая слева точка к хг в М21), которое представляет собой проекцию на вторую координату множества V2(y1), и т.д. Таким образом, множество Vn(y1,..., yn_1) содержит все те и только те точки из V, которые удовлетворяют первым гг — 1 неравенствам (3.14). Далее запрос х продвигается вдоль цепочки, растущей из а, пока записи из Vn(y1,..., yn_1) не больше по последней координате, чем х„. Тем самым ответ на запрос х будет содержать только те записи, которые удовлетворяют запросу, причем все такие записи.

Второй случай: для любого a G C(Un-) запрос х ^ Ха. Это означает, что запрос не дойдет ни до одного из листьев графа (/п-ь и, значит, ответ на запрос х будет пуст. Осталось показать, что при таком х в библиотеке V не содержится записей, удовлетворяющих х.

Пусть i G {1,п - 1} — такой номер, что существует такой набор (у1,..., у*-1) из У*”1, что х € Xх..., у*”"1), и для любого набора (у1» • - - > У*) из У* запрос х ? -ЛГ*+11,... ,у*). Очевидно, что такой номер есть, так как х 6 X1 = Xdom• Так как для некоторого набора (у1,..., у*”1) из У*-1 выполняется х € -ХДу1,... ,у*-1) (очевидно, что такой набор только один), то запрос х пройдет в лист 7 графа Ui-u которому соответствует набор (у1,...*у*”1) (если i = 1, то в качестве 7 рассматривается корень графа U). Из листа 7 растет граф, который решает вторую задачу о близости для множества Мг..., у*-1), и так как для любого набора (у1,..., у*) из У* запрос х & Хг+1... ,у*), то это, значит, что х, меньше чем любая точка из М'(у ..., у*-1), т. е. в множестве V*(y..., у*”1), которое состоит из записей, удовлетворяющих первым i — 1 неравенствам из (3.14), не найдется ни одной точки, t-я координата которой не больше чем х,. Следовательно, в V нет записей, удовлетворяющих запросу х.

Тем самым мы показали, что граф U разрешает задачу I.

Подсчитаем сложность графа U.

Рассмотрим произвольный лист а графа Un~. Пусть ему соответствовал вектор (у1,... ,yn_1) из Уп_1. Цепочку ребер, растущую из а, обозначим через U'a. Переобозначим множество УЛ1,..., уп_1) в Vay а Хпу"-1) в Ха.

Легко видеть, что сложность графа U'а равна

откуда

Подсчитаем объем графа U. Для этого оценим величины Yq, где q = 1,п. Понятно, что если библиотека V такова, что ее проекция на любую ось координат имеет мощность А:, то величины Yq будут достигать максимума, и в этом случае эти величины будут зависеть только от к и q. Покажем индукцией по у, что для такого рода библиотек Yq =

Базис индукции, q = 1. Тогда

Индуктивный переход. Пусть для любого i € {1,д — 1} справедливо |У*| = Напомним, что по построению количество листьев

в графе Uq равно |У*|. Рассмотрим граф U. Пусть У1 = М1 = = {yi,..., у*}, где yi < Уг < • * • < У к- Обозначим через о;* лист графа U, которому соответствует точка у, , а через U? — подграф графа Uq, растущий из листа а*. Легко заметить, что U? и Uq- изоморфны как графы при А; = г и, значит, число листьев графа Uпо предположению индукции равно Откуда число листьев графа Uq равно

Последнее равенство можно найти в качестве упражнения, например, в (13, стр. 262].

Тем самым мы показали, что для любой библиотеки V и любого q Е {1, гг} величина

По построению графа U легко видеть, что объем графа U равен объему графа Un~ плюс количество листьев в графе U, так как помимо ребер графа Un- в графе U есть только ребра, ведущие в листья, и на каждый лист приходится ровно одно ребро. По аналогии с тем, как мы определяли число листьев в графе Uq, легко показать, что число листьев графа U равно |УП|. Следовательно,

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

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