Мгновенное решение. 
Интеллектуальные системы

Пусть.

где Fi, G_y G2 определяются соотношениями (2.28), (2.29), (2.31).

Понятно, что для N/ 6 ст для любого / € G3.

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

Теорема 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₂ на переключатель д._%Тп 6 G$. Полученный информационный граф обозначим через U'_m.

Отметим, что для любого запроса х = (и, v)? Xj_nt если j = д, т (х)_} то j является минимальным числом, таким что j/m > и. Следовательно, вершина 02 с исходящими из нее ребрами функционально совпадает с деревом D_m_i, и, значит, ИГ U^ решает ЗИП I.

Что касается сложности графа U'_m, то по сравнению с ИГ U_m на любом запросе х? Xint^/m вместо ] log₂(m — 1)[ вычислений переключателей, соответствующих проводящей цепи дерева D_m_i, будет вычислен один переключатель д._>Тп. Поэтому.

Подсчитаем объем графа U' :

Здесь первое слагаемое соответствует ребрам, исходящим из 0о. Второе слагаемое есть количество ребер в дереве D. Третье и четвертое слагаемые соответствуют ребрам из правосторонней и левосторонней концевых цепочек. Пятое слагаемое — это ребра, исходящие из вершины 02- И, наконец, шестое слагаемое не меньше чем число ребер, исходящих из вершин 0[ (г = 1, т).

Возьмем в качестве параметра га = [2 с [log₂ &]] и получим.

что и доказывает утверждение теоремы 17. ?

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

Пусть нам дано множество V = {у_1}…, г/ь}, в котором мы должны производить поиск. Сначала упорядочим его в порядке возрастания. Если известна оценка сверху с функции плотности вероятности появления запросов, то в качестве параметра га возьмем га = 2c[log₂A, если же с неизвестна, то вместо нее можно взять любое число, например, с = 2. Затем для V построим множество номеров S = {si,…, s_m-i}, описанное выше. Отметим, что оно строится только однажды. Теперь поиск по произвольно взятому интервалу-запросу х = (u, v) производится следующим образом.

Сначала вычисляется длина запроса х.

Если она меньше чем 1/га, то в множестве V бинарным поиском находится ближайшая справа к точке и запись. Далее, начиная с этой записи, просматриваются слева направо все записи из V и сравниваются с правым концом запроса — точкой v — до тех пор, пока очередная запись не станет больше v. Тем самым в этом случае, помимо перечисления ответа, производится порядка log₂ к действий.

Если 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₂ А, чтобы хранить множество S.