Повна версія

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

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


<<   ЗМІСТ   >>

БІНАРНИЙ ПОШУК

Якщо V - кінцеве підмножина X , то через шахові будемо про-

yev

значать таке y maxV , що для будь-яких у 6 V у? <у т аху і через

min у позначимо таке у т иV, що для будь-яких у € V у т и ^ У- yev

нехай

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

Теорема 13. Якщо I = (X y V y pid) - завдання пошуку ідентичних об'єктів, тобто завдання типу Sid, Р'и - базове безліч, яке визначається співвідношеннями (2.13) - (2.17), то

Доведення. Нехай V = к.

Побудуємо ІГ D l (V) f має вигляд дерева, в такий спосіб.

Візьмемо бінарне збалансоване дерево з до кінцевими вершинами, висоти] log 2 fc [, все ребра якого орієнтовані від кореня до кінцевих вершин. Якщо в цьому дереві є внутрішня вершина, з якої виходять ребра, провідні одне в кінцеву вершину, а інше у внутрішню (якщо така вершина є, то вона тільки одна), то з кінцевої вершини, до якої веде один з цих ребер, випустимо одне ребро. Отримане дерево позначимо D. Оголосимо кінцеві вершини цього дерева листям і порівняти їм зліва направо в порядку зростання елементи з V. (Говорячи про дерево, ми маємо на увазі деяку його укладання, і напрямки "вліво", "вправо" визначаються вже на цій укладанні.)

Нехай 0 - довільна внутрішня вершина дерева D. Позначимо через Vp безліч записів, які відповідають листю, схемно досяжним з 0. Нехай 0 ' - вершина, до якої веде ліве (якщо воно одне, то єдине) ребро з 0 . нехай

Оголосимо всі внутрішні вершини дерева D, у тому числі виходять ребра, що ведуть у внутрішні вершини, вершинами перемикання і для кожної такої вершини 0 лівому ребру, з неї виходить, пріпішем 1, а правому - 2, а самій вершині пріпішем перемикач g < t y 0 (x).

Всі ребра дерева D , що входять до листя, оголосимо предикативними і пріпішем кожному такому ребру, ведучому в лист із записом у } предикат f- y (x).

ІГ, отриманий з дерева D після визначення таким чином навантаження, позначимо D l (V) і будемо називати першим деревом бінарного пошуку.

Покажемо, що D l (V) вирішує завдання / = ( X , V> pid) -

Візьмемо довільну запис у ? V. Нехай а - лист D 1 (V) ) якого застосовується запис у. У цей лист веде єдина ланцюг, що складається з не більше ніж] log 2 ребер, причому всі ці ребра, крім останнього, переключательние. Останнє ребро в ланцюзі - предикатное з предикатом / =, у (х), і його провідність на запиті у дорівнює / =, У (у) = 1. Покажемо, що провідність інших ребер ланцюга на запиті у дорівнює 1. Візьмемо довільно одне з цих ребер (0,0 '). Якщо (/ ?, 0 ') - ліве, що виходить з 0 , то уVpi і предикат, приписаний вершині / 3, д ±, Ув {у) = 1,

так як у <уа = шах у '. Якщо {0,0 ') - праве ребро, під кінець V

дящее з 0 , то у ур і д <, У /! (у) = 2, тим самим провідність ребра {0, 0 ') в обох випадках дорівнює 1. Отже, д> а {у) = 1. Так як ребро, що веде в лист а, має навантаження / =, у , то для будь-якого запиту х ф у <р а (х) - 0.

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

Підрахуємо обсяг ІГ D l (V).

Оскільки D l (V) є дерево, в якому полустепені результату будь-якої вершини дорівнює 2, крім, можливо, однієї вершини, то якщо в дереві D l (V) немає вершини з полустепені результату 1, то в D y {V) буде рівно 2 • до - 2 ребра, а якщо в дереві D l (V) є вершина з полустепені результату 1, то в D l (V) буде 2 к-1 ребро. Звідси слідує що

Підрахуємо складність ІГ D l (V).

Розглянемо довільний запит х € X. Як ми показали вище, активні на цьому запиті вершини графа D y (V) (вершина 0 активна на запиті, якщо рр (х) = 1) утворюють єдиний ланцюг. Причому в цьому ланцюгу не більше ніж] log 2 ? [- 1 переключательних вершин і одна вершина, з якої виходить не більше двох ребе з поелікатамі. Тим самим

Звідси з урахуванням (2.18) відразу випливає, що

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

Відзначимо, що перше дерево бінарного пошуку відповідає стандартним алгоритмом бінарного пошуку в версії Боттенбру- ка [71, с. 214].

вправи

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

 
<<   ЗМІСТ   >>