Региональный поиск
Cтраница 1
 |
Сколько точек юго-западнее р. [1] |
Региональный поиск в форме щее эти запросы, заклю - четырех запросов о доминировании, чается в том, что на плоскости существуют области удобной формы, внутри которых число доминирования Q является константой. [2]
При региональных поисках проводят гравиметрическую и магнитометрическую съемки в масштабе 1: 200000 для изучения регионального геологического плана всей территории с целью выделения основных структурных элементов и составления общей тектонической схемы, для определения мощности осадочных отложений и глубин залегания кристаллических пород в пределах всей нефтегазоносной провинции. [3]
Что касается регионального поиска, то в разд. & - /) - дерева), обладает большим временем поиска. Поэтому кажется, что избыток памяти является ключевым условием быстрого поиска. Как метод прямого доступа, так и метод дерева регионов служат примерами этой идеи. В действительности это примеры приложений, названных Бентли и Сэйксом задачами поиска, допускающими декомпозицию [ Saxe, Bentley ( 1979) ], в которых ответ на запрос относительно всего пространства получается как комбинация ( в данном случае как сумма) ответов на запросы относительно подходящего набора частей этого пространства. Остается открытым важный вопрос о существовании ( N, log N) - алгоритма для 2-мерного регионального поиска. Недавно Чазелле [ Chazelle ( 1983с) ], используя метод фильтрующего поиска, смог понизить потребность в памяти с N log N ло N log N / og log N, показав тем самым, что N log N не является нижней оценкой. [4]
После такого напоминания не составит труда воспользоваться деревом отрезков при региональном поиске. Начнем, как обычно, с двумерного случая. Дерево отрезков 7 ( 1, N) используется при поиске по х - координате. Каждый такой узел v соответствует множеству из ( E [ v ] - B [ v ]) абсцисс ( определения даны в разд. [5]
Применение диаграммы Вороного дает изящный метод получения довольно эффективного решения задачи кругового регионального поиска. Задача заключается в следующем: на плоскости заданы множество 5, содержащее N точек, и окружность С с центром в точке q ( запрос); требуется перечислить точки множества 5, попавшие внутрь С. Как обычно для задач регионального поиска, цель заключается в достижении оценки 0 ( f ( N) k), где k - размер множества точек, соответствующих запросу. Если эта цель достижима, то алгоритм характеризуется парой ( M ( N) f ( N)), где M ( N) - требуемый объем памяти. [6]
В следующих разделах показано несколько достаточно интересных и тонких методов, предложенных для задачи регионального поиска. Будет пролит свет на те трудности, которые до сих пор не позволяют построить оптимальные алгоритмы и которые непосредственно определяют соотношение между двумя важными ресурсами - временем запроса и объемом памяти. [7]
Чтобы соответствующим образом подготовиться к изложению существующих методов, нам придется начать с простейшего примера регионального поиска, который при совершенной своей тривиальности содержит существенные черты данной задачи: речь пойдет об одномерном региональном поиске. [8]
Хотя методы, используемые для решения этих двух типов задач, близки - мы только что видели, как региональный поиск может быть сведен к задаче о локализации точки, - удобно демонстрировать их отдельно. Остаток этой главы посвящен данному вопросу. [9]
Чтобы соответствующим образом подготовиться к изложению существующих методов, нам придется начать с простейшего примера регионального поиска, который при совершенной своей тривиальности содержит существенные черты данной задачи: речь пойдет об одномерном региональном поиске. [10]
 |
Региональный поиск прямым доступом. Адрес х-интервала локализуется методом произвольного доступа после нормализации. По этому адресу находится указатель к двоичному дереву поиска. [11] |
Заметим, что, хотя память удалось сократить с 0 ( N5) до 0 ( N3), время поиска осталось равным 0 ( ogN), поскольку и нормализация регионов, и одномерный региональный поиск используют О ( log АО времени. В массиве х имеется доступ к региону [2, 8], заданному нормализованными абсциссами ( рис. 2.31 ( Ь)); отсюда указатель направляет поиск к двоичному дереву. [12]
Перед тем как приступить к анализу эффективности данного метода, заметим, что дерево отрезков можно считать не только инструментом для разбиения любого отрезка на логарифмическое число кусков, но также и способом применения метода разделяй и властвуй к региональному поиску. [13]
 |
Иллюстрация применения метода дерева регионов к нашему постоянному примеру. Исходный регион разбит тремя стандартными отрезками ( а. Поисковые действия показаны на ( Ь. [14] |
Переходя теперь к анализу сложности метода, заметим, во-первых, что при d 2 каждый узел отнесения из проекции запросного региона на ось х ( их всего О ( log Л /)) порождает отдельную ( d - 1) - мерную задачу регионального поиска. [15]
Страницы: 1 2