Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

КОНСТАНТНИЙ В СЕРЕДНЬОМУ АЛГОРИТМ ПОШУКУ

Нехай No = NU {0} - безліч цілих невід'ємних чисел.

нехай

функція, певна на безлічі No-

Доведемо наступне допоміжне твердження.

Лемма 6. Нехай L (l) - функція, певна вище, нехай кут 6 N, нехай

Доведення. Якщо доопределить функцію L (l) на позитивну піввісь числової прямої, наприклад, наступним чином: то отримана функція буде безперервної і увігнутою. І, взагалі кажучи, увігнутість цієї функції пояснює результат леми.

Більш докладний доказ будемо вести від противного. Припустимо, що лема невірна, тобто

і серед чисел ^ (г = 1, т) існує 2 числа, різниця яких не менше двох.

Без обмеження общностіможем вважати, що 1 [- 1 ' 2 > 2. Нехай

Так як функція L (х) увігнута, то по властивості увігнутих функцій

Якщо в нерівності (2.21) нерівність суворе, то отримали

m

протиріччя, так як - не максимально; якщо ж

• = 1 _

немає, то позначимо I "- 1(г = 3, т) і перейдемо до розгляду суми

Якщо серед чисел I " (r = 1 , т) немає пари чисел, різниця яких перевищує 1, то отримаємо протиріччя з нерівністю

  • (2.20), якщо ж є, то знову виконаємо операцію, описану вище, і позбудемося такої пари, і так будемо робити до тих пір, поки або не отримаємо суворе нерівність у нерівності
  • (2.21), або не прийдемо до розбиття l [ n ..., 1т такому, що

і всі вони відрізняються не більше ніж на 1, і тим самим отримаємо протиріччя з нерівністю (2.20), що доводить лему б.

?

Нехай на X задано ймовірнісний простір (X, а, Р). Нехай д} п (х) - перемикач такий, що

де ХХ 9 ..., Х т - розбиття множини X (тобто X = Х U • • • U Х т і Xi П Xj = 0, якщо i ф j) таке, що

де с - постійна, яка не залежить від т.

Так як

то звідси відразу випливає, що з> 1.

нехай

Справедлива наступна теорема.

Теорема 14. Нехай I = {X, V, pid) - завдання пошуку ідентичних об'єктів, тобто завдання типу Sid, де V = k, Т - базове безліч, яке визначається співвідношеннями ( 2 ЛЗ) - ( 2 Л 6 ),

(2.22) - (2.25), т - натуральне число, з - константа, яка визначається співвідношенням (2.23), Ь [1) - фгункція, яка визначається співвідношенням (2.19). тоді

Зокрема,

і Т (1, Т) ~ 1 при до -? оо. Крім того, для ІГ U 6 U {I, T), на якому досягається верхня оцінка, T (U) <2+] log 2 fc [.

Доведення. Побудуємо ІГ 1Д, що має вигляд дерева, в такий спосіб.

Візьмемо вершину До і оголосимо її коренем графа С / ^. Випустимо з До m ребер, пріпішем їм числа від 1 до т, оголосимо До точкою перемикання і припишемо їй перемикач д ^ (х).

Нехай Vi - Xi П V, l t = V {, i = , m.

Кінець ребра з номером г позначимо /?;.

Для всіх таких г, що Vi ф 0, випустимо з вершини Pi перше дерево бінарного пошуку, описане в розділі 2.4.1, тобто дерево D l {Vi).

Отриманий ІГ з | І | = А: листям позначимо U ^. Це граф над базовим безліччю Т.

Покажемо, що 17%, вирішує завдання / = (X, V, p, j).

Візьмемо довільну запис у & V. Нехай у G Vi (г € {1, т}), тобто лист а, якому приписана запис у, належить дереву D l (Vi). Так як д] п {у) = г, запит у пройде по Г'-му ребру, що виходить з кореня, в корінь дерева D l {V % ). Так як D l ( Vi) вирішує завдання пошуку ідентичних об'єктів для бібліотеки Vi, то тільки запит у пройде в лист а.

Таким чином, ми показали, що а (х) = f =, y {x). З огляду на довільність вибору у і теорему 9, отримаємо, що ІГ U%, вирішує завдання I = (X , V, рц).

Підрахуємо обсяг графа U% ,.

Підрахуємо складність ІГ? / ^.

Розглянемо довільний запит хX. Нехай х € Xi (r =

ТДП).

де L (l) - функція, яка визначається співвідношенням (2.19).

За визначенням і з огляду на лему 6,

Візьмемо т =] з? до [. При цьому Так як з> 1, то т> к. Якщо т = А ;, то к / m = 1 і Якщо тп > fc, то к / m = 0 і Отже,

Якщо взяти т =] A: -7 (fc) [, де 7 (А :) -? оо при до -? оо і 7 (к)> 1 при будь-якому до , то

З іншого боку, Т (/, / *)> 1, так як з кореня має виходити хоча б одне ребро, оскільки до > 0.

І нарешті, оцінимо В-складність ІГ? / Q скориставшись співвідношення (2.26),

Тим самим теорема доведена. ?

Слідство 1. Якщо Т - базове безліч, яке визначається співвідношеннями (2.13) - (2.16), (2.22) - (2.25), до - натуральне число, то

і при до -? оо

Наведемо два приклади завдання пошуку ідентичних об'єктів.

Приклад 1. Нехай i = (X, X, pid) - тип пошуку ідентичних об'єктів, де X = [0,1], причому задано ймовірнісний простір ( X , <7, Р) над X таке, що Р задається функцією щільністю ймовірності р (х).

нехай

Тоді перемикач у ^ (х) = шах (1,] х • т [) задовольняє співвідношенню (2.22).

Якщо р (х) <с = const , то Р (Х *) < с / т , і ми знаходимося в умовах теореми 14.

Наведемо неформальне опис алгоритму пошуку, описаного в доведенні теореми 14, стосовно до задачі / = (X , V, p id ) типу Sidi, де V = к.

Розіб'ємо відрізок [0,1] на т рівних частин відповідно до співвідношеннями (2.27).

Кожній частині можна порівняти підмножина безлічі V, що складається з точок, що належать цій частині.

Тепер для довільної точки-запиту х пошук точки з V , ідентичною запитом, будемо вести таким чином.

Визначимо ту частину відрізка, якій належить запит х. Її номер дорівнює тах (1,] х • т [).

Далі в безлічі, зіставлення знайденої частини, здійснимо звичайний бінарний пошук.

Згідно лемі 6 найбільше середнє час пошуку буде в тому випадку, коли точки з безлічі V рівномірно розподілені по всьому т частинах відрізка.

Якщо в якості т взяти т = до, то випадок, коли в кожну частину потрапить по одній точці з V , буде мати найбільшу складність. А оскільки знайти або годі й шукати об'єкт в безлічі потужності 1 можна за 1 крок, то в середньому за 2 кроки (на першому ми визначили номер потрібної частини) ми можемо вирішити завдання пошуку ідентичних об'єктів.

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

Якщо уважно придивитися до описаного алгоритму, то можна помітити, що за своєю структурою він нагадує гешування за методом ланцюжків, в якому в якості хеш-функції взято множення, а ланцюжки-списки організовані у вигляді бінарного дерева.

Приклад 2. Нехай Sm 2 = (Л ", X , pid) - тип пошуку ідентичних об'єктів, де X = {1, ..., N}.

Нехай (X, cr, Р) - імовірнісний простір над X , де а - безліч всіх підмножин, а імовірнісна міра Р визначає рівномірну ймовірність на безлічі запитів X , тобто для будь-якого х 6 X Р (х) = 1 / N.

Нехай задано т ? N.

Нехай г = N - т? [N / m].

Нехай Х , ..., Х т - таке розбиття множини, що і ми знову перебуваємо в умовах теореми 14 при с = 2.

вправи

2.35. Нехай / = (XjV } p c ) - задача про близькість, де X = {1,2, ..., N}, V З Х у р з - відношення пошуку, що задається співвідношенням мул X х V і визначається співвідношенням (2.11 ). За аналогією з пошуком ідентичних об'єктів побудуйте ІГ, що вирішує завдання про близькість I і має константну складність.

 
<<   ЗМІСТ   >>