Нижняя оценка сложности включающего поиска

В данном пункте нам понадобится теорема Краскала-Катоны, приведенная, например, в работах [166, 172, 173, 175]. Переформулируем ее в удобных для нас терминах.

Теорема 25 (Краскала-Катоны). Пусть — т-й слой куба В^п и, А С В^. Пусть R (A) = {a G B^_+l: (ЗР 6 А: а У Р)}. Тогда минимум |Я (Л)| достигается, если А — начальный отрезок слоя В^, причем в этом случае R (A) — начальный отрезок слоя B^+i •.

b b

Если A 6 Bⁿ, то обозначим 0(A, >:) = (J 0(lf" b);

y (=A

Приведем одно простое следствие.

Следствие 11 (теоремы Краскала-Катоны). Пусть А С В ь

тогда |0(А, >^)| достигает минимума, если, А — начальный отрезок слоя В^.

ь

Лемма 17. Пусть I = (В^п, V, h) ^— ЗЯЯ типа Sbooi• Пусть U — разрешающий ЗИП 1 ПИГ над базовым множеством Т — (АЛ^П, 0), где М^п — множество монотонных булевых функций от п переменных. Тогда существует такое разбиение библиотеки V на непересекающиеся части, что

• • каждая часть содержит записи одного веса, и этот вес назовем весом части;
• • каждой части веса т > 0 и мощности t можно поставить в соответствие такую совокупность ребер графа U, что сумма сложностей ребер из этой совокупности не меньше чем t • 2^1-тп, причем образы различных частей при этом соответствии не пересекаются.

Доказательство. Пусть V = {2/1,…, у*}.

Отметим, что если у* € V — запись веса т, то |0(у,-, >:)| = 2^{п т}

так как 0(у, >:) — (п — т)-мерная грань куба В^п.

Обозначим через А¹_т начальный отрезок длины I т-го слоя куба В^п. Легко видеть, что если I ^ п — т + 1, то.

Так как для любой записи у* € V выполняется 0(у*, Ь) Ф 0> ^то согласно следствию 10 из теоремы 21 о существовании главных цепей для любой записи yi? V в графе U существует главная цепь записи yi, которую обозначим через С{. Лист из Ьц (у{), в который ведет эта цепь, будем обозначать оц (г = 1 , к).

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

Рассмотрим произвольную запись yi € V (г € {1, А:}), которая на момент рассмотрения не попала ни в какую часть разбиения. Пусть ее вес равен т > 0. Пусть Д- ф а* — ближайшая к а* вершина в цепи С{, через которую также проходит главная цепь какой-то другой записи.

Такая вершина ft обязательно существует, в крайнем случае, ft — корень графа ?/, так как все главные цепи начинаются в корне. Пусть 7i — вершина графа, в которую ведет ребро цени Cj, исходящее из ft. Разберем возможные случаи.

Случай 1. Пусть ft — корень графа U. Тогда ребро (ft, 7*) имеет сложность 1. Мы заведем новую часть разбиения, состоящую из одной записи у*, и сопоставим этой части ребро (ft, 7″).

Случай 2. Предположим теперь, что ft не является корнем графа ?/, но совпадает с каким-либо листом aj, где j G {1, к} {г}. Легко заметить, что так как С{ и Cj — главные цепи, то вес записи yj меньше веса записи у" и, следовательно, сложность ребра (ft, 7″) не меньше чем 2^1_тп. Мы заведем новую часть разбиения, состоящую из одной записи у", и сопоставим этой части ребро (ft, 7*).

Случай 3. Пусть теперь ft не является корнем графа U и не совпадает ни с каким листом ocj. Пусть Cj_l,…, Cj_q — множество главных цепей записей, проходящих через вершину ft.

Случай 3.1. Пусть среди записей у₇₁,…, yj_q существует запись, вес которой меньше т. Тогда сложность вершины ft не меньше чем 6 6.

P (0(yj,>;)) = 0{Vj, i Ы½^П ^ 2^{1 m} и, следовательно, сложность ребра (ft, 7i) не меньше чем 2^1_т. Мы заведем новую часть разбиения, состоящую из одной записи j/j, и сопоставим этой части ребро (ft, 7*).

Случай 3.2. Предположим, что среди записей у₇₁,…, yj_q не существует записи, вес которой меньше т. Пусть в множестве {у₇₁, • • •, 2/j,} имеется t записей веса т таких, что в главных цепях этих записей между вершиной ft и листом, в котором заканчивается цепь, нет вершин пересечения с другими главными цепями записей. Понятно, что t ^ 1. Обозначим это множество записей через V и объявим его новой частью разбиения. Понятно, что все записи из V' до данного момента еще не рассматривались, так как в противном случае запись у_{ уже оказалась бы в некоторой части разбиения. Понятно также, что для каждой записи y_s € V ft — ближайшая к q_s вершина в цепи С₅, через которую проходит главная цепь какой-то другой записи, причем, если у₉ — вершина, в которую ведет ребро цепи С₉₁ исходящее из ft, то ребро (ft, 7″) ^не принадлежит никакой другой цепи, кроме С₉. Сопоставим V совокупность ребер, состоящую из t ребер, исходящих из вершины ft и принадлежащих главным цепям записей из V и t' ребер, входящих в вершину ft и принадлежащих главным цепям записей из V (t' ^ t). Заметим, что сумма сложностей последних t!

ъ

ребер не меньше чем P (0(V >:)), и сложность вершины & не меньше ь

чем P (0(V'^/, ^)), следовательно, сумма сложностей ребер совокупно;

сти, сопоставленной части V не меньше чем (t + 1) • P (0(V^/, ^;)) =.

= 2 ⁿ(t 4- 1) • (V ^)|. Согласно следствию теоремы Краскала- 6 6.

Катоны (V >;)| ^ |0(А^, ^;)|. Следовательно, если t < п — т -f 1, то.

При t > п — т+1, поскольку для любой записи у € V справедливо.

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

Отметим, что по ходу построения соответствия мы для каждой записи у, 6 V (г 6 {1, А;}), нашли свои вершины ft и 7*, описанные выше.

Докажем одно полезное свойство.

Свойство 10. Если ft и 7^ — описанные выше вершины, соответствующие записи yi, то ребро (ft, 7t) принадлежит только совокупности ребер, соответствующей части разбиения, содержащей запись у".

Доказательство. Так как для любой записи у* 6 V совокупность ребер, связанная с записью у*, содержит только ребра либо входящие в ft, либо исходящие из ft, то ребро (ft, 7″) может попасть в другую совокупность ребер только в том случае, если вершина 7* совпадает с какой-то другой вершиной ft. Итак, пусть существует s € {1, Л:} {г} такое, что 7* = ft. Тогда 7* принадлежит цепи С₉, отличной от С", а так как 7″ в цепи С" ближе к листу а*, то согласно определению вершины ft вершина 7* должна совпадать с вершиной а*, а это сразу означает, что каждая из записей у₃, вершина ft которой совпадает с тi, подпадает под случай 2, и, значит, содержащая у₅ часть состоит из одной записи y_s и ей соответствует одно единственное ребро (ft, 7₅), не совпадающее с (ft, 7,).

Тем самым свойство 10 доказано.

Возьмем произвольную запись у, — € V. Покажем, что совокупность ребер, соответствующая части разбиения, содержащей запись у", не пересекается с образами никаких других частей разбиения.

Рассмотрим возможные варианты.

Вариант 1. Пусть существует sG {1, к} {*} такое, что ft =7,.

Тогда по тем же соображениям, которые описаны в доказательстве свойства 10, запись у* подпадает под случай 2, и, значит, содержащая yi часть разбиения состоит из одной записи у; и ей соответствует одно единственное ребро (ft, 7*), которое согласно свойству 10 принадлежит только совокупности ребер, соответствующей части разбиения, содержащей запись у,-.

Вариант 2. Пусть для любого s 6 {1, к} {г} выполняется ft ^7,.

Тогда возможны следующие подварианты.

Вариант 2.1. Для любого s€{l, fc}{i} вершина ft не совпадает с вершиной ft.

Отсюда следует, что все ребра, входящие в ft, нс принадлежат никаким совокупностям ребер, кроме, быть может, совокупности ребер, соответствующей части разбиения, содержащей запись у{. Кроме того, отсюда следует, что-либо запись уi подпадает под случай 3.1 алгоритма построения соответствия и тогда части разбиения, состоящей из одной записи у*, сопоставляется одно единственное ребро (ft, 7*), либо запись yi подпадает под случай 3.2 алгоритма построения соответствия, где параметр t принимает значение 1, и тогда части разбиения, состоящей из одной записи у*, сопоставляется два ребра: ребро (ft, 7i) и ребро, входящее в ft и принадлежащее цепи (ft. Следовательно, согласно приведенному выше замечанию и свойству 10, и в этом варианте совокупность ребер, соответствующая части разбиения, содержащей запись у*, не пересекается с образами никаких других частей разбиения.

Вариант 2.2. Существует s € {1, А:} {г} такое, что ft = ft.

Пусть V' = {yj_x,…, уу,} — подмножество записей из V таких, что ft_r = ft (г = 1,/). Так как мы находимся в условиях варианта 2, то все ребра, входящие в ft, не принадлежат никаким совокупностям ребер, кроме, быть может, совокупностей ребер, соответствующих частям разбиения, содержащим записи из V.

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

Вариант 2.2.1. В множестве V есть запись с весом, меньшим чем вес записи у".

Тогда запись у, подпадает под случай 3.1 алгоритма построения соответствия и части разбиения, состоящей из одной записи у,-, сопоставляется одно единственное ребро (ft, 7*), которое согласно свойству 10 принадлежит только совокупности ребер, соответствующей части разбиения, содержащей запись у*.

Вариант 2.2.2. В множестве V нет записей с весом, меньшим чем вес записи у".

Тогда запись у* подпадает под случай 3.2 алгоритма построения соответствия. Пусть V" С V — множество записей, вес которых совпадает с весом у*. Согласно алгоритму построения соответствия множество V^й образует одну часть разбиения, которой сопоставляется совокупность ребер, инцидентных вершине ft и принадлежащих главным цепям записей из V". Согласно свойству 10 и сделанному в варианте 2.2 замечанию, эти ребра не принадлежат образам других частей разбиения.

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

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

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

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

ь

Теорема 26 (нижняя оценка). Пусть I — (В^п, У, У) — ЗИП типа Sboob Пусть базовое множество имеет вид Т — (Л4^П, 0), где М^п — множество монотонных булевых функций. Тогда

где to — число записей веса 0 в библиотеке V (to 6 {0,}).

Доказательство. Обозначим через U — число записей веса г в библиотеке V (г = 1, п).

Возьмем произвольный ПИГ U над базовым множеством Т = = (Л1^п, 0), разрешающий ЗИП I. (Такой ПИГ обязательно существует, так как Т полно для типа Sboob).

Согласно лемме 17 библиотеку V можно разбить на такие непересекающисся части, что каждая часть содержит записи одного веса и каждой части веса i > 0 и мощности t сопоставляется такая совокупность pe6ej) графа U, что сумма сложностей ребер из этой совокупности не меньше чем V 2^1-тп, причем образы различных частей при этом соответствии не пересекаются. Отсюда следует, что.

Теперь предположим, что в библиотеке V есть запись уо = = (0,…, 0) веса 0. Обозначим через Со главную цепь, ведущую из корня в множество Ьи{уо) (согласно теореме 21 такая цепь существует). Пусть ао — лист, в котором заканчивается цепь Со, а ребро (0Оу^ао) — последнее ребро цепи СоТак как запись уо удовлетворяет всем запросам из В^п, то все запросы проходят через ребро {0о,<*о), и, значит, сложность этого ребра равна 1. Остается заметить, что ребро (/?о><*о) не принадлежит ни одной совокупности ребер, соответствующей части разбиения веса, большего 0.

Таким образом,.

Отсюда в силу произвольности ПИГ U вытекает утверждение теоремы. Что и требовалось доказать.

Замечание. Если мы находимся в условиях теоремы 26, то нижняя оценка, получаемая из этой теоремы, практически в два раза лучше мощностной нижней оценки.

Теорема 27 (верхняя оценка). Пусть I = {В^п, У, У) — ЗИП типа Sbooi• Пусть базовое множество имеет вид Т — (/С^п, 0), где К^п — множество монотонных элементарных конъюнкций. Пусть V = к и т — такое число, что 2(«J < k ^ 2(_m» J. Тогда

Доказательство. Обозначим через /Ср — множество всех монотонных элементарных конъюнкций, содержащих не более / переменных (или другими словами, имеющих длину не более /).

Построим по индукции информационный граф (/", реализующий как функции фильтров каких-либо вершин все функции из /С[*.

Базис индукции. 1 = 1. /С" = {l, xi,. ., х_п}.

Ui будет иметь вид, изображенный на рис. 3.11, где жирной точкой изображен корень графа, а на концах ребер реализуются функции из /С".

Рис. 3.11. Универсальный многополюсник для множества /С?

Шаг индукции. Пусть (7/L _х — граф, реализующий все функции из /Ср_ 1 — Граф Uf¹ будем строить, добавляя к U[^l_₁ вершины и ребра, чтобы реализовать функции из /CJ¹ K^__v следующим образом. Возьмем произвольную монотонную элементарную конъюнкцию Xij & ••• & Х{₍ длины /. В графе U[Li найдем вершину, на которой реализуется функция х*_г & ••• & х<_|-1, и выпустим из нее ребро, которому припишем переменную хц. На вершине, в которую ведет это ребро, будет реализовываться как функция фильтра функция Xjj & • • • & Xi_r Перебрав все функции из /CJ¹ К,^х__г и проделав для каждой эту операцию, получим требуемый граф С//¹, реализующий все функции из /С".

Отметим, что на первом ярусе графа UJ¹ находится п + 1 = («) -f 1 ребер, и сложность каждого из них равна 1 (первый ярус — это ребра, исходящие из корня), а на г-ом ярусе (i ^ 2) находится (*?) ребер, и сложность каждого из них равна 2¹~^t (г-ый ярус — это ребра, исходящие из концов ребер (г- 1)-го яруса). Таким образом, сложность графа Up равна.

Вернемся теперь к нашей задаче I.

Заметим, что для любой записи у (Е V характеристическая функция этой записи есть некоторая монотонная элементарная конъюнкция, которую будем обозначать К_у.

Информационный граф ?/, разрешающий задачу /, будем строить следующим образом. Возьмем граф Uописанный выше. Возьмем произвольную запись у 6 V. Возможны два случая.

• 1. Характеристическая функция этой записи К_у имеет длину, не превышающую т. Тогда в графе C/JJ находим вершину, на которой реализуется функция К_у, объявляем эту вершину листом и приписываем ей запись у.
• 2. Длина элементарной конъюнкции К_у больше чем т. Пусть К_у =

= где I > т. Тогда найдем в графе UР вершину, на которой реализуется функция х& • • • & х*_т, выпустим из этой вершины ребро, припишем этому ребру функцию х*_т+1 & ••• & х;₍, объявим конец этого ребра листом и припишем ему запись у.

Проделав эту операцию для каждой записи у € V, мы получим граф U, который, как нетрудно заметить, согласно теореме 1 разрешает задачу I.

Оценим сложность графа U. Граф U содержит в себе как подграф граф Up. В худшем случае, когда для каждой записи реализуется случай 2, мы добавим к графу Up к ребер, каждое из которых исходит из некоторой вершины, на которой реализуется элементарная конъюнкция длины тп. Следовательно, сложность каждого из этих к ребер будет равна 2^-ш. Таким образом,.

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

Теорема 27 позволяет нам показать, что существуют библиотеки, для которых нижняя оценка теоремы 26 асимптотически не улучшаема.

Следствие 12 (асимптотическая неулучшаемость нижней оценки). Если базовое множество имеет вид Т = (F, 0), где

ъ

F С М^п и /С^п С F, то существуют такие ЗИП I = (В^п, V, У) типа

3bool} *41 710

Доказательство. Пусть ш (п) -" оо при пчооит = о (п). Пусть к (п) такое, что (_TO" j) = д (к) и к < (^). Рассмотрим библиотеку V, являющуюся fc-элементным подмножеством m-го слоя куба В^п, то есть У С В^г_п и |У| = к. Рассмотрим связанную с этой библиотекой ь

ЗИП I = (?^п, V, ^). Согласно теореме 26.

согласно теореме 27.

Осталось заметить, что последние два неравенства доказывают утверждение следствия 12.