Алгоритмы - построение и анализ (1021735), страница 222
Текст из файла (страница 222)
В качестве входных данных в первом вызове выступает подмножество Р~, и массивы Хг. и Уь1 во втором вызове на вход подается множество Рн, а также массивы Хи и Уд. Обозначим расстояния между ближайшими точками в множествах Рл и Ри через бь и дл соответственно; введем также обозначение б = ппп (бг„бн). Комбинирование. Ближайшая пара либо находится друг от друга на расстоянии б, найденном в одном из рекуррентных вызовов, либо образована точками, одна из которых принадлежит множеству Рг., а вторая — множеству Часть и'11. Избранные темы 1076 ,-е. Рд )7 ° , '! е в 1 '.. Р)'а ' е е ), Совпадающие точкиоаиав Р, одна в Р„ Совпаааюшие точкиоднав Р, одна в Рд а) б) Рд.
В алгоритме определяется, существует ли пара таких точек, расстояние между которыми меньше б. Заметим, что если существует такая "пограничнаяе пара точек, расстояние между которыми меньше Б, то обе они не могут находиться дальше от прямой 1, чем на расстоянии б. Таким образом, как видно из рис. 33.11а, обе эти точки должны лежать в пределах вертикальной полосы шириной 2б, в центре которой находится прямая 1.
Для поиска такой пары (если она существует) в алгоритме производятся описанные ниже действия. 1. Создается массив У' путем удаления из массива У всех точек, не попадающих в полосу шириной 2б. Как и в массиве У, в массиве У' точки отсортированы в порядке возрастания координаты у. 2. Для каждой точки р из массива У' алгоритм пытается найти в этом же массиве точки, которые находятся в б-окрестности от точки р. Как мы вскоре увидим, достаточно рассмотреть лишь 7 точек, расположенных в массиве У' после точки р.
В алгоритме вычисляется расстояние от точки р до каждой из этих семи точек, и отслеживается, какое из расстояний от между всеми парами точек в массиве У' является наименьшим. 3. Если выполняется неравенство бт < б, то в вертикальной полосе действительно содержится пара точек, которые находятся друг от друга ближе, чем те, что были найдены в результате рекурсивных вызовов. В этом случае возвращается эта пара точек и соответствующее ей расстояние й.
В противном случае возвращается пара ближайших точек Рис. 33.11. Основные концепции, которые используются при доказательстве достаточно- сти проверки 7 точек массива У' при поиске пары ближайших точек Глава 33. Вычислительная геометрия 1077 и расстояние между ними б, найденное в результате рекурсивных вызовов. В приведенном выше описании опущены некоторые детали реализации, необходимые для сокращения времени работы до величины О (и 1я и). После доказательства корректности алгоритма будет показано, как реализовать этот алгоритм так, чтобы достичь желаемой границы для времени работы. Корректность Корректность этого алгоритма, предназначенного для поиска пары ближайших точек, очевидна, за исключением двух аспектов. Во-первых, мы уверены, что в результате рекурсивного спуска до случая, когда ~Р~ < 3, никогда не придется решать вспомогательную задачу, в которой задана только одна точка.
Второй аспект заключается в том, что понадобится проверить всего 7 точек, расположенных в массиве У' ниже каждой точки р; далее будет приведено доказательство этого свойства. Предположим, что на некотором уровне рекурсии пару ближайших точек образуют точки рг. Е Рг, и ри Е Рл. Таким образом, расстояние б' между этими точками строго меньше б. Точка рг.
должна находиться слева от прямой 1 на расстоянии, не превышающем величину б, или на этой прямой. Аналогично, точка рп находится справа от прямой 1 на расстоянии, не превышающем величину б, или на этой прямой. Кроме того, расстояние по вертикали между точками рг. и рл не превышает б. Таким образом, как видно из рис. 33.11а, точки рг. и рл находятся внутри прямоугольника б х 2б, через центр которого проходит прямая 1. (В этот прямоугольник могут также попасть другие точки.) Теперь покажем, что прямоугольник размерами б х 2б может содержать не более восьми точек. Рассмотрим квадрат б х б, который составляет левую половину этого прямоугольника. Поскольку расстояние между любой парой точек из множества Рл не меньше б, в этом квадрате может находиться не более четырех точек (рис.
33.11б). Аналогично, в квадрате размерами б х б, составляющем правую половину означенного прямоугольника, тоже может быть не более четырех точек. Таким образом, в прямоугольнике б х 2б содержится не более восьми точек. (Заметим, что поскольку точки на прямой 1 могут входить либо в множество Рд, либо в множество Рл, на этой прямой может лежать до четырех точек. Этот предел достигается, если имеется две пары совпадающих точек, причем в каждой паре одна из точек принадлежит множеству Рь, а другая — множеству Рл. Кроме того, одна из этих пар находится на пересечении прямой 1 и верхней стороны прямоугольника, а вторая — на пересечении прямой 1 и нижней стороны прямоугольника.) Поскольку в прямоугольнике указанных выше размеров может содержаться не более восьми точек множества Р, очевидно, что достаточно проверить 7 точек, Часть Чй.
Избранные темы 1078 расположенных в массиве У' после каждой точки. Продолжая придерживаться предположения, что пара ближайших друг к другу точек состоит из точек рь и рл, без потери общности предположим, что в массиве У' точка рь находится перед точкой рл. В этом случае точка рн является одной из семи точек, следующих после точки рг,, даже если точка рь встречается в массиве У' так рано, насколько это возможно, а точка рн — настолько поздно, насколько это возможно.
Таким образом, корректность алгоритма, предназначенного для поиска пары ближайших точек, доказана. Реализация и время работы алгоритма Как уже упоминалось, наша цель заключается в том, чтобы показать, что время работы представленного алгоритма описывается рекуррентным соотношением Т (и) = 2Т (п/2) + О (и), где Т (и) — время работы алгоритма для и точек. Основная сложность — это добиться, чтобы массивы Хь, Хд, Уь н Ун, которые передаются в рекурсивных вызовах, были отсортнрованы по соответствующей координате и чтобы массив У' был отсортировал по координате у. (Заметим, что если массив Х, который передается в рекурсивном вызове, уже отсортировал, то разбиение множества Р на подмножества Рь и Рн легко выполнить в течение времени, линейного по количеству элементов.) Главное заключается в том, что в каждом вызове следует сформировать отсортированное подмножество отсортированного массива.
Например, пусть в какомто отдельно взятом рекурсивном вызове задано подмножество Р и массив У, отсортированный по координате у. В процессе разбиения множества Р на подмножества Рь и Рл нужно образовать массивы Уь и Ун, которые должны быть отсортированы по координате у. Более того, эти массивы необходимо сформировать в течение линейного времени. Этот метод можно рассматривать как антипод процедуры Миксе, описанной в разделе 2.3.1: отсортированный массив разбивается на два отсортированных массива. Эта идея реализована в приведенном ниже псевдокоде. 1 1епдй[Уь] +- 1епдй[Ун] — 0 2 1ог г' — 1 Фо 1епдй[У] 3 йо и У[1] е Рг, 4 1йеп 1епдй[Уь] ~ — 1епдй[Ул] + 1 5 Уь[1епдй[Щ У[т] 6 е1ве 1епдй[Ул] - 1елдй[Ул] + 1 7 Ул[1епдй[Ун]] У[1] Точки массива У просто обрабатываются в порядке их расположения в этом массиве.
Если точка У [1] принадлежит множеству Рс, она добавляется в конец массива Глава 33. Вычислительная геометрия 1079 Уг.; в противном случае она добавляется в конец массива Ул. С помощью аналогичного псевдокода можно сформировать массивы Хг., Хл и У'. Единственный оставшийся вопрос — как сделать так, чтобы точки были отсортированы с самого начала. Для этого следует провести их нредварнтелъную сортировку (ргезоп1пя); т.е.
это делается один раз леред первым рекурсивным вызовом. Отсортированные массивы передаются в первом рекурсивном вызове, а затем они будут дробиться в рекурсивных вызовах до тех пор, пока это будет необходимо. Предварительная сортировка добавит ко времени работы алгоритма величину О (и !к и), но позволит выполнять каждый шаг рекурсии в течение линейного времени. Таким образом, если обозначить через Т(и) время обработки каждого шага рекурсии, а через Т' (и) — общее время работы всего алгоритма, то получим равенство Т' (и) = Т (и) + О (и !к и) и соотношение (2Т (и/2) + О (и) если и > 3, Т(и) = (О (1) если и < 3.
Таким образом, Т (и) = О (и 1ки) и Т (и) = О (и !к и). Упражнения 33.4-1. Профессор предложил схему, позволяющую ограничиться в алгоритме поиска пары ближайших точек пятью точками, которые находятся в массиве У' после каждой из точек. Его идея заключается в том, чтобы точки, которые лежат на прямой 1, всегда заносились в множество Рь. Тогда на этой прямой не может быть пар совпадающих точек, одна из которых принадлежит множеству Р~„а другая — множеству Рл. Таким образом, прямоугольник размерами б х 2б может содержать не более шести точек. Какая ошибка содержится в предложенной профессором схеме? 33.4-2.
Покажите, как без ухудшения асимптотичесюго времени работы алгоритма убедиться в том, что передаваемое в самом первом рекурсивном вызове множество не содержит совпадающих точек. Докажите, что в этом случае достаточно проверять по 5 точек, расположенных после каждой точки в массиве У'. 33.4-3. Расстояние между двумя точками можно определить и не в евклидовом смысле, а по-другому. Так, ),„-расстояние (Ьы-б!з!апсе) между точками р1 и рз на плосюсти задается выражением Ох1 — хз) + )у1 — уз)™) Поэтому евклидово расстояние — это Ьз-расстояние.
Модифицируйте алгоритм поиска пары ближайших точек для Ь|-расстояния, известного как манхэттенское расстояние (Мап!запал йз!апсе). Часть ЧП. Избранные темы 1080 33.4-4. Для точек рг и рз, заданных на плоскости, Ь -расстоянием между ни- ми называется величина шах ((хг — хз), )уг — уз~). Модифицируйте ал- горитм поиска пары ближайших точек для Ь -расстояния. 33.4-5. Предложите, как изменить алгоритм поиска пары ближайших точек, что- бы избежать в нем предварительной сортировки массива У, но чтобы время его работы по-прежнему осталось равным О (п1яп).
(Указание: объедините отсортированные массивы Уг. и Ул в отсортированный массив У.) Задачи 33-1. Выпуклые слои Для заданного на плоскости множества точек Я вынунлме слои (соптех 1ауегз) определяются следующим образом. Первый выпуклый слой множества Я состоит из вершин СН (Я). Уберем эти точки и снова найдем выпуклую оболочку — ее вершины образуют второй выпуклый слой. Отбросим их и возьмем выпуклую оболочку остатка — ее вершины образуют третий выпуклый слой и т.д. Строго выпуклые слои определяются инлуктивно следующим образом. Первый выпуклый слой множества (~ состоит из вершин СН Я).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
