Повна версія

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

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


<<   ЗМІСТ   >>

ЛОГАРИФМІЧНИЙ ПОШУК

нехай

Відзначимо, що N / € а для будь-якого предиката / € F uGi, тобто базове безліч Т вимірюється. Оскільки для будь-якого запису УYint Ху, Pint 6 Fy то Т повно для типу S in t- Справедлива наступна теорема.

Теорема 15. Нехай I = {Xi ni , V, p int ) - ЗІП типу Si nt} де V = {j / i, ... У ук}, причому 0 <t / i <... <у * < 1; Т - базове безліч, яке визначається співвідношеннями (2.28) - (2.30). тоді

Доведення. Побудуємо перше дерево бінарного пошуку для бібліотеки V , описане в розділі 2.4.1, але тільки навантаження переключательних вершин ми будемо брати з безлічі а замість предикатів / => 0 використовувати предикати Xa, p int € ^ i- Позначимо це дерево через D.

Для позначення Vp буде використаний той же сенс, що і в розділі 2.4.1.

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

Позначимо лист, якому відповідав би запис у *, через а, (г = 1 , к). З кожного листа or * (r = 1, А: - 1) випустимо ребро, що веде в лист а * + 1, і припишемо йому предикат Ху »+ ьр» п «€ ^ 1

Це безліч з (до - 1) -го ребра назвемо правобічної кінцевий ланцюгом.

Отриманий граф позначимо через Uy .

Відзначимо одне досить очевидне властивість графа Uy. Нехай (5 - вершина графа Uy, що не є листом. Нехай Vp = {y «, ffc + i» * "» y; b Тоді

Покажемо, що Uy вирішує ЗІП I. По теоремі 9, для цього достатньо показати, щоQi = Xy it p xn tАля будь-якого i € {1, до}.

Доводити це будемо індукцією по м

Базис індукції, г = 1.

У лист Qi веде єдине ребро з вершини, яку позначимо через ft. очевидно,ai= Wr & Xybp in ** Через yj позначимо максимальну запис в бібліотеці Vp>. Приймемо з - у 7 , якщо j ф до, і з = 1, якщо j = к. Очевидно, з> у. тоді

тобто tp ai = XyuPint-

Індуктивний перехід. Припустимо, що для деякого i> 1 функція фільтра листа а »дорівнює y? ai = Ху », р» п * -

Розглянемо лист oti + (г + 1 < к). У нього ведуть два ребра: з листа Qi і деякої вершини / ?, не є листом. Нехай Vi і yj - мінімальна і максимальна записи в бібліотеці Vp відповідно. нехай

Тим самим ми показали, що Uv вирішує I.

Покажемо, що

Розглянемо довільний запит х G Хш- Оскільки через комутаційне частина дерева D пролягає єдина провідна ланцюг, і її довжина не перевищує] log 2 А; [- 1, то на будь-який запит буде обчислено не більше ніж] log 2 А: [- 1 перемикачів . Далі на запиті х обчислюються один або два предиката, відповідних предикатним ребрах з предикатной частини дерева D , зростаючим з вершини, до якої веде проводить ланцюг. Таким чином, сумарна складність дерева D не перевищує] log 2 / c [-f 1.

Залишилося підрахувати складність правобічної кінцевий ланцюга. З кожного аркуша а »(г = 1, А: - 1) виходить одне ребро і його складність дорівнює Р ( 0 (у {, рш)).

отже,

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

Алгоритм пошуку, відповідний графу? / У »побудованому в доведенні теореми 15, полягає в наступному. У впорядкованої по зростанню бібліотеці за допомогою бінарного пошуку за log 2 до кроків знаходиться найлівіша запис, яка була над лівіше лівого кінця запиту. Потім зліва направо, починаючи з знайденої запису, проглядаються записи і порівнюються з правим кінцем запиту, і якщо виявляється, що чергова запис не більш правого кінця, то цей запис включається у відповідь, а якщо більше, то пошук припиняється, тобто - це традиційний алгоритм вирішення даного завдання пошуку за допомогою структури даних, званої прошитим двійковим деревом [52]. Там же [52, стр. 93] стверджується, що описаний алгоритм оптимальний як за часом пошуку, так і по пам'яті, але мається на увазі час в гіршому випадку, а оптимальність розуміється по порядку.

 
<<   ЗМІСТ   >>