Задачи о близости
Задачи о близости, которые состоят в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объектузапросу, так же, как и задачи поиска идентичных объектов, очень распространены в информационных системах и как самостоятельные задачи, и как задачи, возникающие при декомпозиции более сложных задач поиска. В частности, мы тоже будем использовать задачи о близости при решении… Читать ещё >
Задачи о близости (реферат, курсовая, диплом, контрольная)
Задачи о близости, которые состоят в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объектузапросу, так же, как и задачи поиска идентичных объектов, очень распространены в информационных системах и как самостоятельные задачи, и как задачи, возникающие при декомпозиции более сложных задач поиска. В частности, мы тоже будем использовать задачи о близости при решении многомерной задачи интервального поиска и задачи о доминировании.
Среди работ, в которых исследуются задачи о близости, быть может, в более общей постановке, можно выделить, например, следующие [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) с таким отношением поиска назовем второй задачей о близости.