Повна версія

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

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


<<   ЗМІСТ   >>

СВЕРХЛОГАРІФМІЧЕСКІЙ ПОШУК

нехай

де Fi, G i визначаються співвідношеннями (2.28), (2.29).

Зрозуміло, що для Nf G сг для будь-якого / 6.

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

Теорема 16. Нехай функція щільності розподілу ймовірностей p (u, v), яка визначає міру Р імовірнісного простору над безліччю запитів ХШ, така, що p (u, v) <з = const; I = ( Xi n t , V, pint) ~ довільна ЗІП типу Si n t; Т 2 - базове безліч, яке визначається співвідношенням (2.32). тоді

Доведення. Впорядкуємо записи в бібліотеці у = {уь • • •> 2 / fc} так, що у, <у 2 <? ? ? <Ук?

Нехай т - деякий параметр, значення якого визначимо пізніше.

Введемо безліч номерів S = { «I, ..., s m _i} таке, що Si - номер запису з V такий, що y Si - найближча зліва запис до точці i / m (г = 1 , т - 1), а якщо такого запису не існує, то Si = 0.

Візьмемо точку, оголосимо її коренем графа і позначимо /% • Випустимо з кореня два ребра, одне з яких будемо вважати лівим, а інше правим. Кінець лівого ребра позначимо Д, а кінець другого - fo.

Припишемо корені перемикач g- % rn (u, v) з безлічі ?? з. Лівому ребру пріпішем 1, а правому 2.

Побудуємо для V граф Uy так, як це було зроблено в доведенні теореми 15 і сумісний його корінь з вершиною

А-

Побудуємо орієнтоване збалансоване бінарне дерево з т - 1 кінцевими вершинами з коренем у вершині Д, все ребра якого орієнтовані від ft до кінцевих вершин. Позначимо це дерево через D m _i. З кожної внутрішньої вершини дерева Дп-i виходить 2 ребра, одному з них пріпішем 1, а іншому - 2, тобто всі ребра дерева D m _i будуть перемикачів. Тоді кожної кінцевий вершині дерева D m _i можна зіставити слово з символів 1 і 2 відповідно до ребрами, зустрічаються в ланцюзі від кореня до даного листа, причому перший символ слова відповідає ребру, що виходить з кореня, а останній ребру, що входить в кінцеву вершину. Занумеруем кінцеві вершини відповідно до словниковим порядком слів, відповідних кінцевим вершин, і позначимо їх через 0 [, ... тобто вершині 0 [ відповідає слово 11 ... 1, а вершині 0 > т- слово 22 ... 2. Навантаження внутрішніх вершин дерева D m -i перемикачами з G визначимо наступним чином. Нехай 0 - довільна внутрішня вершина дерева D m -Нехай /? '• - кінцева вершина з максимальним номером в гілки, що росте з вершини, в яке веде ребро з номером 1, що виходить з 0. Тоді вершині 0 пріпішем перемикач 9/ M • Таку операцію виконаємо для всіх внутрішніх вершин дерева, і повністю визначимо навантаження вершин і ребер дерева Dm- 1

Нагадаємо, що в графі Uy листя позначаються c * i, ..., а * і їм приписані відповідно записи у х , ..., у до . Візьмемо до нових точок, оголосимо їх листям і позначимо а , ..., а *. Кожному листу <* { (г = 1 , к) пріпішем запис уг (тим самим кожен запис у { буде приписана двом листам - а * і а). З кожного аркуша а (г = 2, А :) випустимо ребро, що веде в лист ot _ x , і припишемо йому предикат Xy.-i , PintF x .

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

Тепер для кожної вершини 0 [ виконаємо наступні дії. Якщо Si 0, то з 0 [ випустимо ребро, що веде в лист a ' t , і припишемо йому предикат X y , it p intF x . Якщо Si <до, то з 0 [ випустимо ребро, що веде в лист a 5 . + I, і припишемо йому предикат * Ув <+1 tPintF x .

Це безліч ребер, що виходять з вершин 0 [(i = 1, т - 1), назвемо правої предикатной частиною.

Отриманий таким чином ІГ позначимо через U m .

Покажемо, що граф U m вирішує одновимірну задачу інтервального пошуку I = (Xinty V, pint).

Розглянемо довільну запис у * € V. За побудовою LumiVi) = В кожен з листя а »і а 'ведуть тільки

ребра, яким приписаний предикат x yiiPint , отже,

Нехай х = (і. V) - довільний запит, такий що і <у »< v , тобто х0 (у {.рш) - Покажемо, що 4 > рах ( х ) v 4> з * ( х ) = 1 *

Позначимо Л а = = (і, і): 0 < v - і < а}.

Розглянемо спочатку випадок, коли х € ^ i / ( m + i) -

Тоді провідність ребра (Po.Pi) дорівнює одиниці, а ребра (Ро. Р2) - нулю. Оскільки будь-яка ланцюг, що веде в лист а 'проходить через ребро (Ро.р 2 ). то а [( х ) = О

Позначимо через G'p підграф графа? / Т , що складається з ланцюгів, що виходять з вершини р.

Так як провідність ребра (Ро.Рх) на запиті х дорівнює 1, то ми виходимо в вершину Pi . За побудовою граф Gp x збігається з Uv і, отже,ai ( x )= 1> так як Uv вирішує ЗІП I.

Тепер розглянемо випадок, коли х # j4i / ( m + i>.

В цьому випадку р_ ш (х) - 2 і провідність ребра (Po.Pi) буде дорівнює 0, а ребра 0 2 ) дорівнює 1, тобто ми потрапимо в вершину Р2 , а провідність всіх ланцюгів, що проходять через ( Ро.Рх) дорівнює 0. з вершини Р 2 зростає дерево An-i, і воно має ту властивість, що з кожної його внутрішньої вершини виходить 2 перемикальних ребра, і, отже, завжди провідність рівно одного з ребер дорівнює 1. звідси випливає, що для будь-якого запиту завжди існує єдина ланцюг, що з'єднує Р2 з деякою вершиною /? ' , Провідність якої дорівнює 1. Таким чином, після проходження дерева ми потрапимо в деяку вершину /? ', Причому з побудови цього дерева ця вершина, така, що j є мінімальним числом, таким що j / m> і.

Так як v - і> 1 / т, то точка j / m належить відрізку

U, v].

Розглянемо два випадки.

1) 2 Н <j / m.

Тоді і <у. <У Sj < v, так як y 9j - найближча зліва до j / m запис з бібліотеки V. Звідси випливає, що провідність ребра, що веде з /? ' в лист a ' Sj дорівнює 1. Залишилося помітити, що провідність частини лівосторонньої кінцевий ланцюга, що веде з a' 3j в orj, також буде дорівнює 1, так як 0 < yi <y Sj < v.

Відзначимо також, що в цій ситуації ip ai (x) = 0, так як в кращому випадку ми потрапимо в вершини правобічної кінцевий ланцюга в точці o 4j + i, яка в цьому ланцюзі знаходиться після

ТОЧКИ c * j.

2) Vi> j / m.

тоді іSj +1 <у, - < v. Звідси випливає, що провідність ребра, що веде з / 3 'в лист a ^ + i, дорівнює 1, і провідність частини правобічної кінцевий ланцюга, що веде з a Sj + i в c * j, також дорівнює 1 на запиті х.

Аналогічно попередньому випадку ip a > (х) = 0.

Тим самим ми показали, що для будь-якого запису у *? V і будь-якого запиту? Xi nt такого, що xpi nt yi в графі U m існує проводить на запиті х ланцюг, що веде з кореня в будь-якої (але рівно в один) з листя а, і с / { .

Що і доводить, що граф С / т вирішує завдання I.

Підрахуємо складність графа U m .

Розглянемо спочатку довільний запит х? Ai / m .

В цьому випадку

Тут перший доданок відповідає обчисленню перемикача g- t m в вершині / 3 0 . Другий доданок дають перемикачі, що входять в єдину провідну ланцюг, що пролягає через комутаційне частина дерева D. Третє складова відповідає обчисленню одного або двох предикатів, відповідних предикатним ребрах з предикатной частини дерева D, зростаючим з вершини, до якої веде проводить ланцюг. Четверте доданок відповідає обчисленню предикатів, відповідних ребрах, що виходить з листя, записи яких входять у відповідь (по одному на кожну запис).

Розглянемо випадок, коли х? XAi / m .

тоді

Тут перший доданок відповідає обчисленню перемикача <7_, т . Другий доданок дають перемикачі, що входять в єдину провідну ланцюг, що пролягає через дерево D m - 1. Третє складова відповідає обчисленню одного або двох предикатів, приписаних ребрах, що походить із тієї вершини / 3 ', в яку веде проводить ланцюг дерева D m -i- і, нарешті, четверте доданок, як і раніше, відповідає обчисленню предикатів, відповідних ребрах, що виходить з листя, записи яких входять у відповідь. Як ми показали раніше, для будь-якого запису у ,, що увійшла в відповідь, рівно у одного з листя а, і а 'функція фільтра буде дорівнює 1, і, отже, кожного запису відповідає рівно одне ребро і відповідно рівно один обчислений предикат.

Підрахуємо складність графа U m .

Оскільки граф U m вирішує завдання /, то і отже, що використовується вище рівність

доводиться простою зміною порядку підсумовування.

Встановивши значення параметра m =] 2clog 2 fc [, отримаємо

Теорема 16 доведена. ?

Алгоритм пошуку, відповідний графу U m , являє собою наступне.

Нехай нам дано якийсь запит х - (і, v) і X lnt . Пошук по цьому запиту будемо здійснювати в такий спосіб.

Спочатку обчислимо довжину інтервалу х.

Якщо v - і <l / ([log 2 к] + 1), то відповідь будемо шукати за методом, описаним в теоремі 15. Якщо v - і> l / ([log 2 A;] + 1), то ми за час og 2 og 2 k знайдемо номер j точки j / m, що потрапляє в інтервал [і, і]. Потім, починаючи із запису з номером Sj ) переглядаємо справа наліво записи з V і порівнюємо з лівим кінцем запиту - точкою і. Як толька чергова запис виявиться менше і у ми, починаючи з записи з номером +1, переглядаємо зліва направо записи з V і порівнюємо з правим кінцем запиту - точкою v до тих пір, поки чергова запис не стане більше v.

Таким чином, в першому випадку крім перерахування відповіді ми витрачаємо час порядку log 2 до , а в другому - log 2 log 2 к. Оскільки в переважній більшості інтервал х буде досить великим, то ми отримаємо оцінку теореми 16.

 
<<   ЗМІСТ   >>