Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей.

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

Дадим строгое определение исследуемого в данном разделе класса задач поиска.

Скажем, что ЗИП I = (X, V, р) обладает F-свойством, если она обладает A-свойством и для любых у, у'V справедливо Р(0(у,р)) =

= р (0№р)).

Обозначим

Справедлива следующая теорема [24].

Теорема 7. Если I = {X, У,р) — ЗИП, обладающая F-свойством, Т — (F, 0) — измеримое базовое множество, допустимое для I, то

где у е V.

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

Лемма 3. Пусть 0 < t ^ ^ гпогда

Доказательство. Нетрудно убедиться, что R(k) есть непрерывная выпуклая функция, представляющая собой ломаную линию, причем точки З1 и 2 • З1 (/ = 0,1,2,...) являются точками излома. А из свойств выпуклых функций легко выводится утверждение леммы.

Обозначим через N — множество натуральных чисел, а через N0 = N U {0}.

Доказательство. Из леммы 3 следует, что

Пусть / = [log^k], с = к - 3^log3 к т. е. к = 3* + с, где 0 ^ с ^ 2 • 3*, тогда по определению функции R(k)

Докажем утверждение леммы при четном к.

1) Пусть 0 < с ^ 3Z_1, тогда

так как в этом случае (3Z_1 + с)/2 ^ 3Z_1.

Для нечетного к лемма доказывается аналогично.

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

Следствие 2. Г(к) ^ R(k)-2-k, причем равенство достигается только при 4 • 3(»og3*]-i k log3*l.

Доказательство. Из леммы 3 следует, что Докажем утверждение леммы при к = 3s.

Пусть I = [log3 к], с = к - 3^1оКз к т. е. к = 3* + с, к/3 = 3/_1 + с/3.

1) Пусть 0 ^ с ^ 3*, тогда

2) Пусть 31 ^ с ^ 2 • 3Z, тогда

Для случаев к = 3s+l и к = 3s-f 2 лемма доказывается аналогично.

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

Рассмотрим функцию M(D) = Y1 Р ' Фр-» гДе D € Vo, Vq

/зея(о)

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

Пусть N(k) = min{M(Z>): DVo и D = к}, где |.D| — количество концевых вершин в дереве D.

Дерево D € Vo назовем простым, если M(D) = iV(|?)|).

Лемма 6. Для любого натурального к существует простое дерево с к концевыми вершинами, полустепень исхода любой внутренней вершины которого равна либо 2, либо 3.

Доказательство. Предположим, что дерево D содержит ветвь D вида изображенного на рис. 2.1, где / ^ 4.

Рассмотрим дерево D2 вида, указанного на рис. 2.2, где г = [//2].

Покажем, что M(D2) ^ M(D).

Пусть U = Щ (i = М), U ^ 1.

Ветвь с большой полустепенью исхода корня

Рис. 2.1. Ветвь с большой полустепенью исхода корня

Уменьшение полустепени исхода ветвей

Рис. 2.2. Уменьшение полустепени исхода ветвей

Возможны два случая:

1) / — четно, т. е. / = 2 • г, где г ^ 2, тогда

причем равенство достигается лишь при г = 2.

2) I — нечетно, т. е. I = 2 • г + 1, где г ^ 2, тогда

Таким образом, мы показали, что если в дереве есть ветвь вида Di, то ее всегда можно заменить на ветвь вида ?>2, и дерево от этого не усложнится.

Ветвь с единичной полустепенью исхода корня

Рис. 2.3. Ветвь с единичной полустепенью исхода корня

Осталось заметить, что ветвь вида ?>з, изображенного на рис. 2.3, всегда можно заменить на ветвь Dt> не усложняя при этом дерева. Тем самым лемма доказана.

Доказательство. Доказывать будем индукцией по числу к. Базис индукции, k = 1; 7V(1) = 0 = Я(1). к = 2; N(2) = 4 = R(2). А: = 3; JV(3) = 9 = #(3).

Шаг индукции. Пусть для любого t < к выполнено N(t) = R(t).

Дерево D

Рис. 2.4. Дерево D

Согласно лемме 6, существует простое дерево с к концевыми вершинами, которое имеет либо вид D1? изображенный на рис. 2.4, либо вид ?>2> изображенный на рис. 2.5.

Дерево D2

Рис. 2.5. Дерево D2

Согласно предположению индукции, лемме 5 и следствию 2,

С другой стороны, если D, D'2, D'3 — простые и такие, что их мощности (т. е. количество концевых вершин) различаются не более чем на 1, то M(D) = R(k) и D — простое, а если 4 • 3^log3 к^~1 ^ к ^ ^ 2-3(*з*] и D" и ?>2 — простые и такие, что ||I?i| — D2 ^ 1, то M(Z>2) = R(k) и D2 простое дерево.

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

Перейдем к доказательству теоремы 7.

Возьмем произвольный ИГ U ? U(I,F). Согласно теореме 6 существует такое информационное дерево D ? V1, что T(U) ^ T(D). Оценим сложность ИД D.

где у' некоторая запись из V.

В силу произвольности U теорема доказана.

Следствие 3. В условиях теоремы 7 где с ^ 3.

Справедливость утверждения следует из того, что k-Р(0(у, р)) ^ 1.

Для сравнения отметим, что мощностная нижняя оценка сложности, получаемая с помощью теоремы 4 для задач, обладающих F- свойством, равна константе, которая не превышает 1.

Результат следствия 3 может показаться аналогичным теоретикоинформационной нижней оценке [121], но он имеет принципиальные отличия: во первых, он касается средней сложности, а не сложности в худшем случае, во-вторых, доказывался для произвольных сетей, а не бинарных деревьев.

Следствие 4. Если I = (X, У,р) — ЗИП, обладающая F-свойством, Т — (F, 0) — измеримое базовое множество, допустимое для I, такое, что Fq С F, то

Доказательство. Нижняя оценка следует из теоремы 7, а верхнюю даст ИД, изображенный на рис. 2.3, где Aj — простое дерево с к концевыми вершинами, которые одновременно являются листьями графа, нагрузка листьев записями из V выбрана произвольно, а нагрузка ребер осуществляется по методу, описанному в доказательстве теоремы б, так, чтобы выполнялось С-свойство.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >