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

Задачи о близости

Задачи о близости, которые состоят в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объекту- запросу, так же, как и задачи поиска идентичных объектов, очень распространены в информационных системах и как самостоятельные задачи, и как задачи, возникающие при декомпозиции более сложных задач поиска. В частности, мы тоже будем использовать задачи о близости при решении многомерной задачи интервального поиска и задачи о доминировании.

Среди работ, в которых исследуются задачи о близости, быть может, в более общей постановке, можно выделить, например, следующие [70, 125, 144, 147, 150, 151, 165, 216|.

Пусть X — множество запросов, Y — множество записей. В задачах о близости (ЗоБ) в отличие от ЗИП отношение поиска задается не на X х У, а на X х V, где V — библиотека задачи о близости.

Пусть на множестве записей Y задано отношение линейного порядка Если у' ^ у и у' ф у, то будем писать у' -< у.

Отношение поиска pneari задастся на X х V и определяется соотношением

т. е. х pneari У, если у 6 V, ближайшее справа к х.

При выполнении этих условий ЗИП I = (X, V,pncari) назовем первой задачей о близости, а тип Sneari = {X, X, рпеаг) назовем типом первой задачи о близости.

Когда надо найти в библиотеке запись, ближайшую к запросу слева, то отношение поиска рпеаг2 определяется соотношением

Хрпеаг2У <=> (У ^ V)&(y ^ х) &(-i(3y')((y' 6 V)k(y' < х)&(у у'))).

ЗоБ I = (X, V, рпсаг2) с таким отношением поиска назовем второй задачей о близости.

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