Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
В следующих главах исследуются интересные приложения этой геометрической двойственности.
1.4. Модели вычислений
Главный методологический вопрос, с которым неизбежно сталкиваешься прежде всего при любом исследовании алгоритмов, заключается в тщательном описании принятой модели вычислений. Действительно, алгоритм, предложенный для решения определенной задачи, должен быть оценен в терминах его стоимости как некой функции от размера индивидуального экземпляра этой задачи. Принципиальная важность модели вычислений определяется следующим образом:
Модель вычислений определяет набор допустимых элементарных операций и стоимости этих операций. Элементарные операции — это такие операции, для каждой из которых мы назначаем фиксированную стоимость, хотя эта стоимость неодинакова для разных элементарных операций. Например, если элементарные операции обрабатывают отдельные цифры в числах (как в булевских функциях с двумя двоичными переменными, вычисляемыми на модели машины Тьюринга), то стоимость операции сложения двух целых чисел возрастает с ростом длины операндов, в то время как стоимость этой операции постоянна для модели, в которой операнды имеют фиксиро-
42
Гл. !. Введение
ванную длину (как в любой модели, ориентированной на представление реальных цифровых компьютеров). При выборе модели приходится идти на компромиссы между реальностью и математической строгостью, выбирая схему, которая отражает основные черты используемых математических методов и вместе с тем достаточно проста, чтобы провести тщательный анализ.
Какой же тип модели подходит для геометрических приложений? Чтобы ответить на этот центральный вопрос, нужно тщательно рассмотреть природу решаемых задач.
Как указано в разд. 1.3, главными объектами, которые рассматриваются в вычислительной геометрии, являются точки, принадлежащие пространству Ed. Хотя точка считается вектором в декартовых координатах, желательно, чтобы выбор системы координат не слишком влиял на время работы геометрического алгоритма. Это приводит к тому, что модель вычислений должна допускать необходимое преобразование (декартова базиса), причем его стоимость в расчете на одну точку может зависеть от числа измерений, но не от числа обрабатываемых точек.
С другой стороны, известно, что множество из N точек в пространстве размерности d может быть выражено по отношению к заданному декартову базису за время, пропорциональное N (напомним, что столько же времени по порядку нужно для «считывания» этих точек как исходных данных), поэтому мы можем с самого начала считать, что эти точки уже заданы в избранном декартовом базисе.
Задачи, возникающие в вычислительной геометрии, относятся к нескольким типам, которые мы для удобства сгруппируем в три следующих класса:
1. Поиск подмножества. В задачах этого рода задан набор объектов и требуется найти некое подмножество, которое удовлетворяет определенному условию. Например, поиск ближайшей пары на множестве из N точек или поиск вершин выпуклой оболочки множества. Важная черта задач о выборе подмножества заключается в том, что не нужно создавать никаких новых объектов; решение полностью состоит из элементов, которые заданы на входе.
2. Вычисление. Дано множество объектов, нужно вычислить величину некоего геометрического параметра на этом множестве. Допустимые элементарные операции в модели должны быть достаточно мощными, чтобы реализовать это вычисление. Предположим, например, что точки имеют целочисленные координаты. Чтобы найти расстояние между парой точек, надо уметь не только представлять иррациональные числа, но также извлекать квадратные корни. А в ряде задач нам могут понадобиться даже тригонометрические функции,
1.4. Модели вычислений
43
3. Распознавание1). Задача распознавания естественным образом связана с задачами «Поиск подмножества» и «Вычисление». В частности,
(1) Если в задаче о вычислении требуется найти величину параметра А, то в связанной с ней задаче распознавания D($&) требуется дать ответ ДА/НЕТ на вопрос типа: «Верно ли, что Л $г Л0?», где Л0 — константа.
(2) Если в задаче о поиске подмножества требуется найти подмножество заданного множества 5, удовлетворяющее определенному свойству Р, то в задаче Ъ(зФ) требуется ответ ДА/НЕТ на вопрос типа: «Верно ли, что 5' удовлетворяет Р?», где S' — подмножество S.
Легко заметить, что есть необходимость работать с действительными числами (а не только с целыми) и (на реальном компьютере) с соответствующими им приближениями. Однако при создании модели вычислений можно воспользоваться абстрактным понятием, чтобы избежать проблемы, связанной с округлением для приближенного представления действительного числа. Конкретно, возмем машину с произвольным доступом к памяти (РАМ), похожую на ту, что описана в [Aho, Hopcroft, Ullman (1974)] 2), но у которой каждая ячейка памяти способна хранить единственное действительное число. Следующие операции считаются элементарными и обладают единичной стоимостью (единичным временем выполнения):
1. Арифметические операции (-f-, —, X, /).
