Повна версія

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

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


<<   ЗМІСТ   >>

МИТТЄВЕ РІШЕННЯ

нехай

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

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

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

Теорема 17. Нехай ЗІП I = (Xint, V, Pint) ~~ одномірна задача інтервального пошуку, тобто завдання типу Si nt) F3 - базове безліч, яке визначається співвідношенням (2.35), і «(/) =? Р (0 (у, Pint)) - Тоді , якщо функція щільності веро-

y € V

ятность р (х), яка визначає імовірнісну міру Р, обмежена константою с, то

Доведення. Нижня оцінка випливає з теореми 12.

Побудуємо ІГ, на якому досягається верхня оцінка одновимірної задачі інтервального пошуку.

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

Візьмемо ІГ U m , побудований в теоремі 16. У ньому з вершини виходить дерево кінцевими вершинами якого

є вершини 0 [..., Вилучимо все ребра дерева D m -

і все вершини, що не збігаються з вершинами 02 і 0 [..., 0 ' m ^ i . Випустимо з вершини 02 т - 1 ребро, пріпішем цим ребрах числа від 1 до m - 1, і замінимо навантаження вершини 0 2 на перемикач д. % Тп 6 G $. Отриманий інформаційний граф позначимо через U ' m .

Відзначимо, що для будь-якого запиту х = ( і , v) ? Xj nt якщо j = д, т (х) } то j є мінімальним числом, таким що j / m> і. Отже, вершина 02 з вихідними з неї ребрами функціонально збігається з деревом D m _i, і, значить, ІГ U ^ вирішує ЗІП I.

Що стосується складності графа U ' m , то в порівнянні з ІГ U m на будь-який запит х ? Xint ^ / m замість] log 2 (m - 1) [обчислень перемикачів, відповідних провідної ланцюга дерева D m _i, буде вирахувано один перемикач д. > Тп . Тому

Підрахуємо обсяг графа U ' :

Тут перший доданок відповідає ребрам, що походить із 0о. Другий доданок є кількість ребер в дереві D. Третє і четверте складові відповідають ребрам з правобічної і лівобічної кінцевих ланцюжків. П'яте доданок - це ребра, що виходять з вершини 02- І, нарешті, шосте доданок не менш ніж число ребер, що виходять з вершин 0 [ (г = 1, т).

Візьмемо в якості параметра га = [2 з [log 2 &]] і отримаємо

що і доводить твердження теореми 17.?

Дамо неформальне опис алгоритму, наведеного вище.

Нехай нам дано безліч V = {у 1} ..., г / т}, в якому ми повинні проводити пошук. Спочатку впорядкуємо його в порядку зростання. Якщо відома оцінка зверху з функції щільності ймовірності появи запитів, то в якості параметра га візьмемо га = 2c [log 2 A;], якщо ж з невідома, то замість неї можна взяти будь-яке число, наприклад, з = 2. Потім для V побудуємо безліч номерів S = {si, ..., s m -i}, описане вище. Відзначимо, що воно будується тільки один раз. Тепер пошук по довільно взятому інтервалу-замовлення х = (u, v) проводиться таким чином.

Спочатку обчислюється довжина запиту х.

Якщо вона менше ніж 1 / га, то в безлічі V бінарним пошуком знаходиться найближча справа до точки і запис. Далі, починаючи з цього запису, проглядаються зліва направо всі записи з V і порівнюються з правим кінцем запиту - точкою v - до тих пір, поки чергова запис не стане більше v. Тим самим в цьому випадку, крім перерахування відповіді, виробляється майже log 2 до дій.

Якщо v - і> 1 / га, то за допомогою функції g. tTn отримуємо номер j точки j / m, що потрапляє в інтервал [гх, v]. Потім, починаючи із запису з номером Sj, переглядаємо справа наліво записи з V і порівнюємо з лівим кінцем запиту - точкою і. Як тільки чергова запис виявиться менше і , ми, починаючи з записи з номером Sj 4 "1, переглядаємо зліва направо записи з V і порівнюємо з правим кінцем запиту - точкою v до тих пір, поки чергова запис не стане більше v. Тим самим в цьому випадку ми, крім перерахування відповіді, виробляємо 4 зайвих дії (порівнюємо v - і з 1 / га, обчислюємо функцію g. tmi робимо 1 зайве дію, йдучи справа наліво, і 1 зайве дію, йдучи зліва направо).

Залишилося помітити, що параметр т підібраний так, що середня складність першого випадку не перевищує 1, якщо відома оцінка зверху функції щільності ймовірності, і не перевищує деякої константи, якщо ця оцінка точно не відома.

І, нарешті, зауважимо, що даний алгоритм вимагає додаткову пам'ять порядку log 2 А :, щоб зберігати безліч S.

 
<<   ЗМІСТ   >>