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

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

В данном разделе мы будем исследовать параллельное решение задачи поиска с отношением линейного предпорядка, т. е. задачи поиска типа 5«п, описанной в разделе 3.3.

В данном разделе мы докажем следующие теоремы.

Теорема 36. Для любого натурального числа т и любой ЗИП I типа Sun существует т -оптимальный ИГ над базовым множеством То = (/С, 0).

Пусть V = {з/ь... ,Ук} — такое упорядоченное множество, что

Обозначим

Тогда через R(m, V) обозначим функцию, принимающую вещественные значения, определяемую рекуррентно следующими соотношениями:

где Vj = У = 1»JOТеорема 37. Для любого натурального числа т и любой ЗИП I

I = (X, V, У) типа Sun, такой, что V = {з/ь •. •, у*} — такое

i i i

упорядоченное множество, что у к У у к-1 У ••• У Уъ существует оптимальный в классе т-сепаративных граф над базовым множеством — (1C, 0) и

где R(m,V)функция определяемая соотношениями (3.9), (3.10).

Эта теорема по сути дает описание способа оптимального разделения данных между исполнителями при использовании сепаративного подхода для задачи типа Snn, причем из данной теоремы видно, что для определения этого оптимального разделения необходимо полиномиальное время, где степень полинома равна числу исполнителей.

Теорема 38. Существуют такое натуральное число т и такая ЗИП I типа Sun, что любой т-оптимальный для ЗИП I граф над базовым множеством То = (/С,0) не принадлежит классу т- сепаративных.

I

Существование оптимального графа. Если а, 6 G X и а У 6, то будем говорить, что а не меньше чем 6, и Ь нс больше чем а.

i I

Если a,b € X иаУЬиЬУа, то будем говорить, что а и b равны и писать а = 6.

Отношение равенства “=” делит все множество X на классы эквивалентности. Выберем произвольно из каждого класса по одному элементу и назовем представителем класса. Понятно, что если а = = 6, то Ка(х) = Кь(х) = Кс(х), где сX — представитель класса, которому принадлежат а и 6.

I

Если а, 6 € X маУЬиафЬ, то будем писать а >- b и говорить, что b предшествует а, или 6 меньше а, или а больше 6.

I

Если a, b G X и b У а, то обозначим

и

Если М С X, то минимальным элементом множества М назовем

I

такой элемент х € М, что для любого х' 6 М выполнено х' У х.

Через xmin обозначим представителя класса минимальных элементов множества Ху а через xmoz обозначим представителя класса

I

эквивалентности таких а, что для любого хX а У х.

Далее всюду будем считать, что элементы xmin и хтах существуют, хотя если в X таких элементов нет, например, в случае открытого множества, то в качестве хт*п и хтах можно взять граничные точки, поскольку далее xmtn и хтах используются только как обозначения объекта, не меньше которого (соответственно не больше которого) любой элемент из X.

Так как для любых /, д 6 АС справедливо f V д € JC и / & р ? /С, то для любого ребра с произвольного графа U над базовым множеством То Функция состояния ребра с ?с € АС.

Назовем ИГ U над базовым множеством Tq правильно нагруженным графом, если для любого ребра с графа U нагрузка ребра с равна [с] = Сс = Кау где а — представитель соответствующего класса эквивалентности.

Лемма 34. Для любого натурального числа т и любого ИГ U над базовым множеством Tq = (АС, 0) существует такой правильно нагруженный граф U', что Tn(f/,m,x) = Tn(Umyx) и функционирование графов U и U' совпадает.

Доказательство. Пусть нам дан граф U. Заменим нагрузку каждого ребра с графа U на функцию Ка = ?с, где а — представитель класса элементов 6, для которых Кь = Сс- Полученный граф обозначим через U1. По определению U' — правильно нагруженный граф. Поскольку произведенная замена нагрузочных функций не меняет функций фильтра вершин графа, то очевидно, что функционирование графов U и U' совпадает.

Поскольку вектора состояния графов U и U' совпадают (нагрузка каждого ребра графа U' определялась как функция состояния ребра графа U) у то очевидно, что для любого запроса х 6 X

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

Пусть U — произвольный правильно нагруженный ИГ над базовым множеством Tq. Пусть а1,..., Ка<1} — множество нагрузочных

i i I

функций графа U, упорядоченное так, что aq У aq-1 У ••• У а. Тогда упорядоченное множество {ai,...,aq} назовем определяющим множеством правильно нагруженного графа U.

Легко видеть, что так как граф U правильно нагруженный, то для любого г € {1,д—1} выполнено а* ф at+i и, значит, aq У aq-1 У ••• У а.

Лемма 35. Для любого натурального числа т и любого правильно нагруженного ИГ U над базовым множеством То = (/С, 0), если {ai,..., aq} — определяющее множество графа U и ао = хт%П9 a$+i = = Хтах> то для любого i € {ri,7*2}, где

и для любых Х,Х2 6 [aj,a,+i) справедливо

Доказательство. Возьмем произвольное число i € {гх,Г2} и два произвольных запроса xi,X2 6 [a*,^*+i)- Так как для любого j 6 6 {и,г} выполнено Kaj(x 1) = Kaj(x2) = 1 и для любого j € {г + 1,д} выполнено Kaj(x) = Kaj(x2) = 0, а других нагрузочных функций в графе U нет, то векторы состояния графа на запросах х и хг совпадают, следовательно, процедура обхода будет вести себя одинаково на запросах х и Х2 и, значит,

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

I

Пусть I = (X, У, >:) — ЗИП типа Sun. Тогда упорядоченное множество {ai,...,ar} (ar >- ar_i >-•••>- а) представителей классов эквивалентности записей из У назовем опорным множеством задачи I.

Понятно, что г ^ |У|.

Если I — произвольная ЗИП типа S/,n, то правильно нагруженный ИГ U 6 U(I,To), определяющее множество которого совпадает с опорным множеством ЗИП /, назовем приведенным графом задачи I.

Лемма 36. Пусть Iпроизвольная ЗИП типа Бцп. Пусть U — произвольный ИГ над базовым множеством То = (АС,0), разрешающий ЗИП I. Тогда для любого натурального числа т существует такой приведенный ИГ U' задачи /, что для любого х € X

Доказательство. Согласно лемме 34 существует правильно нагруженный граф функционирование которого совпадает

с функционированием графа U и Tn{U, т, х) = Tn(U", тух). Пусть — определяющее множество графа U”. Предположим, что в этом множестве существует элемент bj, не принадлежащий опорному множеству задачи I. Выделим все ребра графа U", которым соответствует нагрузочная функция Кь5 • Рассмотрим отрезки

[6j_i,6j) и [6j,6j+i). Если какого-то из этих отрезков нет, то он и не рассматривается. Согласно лемме 35 для любого х[bj-,bj) Тп(U",m,x) является константой, которую обозначим через tj-, и для любого х 6 [6j, bj+1) Tn(U",m,x) также является константой, которую обозначим через tj. Если tj-1 ^ tj, то заменим в графе U" нагрузку выделенных ребер на KbJ+ll иначе на К^_х. Полученный граф обозначим U”'.

Так как bj не принадлежит опорному множеству ЗИП I, то проводимость выделенных ребер не определяла ни одну из функций фильтра листьев, следовательно, после произведенной замены функционирование графа сохранится, т. е. граф U,n по прежнему разрешает задачу I.

Покажем, что для любого хX выполняется Тц(иш,т,х) ^ ^ Tn(U",m,x).

Понятно, что для любых запросов х # [bj_i,6J+i) выполняется Tn(U"m,x) = Ti(U",m,x), так как для этих запросов х вектора состояния графов Um и U" совпадают. Если у выделенных ребер нагрузка была заменена на Kbj+1 > то для любого х ? [bj-i, bj+) вектор состояния графа U,n будет совпадать с вектором состояния графа U" при х[bj-iybj), т.е. если tj- ^ tj, то для любого х[bj-i,bj+) Тц(и,п,тп,х) = tj-1. Если у выделенных ребер нагрузка была заменена на Kbj_,, то для любого х ? [6у_1, fcj+i) вектор состояния графа U'" будет совпадать с вектором состояния графа U" при х G [bj,bj+1), т. е. если tj-1 > tj, то для любого х € [6у_i, 6j+i) выполнено Tu(U"', m, х) = = tj. Откуда следует, что для любого хX получим Tx(U,n,m,x) ^ ^ Tu{Un,m,x).

Отметим, что элемент bj не принадлежит определяющему множеству графа U'". Тем самым мы избавились от одного “лишнего” элемента. Если в определяющем множестве графа U'" есть элемент, не принадлежащий опорному множеству задачи I, то действуем по отношению к нему точно так же, как к элементу bj. И таким образом, за конечное число шагов мы придем к графу U'r который разрешает задачу I, определяющее множество покрывается опорным множеством задачи 1, и для любого хX выполнено Tn(U"',m, х) ^ n(U",m,x).

Осталось показать, что любой элемент а, принадлежащий опорному множеству ЗИП /, принадлежит определяющему множеству графа U^r

Возьмем произвольный элемент а из опорного множества ЗИП I. Так как U^ разрешает ЗИП I, то в графе существует такой лист а, что ему приписана запись у, равная а, и а(у) = 1. Следовательно, так как N^a С N^a, то а) = Ка(х). Значит существует ребро, ведущее в а, через которое в а проходит запрос у, отсюда поскольку граф Uправильно нагруженный сразу следует, что этому ребру приписан предикат Ка. Следовательно, а принадлежит определяющему множеству графа U

Лемма доказана.

Лемма 37. Если U такой правильно нагруженный ИГ над базовым множеством То = (АС,0), что {ai,...,aQ} — его определяющее множество, I € {l,q} — такой номер, что

иг — число ребер графа U, нагрузка которых принадлежит множеству {Kai,. ..,Kai,Kat+l} (если I = q, то последний элемент отбрасывается), то для любого натурального числа т

Доказательство. Так как U — правильно нагруженный граф, то ребра, которым приписаны функции Kai+l (если I < q) исходят из вершин, функции фильтра которых принадлежат множеству аг>... ,KQl}. Следовательно, для любого запроса х 6 [аьятах] нагрузки по крайней мере г ребер графа должны быть вычислены. А поскольку имеется m исполнителей, то для любого запроса х

€ [о;,а:тож] по крайней мере один исполнитель вычислит Jфункций, т.е. для любого запроса х € [a/,xmax]

Отсюда

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

Если V = {t/х,... , у*}, где записи упорядочены следующим обра- i i I

зом: yk У ук-1 У • • • У Уи то цепочку нагруженных ребер, изображенную на рис. 3.17, назовем правильной цепочкой для множества V.

Рис. 3.17. Правильная цепочка Доказательство теоремы 36.

Возьмем произвольное натуральное число т и произвольную ЗИП I

I = (X, V, типа Sun. Пусть {ai,...,ag} — ее опорное множество.

Если P((ai,xmai]) = 0, то правильная цепочка для множества V разрешает ЗИП I и m-оптимальна, поскольку ее m-сложность равна 1, а сложность любого графа всегда не меньше 1, так как из корня исходит по крайней мере одно ребро, и хотя бы одну функцию всегда надо вычислить.

Рассмотрим теперь случай, когда P([ai,xmax]) > 0.

Для доказательства существования m-оптимального графа для ЗИП /, покажем, что инфимум в выражении

берется по конечному множеству.

Согласно лемме 36 для любого графа над базовым множеством То, разрешающего ЗИП /, существует приведенный граф не большей сложности, разрешающий ЗИП I. Поэтому инфимум в выражении (3.11) можно брать по множеству графов, нагрузка ребер которых берется из множества {KaiJ..., Kaq).

Существует такой номер I € {1,д}, что

Обозначим

I

Рассмотрим ЗИП V — (X, где V — есть множество записей

из V, равных элементам из {ai,...,a*}. Возьмем произвольный ИГ Uq над базовым множеством То, разрешающий ЗИП Г. Такой ИГ обязательно существует, так как То полно для типа 5цп, например, правильная цепочка для множества V разрешает задачу.

Согласно лемме 37 любой правильно нагруженный граф, разрешающий ЗИП нагрузка ребер которого берется из множества ах,..., Kat}, и имеющий более

ребер будет иметь сложность большую чем Тп(С/о> ш). Отсюда следует, что инфимум в выражении (3.11), но для ЗИП нужно брать по множеству правильно нагруженных графов, имеющих не более го ребер, нагрузка ребер которых берется из множества ах,..., Kat}. Но таких графов конечное число, следовательно, существует т- оптимальный граф, разрешающий ЗИП Г.

Если I < q, т. е. если ЗИП Г отличается от ЗИП /, то возьмем произвольный m-оптимальный граф U разрешающий ЗИП Г. Выберем в нем некоторый лист, которому соответствует запись из V', равная aj+i. Выпустим из этого листа графа правильную цепочку для множества V V. Эта цепочка будет иметь нулевую сложность, а полученный граф разрешать ЗИП I. Так m-сложность полученного графа равна сложности m-оптимального графа U то полученный граф будет m-оптимальным для ЗИП I.

Тем самым, теорема 36 доказана.

Оптимальный граф в тслассе сепаративных.

Если га — некоторое натуральное число, I — некоторая ЗИП типа Sun и граф UU{l>Tо) такой, что для любого ИГ U' € о)

и любого хX

то скажем, что граф U равномерно га-минимальный для ЗИП I.

I

Лемма 38. Для любой ЗИП I = (X, V, У) типа Sun правильная цепочка для множества V является равномерно 1-минимальным графом.

I

Доказательство. Возьмем произвольную ЗИП / = (X, И, У) типа Sun-

Нижняя оценка. Пусть {ai...,a9} опорное множество задачи I. Пусть li (г = 1,д) — количество записей из И, равных а*. Обозначим do — хт{п. Рассмотрим функцию

Покажем, что для любого ИГ U' € U(I,Fq) и любого х G X

Рассмотрим произвольный ИГ U'U(I,To). Согласно лемме 36 существует такой приведенный граф U" G U(Iy .Fo), что любого хX

Так как U" приведенный граф, то его определяющее множество имеет вид {ai..., aq}.

Если ai >- xminy то возьмем произвольный запрос х € [xmjn,ai). Поскольку из корня графа U" исходит по крайней мере одно ребро, то хотя бы одну функцию надо вычислять, и, значит,

Возьмем произвольное число i G {1,9 — 1} и произвольный запрос х € [aj,dj+i). Так как U" разрешает ЗИП /, то такой запрос должен дойти до листьев, записи из V, приписанные которым, предшествуют

i

а*+1 (эти листья назовем выделенными). Таких записей будет h-

j=i

Поскольку в каждый выделенный лист запрос проходит по некоторому ребру, то должен быть подсчитан предикат, приписанный этому

г

ребру. Следовательно, должно быть подсчитано по крайней мере lj

i=i предикатов. Кроме того должно быть хотя бы одно ребро, исходящее из вершин, функция фильтра которых равна 1 на запросе я, и ведущее в невыделенную вершину, поскольку в противном случае не будет ребра, через которое можно пройти к листьям, которым соответствуют записи из V, равные a<+i. Это добавляет еще одну 1 к числу вычисленных функций. Таким образом, при я ? [а*,а*+х)

Возьмем произвольный запрос х ? [a-qixmax. Такой запрос должен дойти до всех записей из V А поскольку к каждой записи мы попадем по некоторому ребру, а всего записей |V|, то при х ? [aq,xmax]

Таким образом, мы показали, что при любых х ? X

Верхняя оценка. Простой проверкой легко убедиться, что правильная цепочка для множества V (обозначим ее через Uo) разрешает ЗИП/иТп(*Уо,1>*) = 7о(х).

Отсюда с учетом нижней оценки имеем, что правильная цепочка для множества V является равномерно 1-минимальным графом для ЗИП I.

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

Лемма 39. Для любого натурального числа т и любого т-сепаративного ИГ U над базовым множеством То = (/С, 0) суще- ствует такой т-сепаративный правильно нагруженный граф U', что 2п(?/,т,я) = Тц(Цтух) и функционирование графов U и U совпадает.

Доказательство. Для доказательства леммы достаточно убедиться, что правильно нагруженный граф U построенный для графа U в доказательстве леммы 34, является m-сепаративным. А это действительно так, поскольку для любого х ? X вектора состояния графов U и U' совпадают.

Лемма доказана.

Лемма 40. Пусть I — произвольная ЗИП типа Sun. Пусть U — произвольный т-сепаративный ИГ над базовым множеством То = = (?,0), разрешающий ЗИП I. Тогда для любого натурального числа т существует такой т-сепаративный приведенный ИГ U' задачи /, что для любого х ? X

1

Доказательство. Доказательство леммы аналогично доказательству леммы 36 и надо только убедиться, что построенный в доказательстве леммы 36 граф U!" является m-сепаративным. В самом деле, вектора состояния графа U”' и m-сепаративного графа U” совпадают на всем X, кроме отрезка [6j-i,6j+i), но поскольку вектор состояния графа U,n на этом отрезке совпадает с вектором состояния графа U" на одном из отрезков [bj-i,bj) или [bj, 6*4.1), на котором сохраняется свойство m-сепаративности, то граф U,n остается т-сепаративным.

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

Лемма 41. Для любого натурального числа т и любой ЗИП I типа Siin существует оптимальный в классе т-сепаративных граф над базовым множеством То = (/С, 0).

Доказательство. Доказательство леммы аналогично доказательству теоремы 36, но только вместо лемм 34 и 36 надо воспользоваться леммами 39 и 40.

Лемма доказана.

Систему подмножеств V,..., Vn некоторого множества V назовем разбиением V, если V U Vi U • • • U Vn = V и для любых г, j 6 {1, п} из того, что t ф j следует V* П Vj = 0.

Если V,..., Vn разбиение некоторого множества V> то ИГ, составленный из п правильных цепочек для множеств Vi,...,К» соответственно, растущих из одного общего корня, назовем правильной п- метелкой разбиения Vi,..., Vn.

Лемма 42. Для любого натурального числа т и любой ЗИП I

I = (X, V, У) типа Бцп существует такое разбиение множества V, что правильная метелка этого разбиения будет оптимальным в классе т-сепаративных графом над базовым множеством То = = (X, 0) для задачи I. [1]

подграфы U,...,Um будут пересекаться только в корне. Нетрудно убедиться, что полученный граф разрешает ЗИП / и сложность его такая же, что и у исходного.

Теперь, если некоторая запись у приписана нескольким листьям, принадлежащим разным подграфам {/,*,,... , ?/^, то выберем среди них один такой, лист с записью у которого имеет функцию фильтра, равную Ку. Такой подграф обязательно найдется. У остальных подграфов листья с записью у объявим обычными вершинами и снимем с них нагрузку у. Такую операцию проделаем для всех записей приписанных разным подграфам и в результате получим граф с тем же функционированием и сложностью, в котором каждая запись из V приписана только одному из подграфов U,..., Um. Поэтому, если через Vi (г = 1 >т) обозначить записи, приписанные листьям подграфа Uij то система Vi,..., Vm образует разбиение множества V.

Если х — некоторый запрос из X, то обозначим через Ti(x) количество вычисленных t-ым исполнителем предикатов при подаче на вход процедуры обхода запроса х. Легко видеть, что 7* (ж) — это 1-сложность графа {/*. Если через TjP(x) обозначить 1-сложность правильной цепочки для множества Vi, то согласно лемме 6 для любого х ? X имеем 7*(ж) ^ Т°(ж). Отсюда если, через Uo обозначить правильную m-метелку разбиения то получим, что

Отсюда поскольку граф U оптимальный в классе тп-сепаративных для ЗИП /, то и граф Uo оптимальный в классе m-сепаративных для ЗИП /.

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

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

Высотой ИГ назовем длину самой длинной ориентированной цепи, исходящей из корня ИГ.

Лемма 43. Пусть U — правильная т-метелка некоторого раз- биения V|,..., Vm- Пусть h — высота ИГ U. Пусть Ь{ (г = 1, h - 1) — минимальный элемент множества записей, приписанных листьям i-го яруса, из которых исходят ребра, и Ьо = хты- Тогда

и

Доказательство. Сначала отметим, что поскольку метелка правильная и в каждой цепочке записи идут в порядке возрастания, то i l I

bh Ь Ь/1-1 h ••• t. h.

Если bi У х, то запрос либо не проходит в вершины первого яруса, либо проходит в те из них, из которых не исходят ребра. Следовательно, в этом случае Тп({/, то,х) = 1.

Возьмем произвольное г € {1,Л — 2} такое, что 1) ф 0.

i

Возьмем произвольный запрос х (Е [&i,6i+i). Поскольку х У bi, то запрос дойдет до вершины, которой приписана запись bi (если i = О, то до корня). С другой стороны bi+i У х, следовательно, х либо не пройдет ни в какую вершину (г + 1)-го яруса, либо пройдет только в те из них, из которых не исходят ребра. Значит при х € [6[2], )

имеем 7п(?/, m, х) = 1 + г.

I

И наконец, если х У бд+i, то все h предикатов некоторой самой длинной цепи будут вычислены и, значит, Т[2]п([/, m, х) = h.

Отсюда следует

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

Зафиксируем число исполнителей т ^ 1.

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

Пусть нам дана произвольная правильная m-метелка. Занумеруем ее листья подряд, начиная с 1, следующим образом:

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

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

Рис. 3.18. Правильная 4-метелка с номерами листьев

Пусть U — правильная m-метелка высоты Л, тогда последовательность чисел • • • ytfc-i) назовем кодом т-метелки U, если ij

есть минимальный номер вершины j-го яруса, из которой исходит ребро (j = l,h - 1).

Например, правильная m-метслка, изображенная на рис. 3.18, имеет код (1,6,11,12).

Пусть U — правильная m-метелка некоторого разбиения библио-

/ i I

теки V = {yi,...,2/*}> гДе Ук >1 Ук-1 t h Уи тогда U назовем простой m-метелкой, если для любого г ? {1, Л:} листу с номером г соответствует запись pi.

i i I

Например, если угз У у12 У ••• >; ух, то правильная т-метелка, изображенная на рис. 3.18, является простой.

Лемма 44. Пусть т — произвольное натуральное число uUq — простая т-метелка с кодом разбиения V

библиотеки V. Тогда для любой правильной т-метелки U с тем же кодомх, г2,..., t^-i) того же разбиения Vi,..., Vm библиотеки V и для любого запроса х G X справедливо

Доказательство. Обозначим yio = xmtn. Пусть V = {yi,...,yk},

i i i

где у к h Ук-i Ь * * • h Уи тогда согласно лемме 43

Возьмем произвольную правильную m-метелку U с кодом (n,i*2,. •., разбиения Vi,..., Vm библиотеки V. Пусть у^ —

минимальный элемент множества записей, приписанных листьям j-ro яруса, из которых исходят ребра, в m-метелке U (j = l,/i — 1). Пусть yi0 = xmin. Тогда согласно лемме 43

Поскольку вдоль каждой цепочки графа U записи идут в порядке возрастания, то для любого j € {1, Л — 1} ij ^ lj. В самом деле если предположить, что для некоторого j 6 {1, Л — 1} ij < lj, то, следовательно, на (j + 1)-ом ярусе есть лист а, которому приписана запись уя, где q < ij, но это сразу означает, что и на j-ом ярусе есть лист 0, которому приписана запись уя>, где q' < q < ij, причем из листа 0 исходит ребро (0, а). Противоречие.

Отсюда с учетом выражений (3.12), (3.13) получается утверждение леммы.

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

Доказательство теоремы 37.

Возьмем произвольное натуральное число т, которое будет опре-

i

дел ять число исполнителей. Возьмем произвольную ЗИП I = (X, У,У) типа Siin, такую, что V = {yi, - • - ,Ук} — упорядоченное множество, l i I

такое, что ук Ь Ук-i h * * * Ъ Уи

Согласно лемме 41 для ЗИП I существует оптимальный в классе m-сепаративных граф над базовым множеством То = (АС,0).

Согласно леммам 42 и 44 оптимальный в классе тп-сепаративных граф надо искать в множестве простых m-метелок. Используя этот факт, докажем индукцией по числу т, что

где R(m, V) — функция определяемая соотношениями (3.9), (3.10). Базис индукции, т = 1.

Согласно лемме 38 правильная цепочка U множества V будет 1-оптимальной для ЗИП /. Согласно лемме 43

Индуктивный переход. Пусть для любого натурального I < т I

и любой ЗИП Г = (X, V, У) типа Sun справедливо

Докажем справедливость утверждения для числа т и ЗИП I. Поскольку оптимальный в классе m-сепаративных граф надо искать в множестве простых m-метелок, будем перебирать простые т- метелки в зависимости от длины первой цепочки. Поскольку ее длина минимальна, то, значит, она может изменяться в пределах от 1 до

[*/”»]? _

Возьмем произвольное число j G {l,[A;/m]}. Пусть Uj — простая m-метелка для множества V, у которой длина первой цепочки равна j, и которая имеет минимальную m-сложность среди всех простых m-метелок для множества К, у которых длина первой цепочки равна j. Согласно лемме 43 ее m-сложность равна

где Tn(Ujt т—1) — (m—1)-сложность подграфа Uj, который состоит из m—l подцепочек всех цепочек, кроме первой, начинающихся с (J — 1)- го яруса графа Uj. Здесь берется (тп — 1)-сложность потому, что обрабатывать эту подграф Щ будет уже т - 1 исполнитель, поскольку первый исполнитель завершает на этом свою работу. Поскольку Uj имеет минимальную m-сложность среди всех простых m-метелок для множества V, у которых длина первой цепочки равна j, то нетрудно заметить, что

где I* = (X,VU~Vm+*t), и vO-Dm+i = {y0_1)m+2(,_1)т+3.....у*}.

Откуда согласно предположению индукции получим

Отсюда

Тем самым, теорема 37 доказана.

Неоптималъпостъ сепаративных графов.

В данном разделе мы докажем теорему 38, т. е. приведем ситуацию, в которой оптимальный граф не является сепаративным.

Пусть X = У = [0,1] — отрезок вещественной прямой. Пусть отношение поиска есть отношение “>” для вещественных чисел. Пусть на X задана равномерная вероятность, т. е. вероятность отрезка равна его длине. Тогда для любого у € X

Пусть число исполнителей т = 2. Рассмотрим некоторую библиотеку V = {2/1,..., Уб}» в которой записи упорядочены по возрастанию, т. е. у < г/2 < •** < 2/6- Рассмотрим ЗИП I = (X, V, >). Согласно теореме 37 сложность Т5(/, 2) оптимального в классе 2-сепаративных графа равна максимуму из трех чисел:

Рассмотрим граф С/*, изображенный на рис. 3.19, где порядок следования ребер в пучке корня следующий: первым идет ребро, ведущее в у4, вторым — в у2, и последним — в У.

Рис. 3.19. Граф U*

Очевидно, что граф U* разрешает ЗИП I.

Применив процедуру обхода, легко проверить, что Tn(U*,2,x) = 2 при х е (0,у4) и Тп(С/*,2,х) = 3 при х € [у4,1]. Отсюда

Согласно процедуре обхода при х € (0,2/5) ребро, ведущее из корня в вершину с записью t/i, просматривается первым исполнителем, а при х G [2/5* 1) — вторым. Следовательно, граф U* не является 2-сепаративным.

Возьмем теперь yi = 0.05, У2 = 0.1, уз = 0.15, у4 = 0.8, ys = 0.9, у6 = 1. Тогда Ti = 3.05, Т2 = 2.25, Т3 = 2.8, Tn(U 2) = 2.2. Откуда следует, что для такой задачи I любой 2-сепаративный граф не может быть 2-оптимальным.

Теорема 38 доказана.

/

  • [1] Доказательство. Возьмем произвольную ЗИП I = (X, У,У) типаSun. Согласно леммам 40 и 41 для I существует приведенный оптимальный в классе m-сепаративных граф, который обозначим через U. Обозначим через Ui (г = 1,ш) подграф графа (/, составленныйтолько из ребер, которые хотя бы на одном запросе из X окрашиваются процедурой обхода г-ым исполнителем. Поскольку граф Um-сепаративен, то реберное пересечение подграфов Ui невозможно,но подграфы Ui могут пересекаться по вершинам. Предположим, чтонекоторые подграфы C/tl,... ,Uit пересекаются но вершине а. Продублируем I раз вершину а (если это лист, то дублируем с нагрузкой) поодной на каждый подграф Uixи тем самым ликвидируем этовершинное пересечение подграфов. Такую операцию проделаем длявсех вершин пересечения кроме корня и в результате получим, что
  • [2] листья, принадлежащие ярусу с меньшей высотой имеют меньшие номера,
  • [3] листья, принадлежащие ярусу с меньшей высотой имеют меньшие номера,
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы