Повна версія

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

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


<<   ЗМІСТ   >>

СКЛАДНІСТЬ ІНФОРМАЦІЙНИХ ГРАФІВ

З визначення функціонування ІГ природним чином випливає, що кожному ІГ U можна зіставити наступну процедуру пошуку.

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

Нехай на вхід процедури надійшов запит х. Вводимо поняття активного безлічі вершин і вносимо в нього в початковий момент корінь ІГ U і помічаємо його. Далі по черзі переглядаємо вершини з активного безлічі і для кожної з них проробляємо наступне:

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

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

Зауважимо, що якщо ІГ вирішує завдання /, то безліч, отримане на виході процедури, буде містити всі ті і тільки ті записи бібліотеки ( U ), що відповідають запиту х. Тобто отримана процедура вирішує ЗІП / = (X> V y p), де V = (? /), І, отже, є алгоритмом пошуку.

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

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

Відзначимо, що в більшості робіт, присвячених дослідженню складності алгоритмів пошуку, під складністю алгоритму розуміється час пошуку в гіршому випадку, і в порівняно рідкісних випадках досліджується середній час пошуку, хоча для задач пошуку, використовуваних в базах даних, для яких характерні масовість і багаторазовість, дослідження середнього часу пошуку видається більш актуальним. Сяке-таке пояснення крену в бік вивчення складності в гіршому випадку можна знайти в цитаті з [52, стор.20): Н На жаль, аналіз поведінки в середньому значно складніша річ, ніж аналіз найгіршого випадку, з двох причин: по-перше істотні математичні труднощі виникають, навіть якщо вдало вибрано вихідне розподіл; по-друге, часто з працею досягається згода в тому, що саме вбрання розподіл є реальною моделлю досліджуваної ситуації. Ось чому переважна більшість результатів пов'язано з аналізом гірших випадків. "

Визначимо поняття складності ІГ на запиті.

Будемо вважати, що час обчислення будь-якого перемикача з G приблизно однаково і характеризується числом a, a час обчислення будь-якого предиката з F - числом 6.

Нехай нам дано якийсь ІГ U і довільно взятий запит

хех.

Складністю ІГ U на запиті х назвемо число

Величина T (U, x) характеризує час роботи описаної вище процедури пошуку, зіставленої ІГ? /, Оскільки T (U, x) дорівнює кількості перемикачів, обчислених даною процедурою при подачі на її вхід запиту х, помножене на а, плюс кількість обчислених предикатів , помножене на 6.

Складність ІГ можна вводити двома способами. По-перше, як максимальну складність на запиті

(тут ми беремо max, а не sup, так як T (U , х) приймає цілі значення, і, значить, sup завжди досягається). Ця величина характеризує час пошуку в гіршому випадку відповідним ІГ алгоритмом і її будемо називати По-складністю ІГ (верхньої складністю). Ця величина досліджується в більшості робіт, присвячених проблемам складності завдань пошуку.

По-друге, можна вводити складність ІГ як середнє значення складності ІГ на запиті, взяте з безлічі всіх запитів. З цією метою введемо імовірнісний простір над безліччю запитів X, під яким будемо розуміти трійку (Х, сг, Р), де а - деяка алгебра підмножин безлічі X, Р - імовірнісна міра на <7, тобто адитивна міра, така, що Р (Х) = 1.

У зв'язку з тим, що ми ввели імовірнісний простір над безліччю запитів, уточнимо поняття типу. А саме, під типом будемо розуміти трійку S = } У, р), вважаючи, що безліч запитів X розглядається разом зі своїм імовірнісним простором у о, Р). У тих же випадках, коли ми хочемо явно виділити розглядається імовірнісний простір над Ху ми будемо представляти тип п'ятіркою S = (X, У, р, <т, Р).

Скажімо, що базове безліч Т - (F, G) з Меріме } якщо алгебра а містить всі множини N /, де /? F U G.

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

Лемма 5. Якщо базове безліч Т - (F, G) измеримое, то для будь-якого ІГ U над базовим безліччю Т функції (і у х), як функція від х, є випадковою величиною.

Доведення. Нам необхідно довести, що для будь-якого ІГ U над базовим безліччю Т і будь-якого дійсного числа г безліч X : T (t /, x) <г} Е а.

Покажемо, що (/ 3 6 F, (U)) -? (N V0 6 а).

Нехай (3 € 7 Z (U). Нехай Ср - безліч всіх орієнтованих ланцюгів ІГ Uу провідних фахівців із кореня в вершину р. Нехай З - деяка ланцюг, а з - деяке ребро. Через 0 (c) позначимо провідність ребра с.

Неважко бачити, що

З огляду на, що Nfv g = Nj U N g , Nj Лд = Nf П N gi маємо

Введемо наступне позначення:

Тоді, як неважко бачити,

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

Далі скрізь будемо припускати, що базове безліч вимірюється.

Складністю ІГ U назвемо математичне очікування величини Т (? /, Х), тобто число

Якщо (/ ?, від) - ребро ІГ, то складністю цього ребра назвемо число

  • • 6 • Р (N ^ 0 ) - якщо (0, а) - предикатное ребро;
  • аP (Np 0 ) / Tpp - якщо це ребро комутаційне.

Якщо 0 - вершина ІГ, то число P (N0)назвемо складністю вершини 0.

Неважко показати, що складність ІГ дорівнює сумі складнощів ребер ІГ. Справді

Далі скрізь будемо припускати, що а = 6 = 1.

Нехай нам дано ІГ U.

Об'ємом Q {U) ІГ U назвемо число ребер в ІГ U.

Як приклад ми можемо підрахувати складність ІГ U, зображеного на малюнку 2.5. Легко бачити, що Q {U) = до і T (U) = до , тобто обсяг графа мінімально можливий, а час максимальне. Це й не дивно, так як ІГ U відповідає переборного алгоритму пошуку.

Нехай нам дана якась ЗІП I.Сложностью завдання I при базовому безлічі Т і заданому обсязі q назвемо число

де - безліч всіх ІГ над базовим безліччю Т,

вирішальних ЗІП /.

Відповідно По-складністю завдання I при базовому безлічі Т і заданому обсязі q назвемо число

>? 4.

(тут ми беремо min, а не inf, так як T (U) приймає цілі значення, і, значить, inf завжди досягається).

число

назвемо складністю завдання I при базовому безлічі Т.

Відповідно По-складністю завдання I при базовому безлічі Т назвемо число

Якщо до - натуральне число, S - тип завдань пошуку, то позначимо

Будемо досліджувати функції, що характеризують складність класу ЗІП l (k } S), такі як функції Шеннона:

(в першому випадку ми беремо шах, а не sup, так як Т (1, Т) приймає цілі значення, і, значить, sup завжди досягається).

Якщо існує такий ІГ U1А {1, Т), що T (U) = Т (1, Т), го ІГ U будемо називати оптимальним для ЗІП /. Відповідно якщо T (U) = Т (1, Т)> то ІГ U будемо називати По-оптимальним для ЗІП I.

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

Нехай X = Y = [0,1] і на X задана рівномірна імовірнісна міра. Нехай відношення пошуку є ставлення ">" для дійсних чисел. Нехай бібліотека складається з одного запису V = {3/4}. Нехай базове безліч має вигляд Т = (F, 0), де

Розглянемо ЗІП I = ( X , V,>). оскільки

то Хз / 4,> = } Х & 1а> А ля будь-якого а 6 (0,1 / 2). Розглянемо ІГ U a , що складається з двох послідовно з'єднаних ребер, початок першого з яких є корінь ІГ, а кінець другого - лист, яким приписана запис 3/4, першого ребра відповідає предикат / ^, а другого - / *. Неважко бачити, що T (U a ) =

1 + а + 1/4 = 5/4 + а. Очевидно, що Т (/, F) = inf {T (U a ): а € (0,1 / 2)} = 5/4, але не існує ІГ, чия складність дорівнює 5/4.

Скажімо, що якась вершина ІГ досяжна з кореня на запиті хX або просто досяжна на запиті х 6 Х } якщо функція фільтра цієї вершини на запиті х дорівнює 1.

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

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

В іншому випадку ребро називаємо істотним.

Легко помітити, що видалення несуттєвих ребер з ІГ не змінює функціонування ІГ і не збільшує його складність. Тому завжди в подальшому ми будемо розглядати ІГ з точністю до несуттєвих ребер, а точніше будемо вважати, що всі ребра в ІГ - суттєві.

Теорема 11 (про існування оптимальних графів). Якщо безліч запитів X звичайно, то для будь-якої ЗІП I = (X, Y, р) і будь-якого базового безлічі Т = (F, G) такого, що 14 (1 yJ 7 ) ф 0, існує оптимальний ІГ над базовим безліччю Т.

Доведення. Зауважимо, що з за кінцівки безлічі X безлічі F і G кінцеві. Справді, якщо Х = т, то число предикатів, визначених на X максимум, ніж 2 т . Отже, | .F | <2 m . Так як область значень будь-якого перемикача є початковий відрізок натурального ряду, то будь-який перемикач над X приймає не більше т значень, отже G <т т .

Для довільного ІГ U позначимо через N (U) підграф графа U, що складається з ребер, що мають ненульову складність.

Візьмемо довільний ІГ ЩU (I, F). Позначимо U ' = {U е Щ1, Т) : T (U) <T (U 0 )}, ЛГ = {N (U) : U € W'}. Очевидно, що

Для доказу існування оптимального ІГ для ЗІП I нам досить показати кінцівку безлічі Л / 7 .

л

Нехай IFuCj = п. Нехай М - безліч, що складається з тотожно нульового предиката і всіх предикатів, отриманих з предикатів безлічі FuG за допомогою операцій кон'юнкції і диз'юнкції. Зрозуміло, що М <rnin (2 m , 2 2n ). Позначимо М ' = {/ G М: P (Nj)> 0}. Нехай mmP (N /) = р За

визначенню г> 0. Оскільки для будь-якого ІГ над Т функції фільтрів вершин належать множині Л /, то складність будь-якого предикатного ребра ІГ над Т або нульова, або не менше ніж г, а складність будь-якого перемикача ребра з ненульовий складністю не менш ніж r / m . Звідси в будь-якому ІГ з безлічі Л / 7 число ребер але лише T (Uq) • га / г.

Так як з кінцівки множин FuG слід кінцівку числа різних навантажень ІГ, то, значить, безліч Л / 7 звичайно.

Що і доводить теорему. ?

вправи

2.27. Нехай X = {1,2, ..., N}, S = (X, X, =, Р, С) - тип пошуку

у

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

  • 1. Порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.16.
  • 2. Порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.17.
  • 3. Порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.18. Для базового безлічі і ЗІП, наведених у вправі 2.18, побудуйте інформаційний граф зі складністю, що не більшою, ніж 1.48.
  • 4. Порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.19, якщо N = 100. Для якого значення параметра т складність буде мінімальна. Для якого значення параметра т В-складність буде мінімальна. Для якого значення параметра тп обсяг буде мінімальним.
  • 2.28. Якщо X = {1,2, ..., 7V} і на X задана рівномірна імовірнісна міра, то порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.20.
  • 2.29. Нехай на безлічі запитів X = [0,1) задана рівномірна імовірнісна міра. Порахуйте складність, В-складність і обсяг інформаційного графа, отриманого при вирішенні вправи 2.21.
  • 2.30. Нехай на безлічі запитів Xint = {(u, v): 0
 
<<   ЗМІСТ   >>