Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Алгебраическим деревом решений {Reingold (1972); Rabin (1972); Dobkin, Lipton (1979)] на множестве переменных {х\, ..., хп} называется программа, записанная операторами LUL2.....Lf, следующего типа:
1. L,: Вычислить f(xu хп). Если /: 0, то перейти к Lh в противном случае к L,- (двоеточие обозначает любую из операций сравнения).
2. Ls: Останов и выдача ДА (в задаче распознавания вход принят).
3. Lt: Останов и выдача НЕТ (в задаче распознавания вход отвергнут).
В случае 1 f — это алгебраическая функция (полином степени равной порядку (/)). Далее предполагается, что программа не имеет возвратов, т. е. имеет структуру дерева Т, при которой каждый нелистовой узел v описывается выражением
Ы*1.....ха): О,
где fv — полином от Х\.....х„, а двоеточие обозначает отношение сравнения. (Заметим, что в этом определении каждый «арифметический отрезок пути» на рис. 1.8 свернут в следующий за ним узел сравнения.) Корень Т представляет начальный шаг вычислений, а его листья представляют возможные окончания и содержат все возможные ответы. Без потери общности допустим, что дерево Т двоичное *).
Хотя программа на алгебраическом дереве решений может оказаться намного более громоздкой, чем соответствующая РАМ-программа, однако для изучаемых нами классов задач обе программы ведут себя идентично. В частности, время работы РАМ-программы для худшего случая по меньшей мере пропорционально длине максимального пути от корня в дереве решений. Это подтверждает важность модели дерева решений, поскольку структура дерева достаточно удобна для получения оценок его высоты.
Говорят, что алгебраическое дерево решений имеет порядок d, если d — это наибольшая из степеней полиномов f0{xi, ... .... хп) среди всех узлов v из Т. Модель дерева решений 1-го порядка, или линейная модель, является мощным средством
') Заметим, что степень узла Т равна числу различных исходов операции сравнения. Допущение о двоичности дерева основано на том факте, что 6-кратное разветвление может быть заменено на k — 1 экземпляров 2-кратных разветвлений.
1.4. Модели вычислений
47
установления нижних оценок для многих задач; мы еще обсудим те весьма тонкие рассуждения, которые будут развиты в последующих главах, в сответствующем контексте (см. разд. 2.2, 4.1.3, 5.2, 8.4). Однако ограничиться рассмотрением только линейных деревьев решений нельзя по двум причинам. Первая и более важная состоит в том, что может случиться, когда любой из известных алгоритмов для данной задачи использует функции со степенью ^=2, поэтому нижняя оценка, основанная на модели линейного дерева решений, окажется бесполезной; если же исключить из рассмотрения подобную ситуацию, то возникнет вторая причина — оценка, основанная на модели линейного дерева решений, не применима к пока неизвестным алгоритмам, использующим функции более высоких степеней.
Весьма важные вклады в решение этих вопросов для d ^ 2 были недавно внесены работами Стили, Яо [Steele, Jao (1982)] и Бен-Ора [Веп-Ог (1983)], использующими классические понятия действительной алгебраической геометрии. Их подход основан на следующей очень простой идее: пусть Х\, Хг, ..., хп — параметры задачи распознавания, каждый индивидуальный экземпляр которой может считаться точкой в и-мерном евклидовом пространстве Еп. Задача распознавания определяет множество точек W <= Еп, т. е. она дает ответ ДА тогда и только тогда, когда (х\, xn)^W (можно сказать, что дерево решений Т решает задачу о принадлежности точки множеству W). Предположим, что нам заранее известно, исходя из природы этой задачи, число #(№) разделимых связных компонент W. Каждое вычисление соответствует какому-то однозначному пути vu V2, vi-i, vi в Т, где v\—корень, a vi — лист; с каждым узлом vj на этом пути (/=1, .... /—1) связана функция fVj(x\, хп), так что (х\, хп) удовлетворяет ограничению типа
fe/ = 0, или fo/>0, или fo/>0. (1.11)
Для приобретения некоторой интуиции рассмотрим вначале частный случай d = 1 (линейная модель дерева решений или вычислений), следуя за Добкином и Липтоном [Dobkin, Lipton (1979)]. Доказательство их теоремы следует ниже.
Пусть W Е Еп — множество истинности ') для данной задачи распознавания, и пусть обозначает число разделимых связных компонент W. Пусть Т — (двоичное) линейное дерево решений, реализующее алгоритм s?, который проверяет принадлежность W. С каждым листом Т связана область в Еп, и каждый лист является принимающим или отвергающим. А именно пусть
') То есть на выходах из W задача имеет ответ «ДА». — Прим. перев.
48
Гл. 1. Введение
{Wu ¦ ¦ ¦ , Wp) — компоненты W, {lu . .., U} — множество листьев, a Dj — область, связанная с //'). Лист // является:
Нижняя оценка для числа листьев г получается путем доказательства того, что г ^ Действительно, возьмем функцию У: {Wu W2, Гр}->{1, 2, г} такую, что Y(Wi) = = min{/: /е {I, 2, г} и D, П W, ^ 0}. Чтобы получить противоречие, предположим, что существуют два различных подмножества Wi и W,- таких, что Y(Wi) = Y(Wj)=h. Поскольку
Рис. 1.9. Иллюстрация к доказательству того, что Wt = Wj.
