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

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

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


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

Бинарный поиск.

Если V — конечное подмножество X, то через шах у будем обозначать такое утах € V, что для любых у € V

у€ У

выполнено у ^ Ушах-, И ЧСрСЗ 1ШП у обозначим такое У minV, что для

yGV

любых у € V выполнено утп ^ У-

Справедлива следующая теорема.

Теорема 12. Если I = (X, V, pid)задача поиска идентичных объектовf т. е. задача типа Sid, ?Ып ~ базовое множество, определяемое соотношениями (2.1)-(2.5), то

Доказательство. Пусть V = к.

Построим ИГ Dl(V), имеющий вид дерева, следующим образом.

Возьмем бинарное сбалансированное дерево с к концевыми вершинами, высоты ]log2 к[, все ребра которого ориентированы от корня к концевым вершинам. Если в этом дереве есть внутренняя вершина, из которой исходят ребра, ведущие одно в концевую вершину, а другое во внутреннюю (если такая вершина есть, то она только одна), то из концевой вершины, в которую ведет одно из этих ребер, выпустим одно ребро. Полученное дерево обозначим D. Объявим концевые вершины этого дерева листьями и сопоставим им слева направо в порядке возрастания элементы из V. (Говоря о дереве, мы подразумеваем некоторую его укладку, и направления “влево”, “вправо” определяются уже на этой укладке.)

Пусть Р — произвольная внутренняя вершина дерева D. Обозначим через Vp множество записей, соответствующих листьям, схемно достижимым из р. Пусть р' — вершина, в которую ведет левое (если оно одно, то единственное) ребро из р. Пусть

Объявим все внутренние вершины дерева D, из которых исходят ребра, ведущие во внутренние вершины, вершинами переключения и для каждой такой вершины р левому ребру, из нее выходящему, припишем 1, а правому — 2, а самой вершине припишем переключа-

тель 9<,уЛх)-

ИГ, полученный из дерева D после определения таким образом нагрузки, обозначим Dl(V) и будем называть первым деревом бинарного поиска.

Все ребра дерева D, входящие в листья, объявим предикатными и припишем каждому такому ребру, ведущему в лист с записью г/, предикат /=,у(я).

Покажем, что Dl(V) разрешает задачу I = (Ху Vypid)- Возьмем произвольную запись у ? V. Пусть а — лист D1(Vr), которому приписана запись у. В этот лист ведет единственная цепь, состоящая из не более чем ] log2 к[ ребер, причем все эти ребра, кроме последнего, переключательные. Последнее ребро в цепи — предикатное с предикатом /=>у(х), и его проводимость на запросе у равна f=,y(v) — 1- Покажем, что проводимость остальных ребер цепи на запросе у равна 1. Возьмем произвольно одно из этих ребер (0,0'). Если (0у 0') — левое, исходящее из то у ? Vp> и предикат, приписанный вершине 0, 9^,у0(у) = 1, так как у -<ур = max у'. Если (0^0')

V'€Vp>

правое ребро, исходящее из 0} то у ур и д<,ур(у) = 2, тем самым проводимость ребра {0,0') в обоих случаях равна 1. Следовательно, фа(у) = 1. Так как ребро, ведущее в лист а, имеет нагрузку /=,у, то для любого запроса х ф у <ра{х) = 0.

Таким образом, мы показали, что Q(a:) = /=,у(я)- Учитывая произвольность листа а и теорему 1, получим, что ИГ Dl{V) решает задачу I = (Х,У,р^).

Подсчитаем объем ИГ Dl(V).

Поскольку Dl(V) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве D1(Vr) нет вершины с полустепенью исхода 1, то в Dl(V) будет ровно 2 • к — 2 ребра, а если в дереве Dl(V) есть вершина с полустепенью исхода 1, то в Dl(V) будет 2 • к — 1 ребро. Отсюда следует, что

Подсчитаем сложность ИГ Dl(V).

Рассмотрим произвольный запрос х ? X. Как мы показали выше, активные на этом запросе вершины графа Dl(V) (вершина 0 активна на запросе, если <рр(х) = 1) образуют единственную цепь. Причем в этой цепи не более чем ]log2 к[ — 1 переключательных вершин и одна вершина, из которой исходит не более двух ребер с предикатами. Тем самым

Отсюда с учетом (2.6) сразу следует, что

Нижняя оценка для Т(/, Тып> 2Л: — 1) следует из теоремы 9, поскольку задача поиска идентичных объектов является задачей, обладающей В -свойством.

Тем самым теорема доказана.

Отметим, что первое дерево бинарного поиска соответствует стандартному алгоритму бинарного поиска в версии Боттенбрука [122, с. 214).

Упражнения

2.1. Пусть / = (Ху V, рс) — задача о близости, где X = {1,2,..., N}, V С Ху рс — отношение поиска, задаваемое соотношением на X х V и определяемое соотношением (1.11). По аналогии с поиском идентичных объектов постройте ИГ, разрешающий задачу о близости / методом бинарного поиска. Получите соответствующие оценки сложности.

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