Логарифмический поиск. 
Интеллектуальные системы

Пусть.

Отметим, что N/ € а для любого предиката / € F uGi, т. е. базовое множество Т измеримо. Поскольку для любой записи У € Yint Ху, Pint 6 Fy то Т полно для типа S_int- Справедлива следующая теорема.

Теорема 15. Пусть I = {Xi_ni, V, p_int) — ЗИП типа Si_nt} где V = {j/i,… _Уук}, причем 0 < t/i < … < у* < 1; Т — базовое множество, определяемое соотношениями (2.28) — (2.30). Тогда

Доказательство. Построим первое дерево бинарного поиска для библиотеки V, описанное в разделе 2.4.1, но только нагрузку переключательных вершин мы будем брать из множества, а вместо предикатов /_=>0 использовать предикаты Xa, p_int €^{iОбозначим} это дерево через D.

Для обозначения Vp будет использован тот же смысл, что и в разделе 2.4.1.

Для удобства дальнейшего изложения назовем множество переключательных ребер дерева D переключательной частью дерева D, а множество предикатных ребер — предикатной частью дерева D.

Обозначим лист, которому соответствует запись у*, через а, (г = 1 , к). Из каждого листа or* (г = 1, А: — 1) выпустим ребро, ведущее в лист а*+1, и припишем ему предикат Ху"+ьр"п" € ^1;

Это множество из (к — 1)-го ребра назовем правосторонней концевой цепью.

Полученный граф обозначим через Uy.

Отметим одно достаточно очевидное свойство графа Uy. Пусть (5 — вершина графа Uy, не являющаяся листом. Пусть Vp = {y", ffc+i"*" «y;b Тогда.

Покажем, что Uy решает ЗИП I. По теореме 9, для этого достаточно показать, что.

Qi = Xy_itp_xnt Аля любого i € {1,к}.

Доказывать это будем индукцией по г.

Базис индукции, г = 1.

В лист Qi ведет единственное ребро из вершины, которую обозначим через ft. Очевидно,.

ai = Wr&Xybp_in** Через yj обозначим максимальную запись в библиотеке Vp>. Примем с — у₇, если j ф к, и с = 1, если j = к. Очевидно, с>у. Тогда.

то есть tp_ai = XyuPint-

Индуктивный переход. Предположим, что для некоторого i > 1 функция фильтра листа а" равна y?_ai = Ху", р"_п*;

Рассмотрим лист oti+ (г+ 1 < к). В него ведут два ребра: из листа Qi и некоторой вершины /?, не являющейся листом. Пусть Vi и yj — минимальная и максимальная записи в библиотеке Vp соответственно. Пусть.

Тем самым мы показали, что Uv решает I.

Покажем, что.

Рассмотрим произвольный запрос х G Хш- Поскольку через переключательную часть дерева D пролегает единственная проводящая цепь, и ее длина не превышает ] log₂ А;[— 1, то на любом запросе будет вычислено не более чем ] log₂ А:[-1 переключателей. Далее на запросе х вычисляются один или два предиката, соответствующих предикатным ребрам из предикатной части дерева D, растущим из вершины, в которую ведет проводящая цепь. Таким образом, суммарная сложность дерева D не превышает ] log₂ /c[-f 1.

Осталось подсчитать сложность правосторонней концевой цепи. Из каждого листа а" (г = 1, А: — 1) исходит одно ребро и его сложность равна Р (0(у{, рш)).

Следовательно,.

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

Алгоритм поиска, соответствующий графу ?/у" построенному в доказательстве теоремы 15, состоит в следующем. В упорядоченной по возрастанию библиотеке с помощью бинарного поиска за log₂ к шагов находится самая левая запись, находящаяся не левее левого конца запроса. Затем слева направо, начиная с найденной записи, просматриваются записи и сравниваются с правым концом запроса, и если оказывается, что очередная запись не больше правого конца, то эта запись включается в ответ, а если больше, то поиск прекращается, то есть — это традиционный алгоритм решения данной задачи поиска с помощью структуры данных, называемой прошитым двоичным деревом [52]. Там же [52, стр. 93] утверждается, что описанный алгоритм оптимален как по времени поиска, так и по памяти, но имеется в виду время в худшем случае, а оптимальность понимается по порядку.