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

Включающий поиск.

Рассмотрим следующий тип задач поиска:

где Вп — единичный п -мерный куб, т. е.

6

У — отношение поиска на Вп х Вп, определяемое следующим соотно- ь _

шением: (xi,...,xn) У (|/i,...,$/n) <=* > Ух, г = 1,п; о — алгебра

подмножеств Вп представляющая собой множество всех подмножеств Вп Р — равномерная вероятностная мера на сг, т. е. такая мера, что для любого х ? Вп выполнено Р(х) = 1/2п и для любого А С Вп выполнено Р(Л) = А/2п.

Задачи поиска, принадлежащие данному типу, есть разновидность задач, именуемых в литературе задачами включающего поиска (см., например, [93)), поэтому тип Sbool мы назовем типом включающего поиска, а задачи, принадлежащие этому типу, — задачами включающего поиска.

Напомним, что в соответствии с терминологией [13] гранью единичного n-мерного куба Вп называется множество

при этом число п — к называется размерностью этой грани.

Весом набора (ai,...,an) € Вп называют число его координат, равных 1. Множество вершин куба, имеющих вес к, называется к-м слоем куба Вп и обозначается В?. Номером набора а = (ai,..., ап) €

п

Вп назовем число ||ar|| = 2n“* • an. Будем считать, что наборы

*=1

в слое куба упорядочены в порядке убывания их номеров. Множество, состоящее из т первых наборов fc-ro слоя куба Вп, будем называть начальным отрезком длины т этого слоя.

Формула &; xf22 & ... & xfrr, где & — знак конъюнкции, оk G 6 {0,1}, = xik, X?k = Xi„, ik e {1,2,...,n>, к = 1,2,....r (r ^

^ 1 и 7i ^ l), называется конъюнкцией над множеством переменных Хп = {xi,X2,... ,хп}, а число г — длиной этой конъюнкции. Если

x%j ф Х{к при j ф к, то конъюнкция называется элементарной. Элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Множество элементарных монотонных конъюнкций от п переменных будем обозначать через К,п. Функцию тождественная единица будем считать элементарной монотонной конъюнкцией длины 0, т. е. будем считать, что она входит в множество АСП, кроме того добавим тождественную единицу и в множество переменных Хп.

Будем говорить, что две элементарные монотонные конъюнкции пересекаются по переменным, если в формулах, описывающих эти конъюнкции, встречаются одинаковые переменные.

Функция алгебры логики /(xi,...,x„) называется монотонной,

6

если для любых двух наборов а и из Вп таких, что а ^ /3, имеет место неравенство /(а) ^ /(/?)• Дизъюнкция элементарных монотонных конъюнкций есть монотонная функция. Множество монотонных булевых функций от п переменных будем обозначать через Мп.

Рассмотрим произвольную запись уВп. Нетрудно заметить, что если есть множество номеров координат вектора у,

которые равны 1, то характеристическая функция записи является элементарной монотонной конъюнкцией

Далее часто знак конъюнкции &; в формулах мы будем опускать.

Таким образом, согласно теореме 1 граф, разрешающий некоторую задачу включающего поиска, представляет собой многополюсник, реализующий некоторую систему элементарных монотонных конъюнкций. Отсюда согласно теореме 2 следует, что каждое из базовых множеств (ЛЛп, 0), (1Сп, 0) и п, 0) является полным для типа S&00/.

Следовательно, тип БьоЫ полностью удовлетворяет условиям теоремы 3, и, значит, для любой ЗИП / типа Бь0ы существует оптимальный ПИГ над любым из базовых множеств п, 0), п, 0) и п, 0).

Упражнения

3.1. Пусть V = {уьУ2>. • • ,Ук} С Вп и число единиц в наборе у* равно ti (г = 1,2,...,А:). Приведите мощностную нижнюю оценку для задачи

ь

включающего поиска I = (Вп, V, У).

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы