Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

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


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Случай оптимальности перебора

Теорема 5. Если I = (X, V, р)ЗИП и Т = (F, 0) — измеримое базовое множество, такие, что для любой записи уV выполня-

етсяху,рF иО{у,р)( U Nf)^9,mo

VeFxv.p 7

Доказательство. Пусть V = {уьУ2>• • • >У*}- Каждому г 6 {l,fc}

сопоставим некоторый запрос Xi € 0(у,р) ( [J N/)- Легко

_ VeFxv.p У

видеть, что для любых таких i,j G {1, А:}, что i ф j, справедливо Ф %j’

Понятно, что U 6 U^T) Ф 0, так как ИГ, изображенный на рис. 1.5, соответствующий алгоритму перебора, разрешает ЗИП I. Обозначим этот ИГ через Uq.

Возьмем произвольный ИГ UU{I,F). Так как U разрешает ЗИП J, то для каждого i € {1, А:} существуют лист а», которому приписана запись у*, и цепочка ребер С», ведущая из корня в лист а*, которая проводит запрос Х{. Нетрудно заметить, что для любых таких i,j 6 {!,&}, что i ф j, цепочки С{ и Cj не пересекаются по ребрам, поскольку, если бы существовало ребро, принадлежащее и С», и С,, то нагрузка этого ребра принимала бы значение 1 одновременно и на х,- и на Xj, но, по определению х* и Xj таких функций в множестве F не существует. Отсюда сразу следует, что из корня ИГ U исходит по крайней мере к ребер, и, следовательно, для любого х 6 X T(U,x) ^ А, откуда T(U) ^ к и T(U) ^ fc, а в силу произвольности ИГ U имеем ^ к и Т(1,Т) ^ к. Но так как для ИГ Uo справедливо T(Uo) = = T(Uq) = А:, то Т(/, Т) = Т(/, Т) — к, что и требовалось доказать.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>