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

Неформальное описание алгоритма.

Пусть абсциссы точек библиотеки V = Ух = (у/,У*), г = l,...,fc, упорядочены

по возрастанию: у ^ у ^ $ у?- Для упрощения изложения будем

считать, что все точки yj различны, поскольку при их совпадении сложность получаемых ИГ только уменьшается.

Пусть М е N, М О, и <*1,... ,с*а/> 0 < а* < 1, г = 1,... , М —

м

некоторые рациональные числа такие, что а» = 1.

«=1

Для любого q € {1,...,М} положим = 0, f*ei+...+«,+1 = причем здесь и везде далее, если некоторое действительное число используется как целое, то подразумевается целая часть этого числа. Множество

назовем у-й сеткой, а интервалы вида j = 1,..., fc°1+‘"+a«,

назовем интервалами g-й сетки. Точки у-й сетки делят каждый интервал (q — 1)-й сетки на частей. В каждом интервале I=

= Очевидно, самая последняя сетка будет иметь вид

Мм = {If = у), j = l,...,k}.

Если М > 1 и q Е {2,..., М}, то обозначим

Под одномерным интервальным поиском понимается задача типа Sint = №nt)[0> !)>Pmt)> гДе Pint определяется соотношением Сu>v) Pint y&u^-y^v.

Поиск по запросу х = (ui,vi,U2,V2) предлагаемым алгоритмом проводится в М этапов.

  • 1 этап
  • 1. Среди точек множества N1 U {1} ищется точка, ближайшая справа к щ. Пусть это /*, р G {1,..., kQl -f 1}.
  • 2. Среди точек множества {/} | j = р — 1,..., A;ai} ищется точка, ближайшая слева к v. Пусть это /J, г 6 {р - 1,..., ка1}.
  • 3. Если р < г, то для упорядоченных ординат у? тех точек библиотеки V, абсциссы которых удовлетворяют условию /j, ^ yj < < мы решаем одномерную задачу интервального поиска, где в качестве запроса берется отрезок х = [иг, иг]*
  • 4. Если М = 1 и /J = у/ для некоторого i € {1, то проверяем

принадлежность ординаты yf отрезку [иг, иг] и в зависимости от результата проверки включаем или не включаем точку у,- = = (у?, yl) в ответ задачи.

5. Если М > 1, то переходим ко второму этапу.

Случай когда s ^ t

Рис. 4.2. Случай когда s ^ t

q этап (2 ^ q ^ M)

Пусть lj~l — точка, ближайшая справа к щ на (q — 1)-й сетке, lj~l — точка, ближайшая слева к v на (q — 1)-й сетке. Эти точки являются левыми концами 5-го и t-го интервалов (q — 1)-й сетки соответственно.

  • 1. Если 5 ^ t (см. рис. 4.2), то:
  • 1.1. среди точек множества A/^_j ищем точку, ближайшую справа к ui; обозначим найденную точку
  • 1.2. среди точек множества Л/J7 ищем точку, ближайшую слева к Vi обозначим найденную точку ?/;;
  • 1.3. для упорядоченных ординат yj тех точек библиотеки V, абсциссы которых yj удовлетворяют условию ^ yj <
  • 1, < ZJ”решаем одномерную задачу интервального поиска с запросом х' = [u2}V2]
  • 1.4. для упорядоченных ординат уj тех точек библиотеки V, абсциссы которых yj удовлетворяют условию ^ уj <

< решаем одномерную задачу интервального поиска С запросом X' = [U2,V2].

  • 2. Если t = 5 — 1 (см. рис. 4.3), то:
  • 2.1. среди точек множества •Л/’/_1 ищем точку, ближайшую справа к ui; обозначим найденную точку
  • 2.2. пусть ? — точка, предшествующая точке ?' на q-й сетке; среди точек множества Л/^_ v не меньших ?, ищем точку, ближайшую слева к v обозначим ее
  • 2.3. если то для упорядоченных ординат yj тех точек

библиотеки V, абсциссы которых yj удовлетворяют условию

^ yj < решаем одномерную задачу интервального поиска, где в качестве запроса берется отрезок х' = [112,1/2].

  • 3. Если q = М и f" = у для некоторого г € {1,..., А:}, то проверяем принадлежность ординаты yj отрезку [^2,^2] и в зависимости от результата проверки включаем или не включаем точку г/,- = = (у>Уи в ответ задачи.
  • 4. Если q < М, то осуществляем переход к следующему этапу.

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

Случай когда t = s — 1

Рис. 4.3. Случай когда t = s — 1

Очевидно, что при М = 1 описанный выше многоэтапный алгоритм совпадает с алгоритмом решения двумерной задачи интервального поиска, приведенном в разделе 4.2.

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

Популярные страницы