Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 241
Текст из файла (страница 241)
В рекурсивном вызове со входными данными Р, Х и )г сначала проверяется, выполняется ли условие ~Р1 < 3. Если оно справедливо, то в вызове просто применяется упомянутый выше метод решения "в лоб": сравниваются между собой все (~ з~) пар точек и возвращается пара точек, расположенных друг к другу ближе других. Если же 1Р) ) 3, то выполняется описанный ниже рекурсивный вызов в соответствии с парадигмой "разделяй и властвуй". Разделение. Выполняется поиск вертикальной прямой 1, которая делит множество точек Р на два множества Рь. и Рд, такие, что ~Рь~ = ЙР1/21, ~1Рд1 = (3Р~ /2), все точки множества Рг. находятся слева от прямой 1 или на зтой прямой, а все точки множества Рд находятся справа от прямой 1 или на зтой прямой. Массив Х разбивается на массивы Хг.
и Хд, содержащие точки множеств Рг. и Рд соответственно, отсортированные в порядке возрастания координаты х. Аналогично массив У разбивается на массивы Уг. и Уд, содержащие соответственно точки множеств Рг. и Рд, отсортированные в порядке монотонного возрастания координаты у. Властвование. После разбиения множества Р на подмножества Рг. и Рд выполняются два рекурсивных вызова: один — для поиска пары ближайших точек в множестве Р~„а другой — для поиска пары ближайших точек в множестве Рд. В качестве входных данных в первом вызове выступает подмножество Рг, и массивы Хь и Ъ'ь, во втором вызове на вход подаются множество Рд, а также массивы Хд и Уд.
Обозначим расстояния между ближайшими точками в множествах Рг. и Рд как бг. и бд соответственно; введем также обозначение б = ппп(бь, бд). Комбинирование. Ближайшая пара либо находится друг от друга на расстоянии б, найденном в одном из рекурсивных вызовов, либо образована точками, одна из которых принадлежит множеству Р~„а вторая — множеству Рд. В алгоритме определяется, существует ли пара таких точек, расстояние между которыми меньше б. Заметим, что если существует такая "пограничная" пара точек, расстояние между которыми меньше б, то обе они не могут находиться от прямой 1 дальше, чем на расстоянии б. Таким образом, как видно из рис.
33.11, (а), обе эти точки должны лежать в пределах вертикальной полосы шириной 2б, в центре которой находится прямая 1. Для поиска такой пары (если она существует) в алгоритме выполняются описанные ниже действия. 1. Создается массив У' путем удаления из массива У всех точек, не попадающих в полосу шириной 2б. Как и в массиве У, в массиве Г точки отсортированы в порядке возрастания координаты у.
!ООО Часть Г71 Избранные темы 2. Для каждой точки р из массива У' алгоритм пытается найти в этом же массиве точки, которые находятся в б-окрестности точки р. Как мы вскоре увидим, достаточно рассмотреть лишь 7 точек, расположенных в массиве У' после точки р. В алгоритме вычисляется расстояние от точки р до каждой из этих семи точек, и отслеживается наименьшее расстояние между точками б', вычисленное по всем парам точек в массиве У'.
3. Если б' ( 6, то в вертикальной полосе действительно содержится пара точек, которые находятся одна к другой ближе, чем те, которые были найдены в результате рекурсивных вызовов. В таком случае возвращаются зта пара точек и соответствующее ей расстояние б'. В противном случае возвращаются пара ближайших точек и расстояние между ними 6, найденные в результате рекурсивных вызовов. В приведенном выше описании опущены некоторые детали реализации, необходимые для сокращения времени работы до величины 0(п 1яп). После доказательства корректности алгоритма будет показано, как реализовать этот алгоритм так, чтобы достичь желаемой ~ранним времени работы.
Корректность Корректность описанного алгоритма поиска пары ближайших точек очевидна, за исключением двух аспектов. Во-первых, ограничивая рекурсивный спуск условием ~Р~ < 3, мы гарантируем, что никогда не придется решать вспомогательную задачу, в которой задана только одна точка. Второй аспект заключается в том, что требуется проверить всего 7 точек, расположенных в массиве У' за каждой точкой р; далее будет приведено доказательство этого свойства. Предположим, что на некотором уровне рекурсии пару ближайших точек образуют точки рг, е Рг. и рл е Рн.
Таким образом, расстояние б' между этими точками строго меньше 6. Точка рг. должна находиться слева от прямой 1 на расстоянии, не превышающем величину б, или на самой этой прямой. Аналогично точка рн находится справа от прямой 1 на расстоянии, не превышающем величину б, или на самой этой прямой. Кроме того, расстояние по вертикали между точками рь и рд не превышает б.
Таким образом, как видно из рис. 33.11,(а), точки рз. и рн находятся внутри прямоугольника б х 26, через центр которого проходит прямая 1. (В этот прямоугольник могут попасть и другие точки.) Теперь покажем, что в прямоугольнике размером б х 26 может содержаться не более восьми точек из Р. Рассмотрим квадрат 6 х 6, который составляет левую половину этого прямоугольника. Поскольку расстояние мелщу любой парой точек из множества Рз, не меньше б, в этом квадрате может находиться не более четырех точек (рис. 33.11, (б)).
Аналогично в квадрате размером 6 х б, составляющем правую половину указанного прямоугольника, также может быть не более четырех точек. Таким образом„в прямоугольнике 6 х 26 содержится не более восьми точек. (Заметим, что, поскольку точки на прямой 1 могут входить либо в множество Рз,, либо в множество Рл, на этой прямой может лежать до четырех точек.
Этот предел достигается, если имеется две пары совпадающих точек, причем в каящой паре одна из точек принадлежит множеству Рь, а другая — множеству 1089 Глава ЗЗ. Вычисяитгльлая геаиеюрия )я Рг,ф-( Ра Рь и-) — 6 — з+я — 6 — з б,' -'--"-', ~,.,"-Рл': ,-.р;,е-::::4::-,-,Ф;- ° $:-г.х,,1.";х.ь-; одва — в Р,, б у г'-.-"":.:"; ',': '! -*. -;",: ..' .".!„г'«: "..*":*-' '-.. *.ч Совпадающие гочки ,' ~!:!~::~';::: !!ьюа((ФУ.'-,!':.';:!::~, одна — в р,, ° ( ° ! одна — в Р (6) (а) Рис. ЗЗЛ).
Ключевые концепции, используемые в доказательстве того, что алгоритму поиска пары ближайших пмек досппочно проверить только семь точек, следующих за каппой точкой в массиве У'. (в) Если точки рь Е Рь и ри Е Рл нахолятся на расстоянии меньше б одна от другой, то онн должны располагаться в пределах прямоупюьника б х 26, посредине юторого проходит прямаа (. (6) Как четыре точки, попарно расположенные на расстоянии не менее б одна от другой, могут располагаться в пределах квадрата б х б. Слева показаны четыре точки из Рю а справа— четыре точки из Рн.
Прямоугальник б х 26 может содержать восемь точек, если на самом леле точки, показанные на прямой (, представаянп собой пары совпадающих точек, нз которых одна находится в Рю а другая — в Рн. Рн. Кроме того, одна из этих пар находится на пересечении прямой ( и верхней стороны прямоугольника, а другая — на пересечении прямой ( и нижней стороны прямоугольника.) Поскольку в прямоугольнике указанных выше размеров может содержаться не более восьми точек множества Р, очевидно, что достаточно проверить семь точек, расположенных в массиве У' после каждой точки. Продолжая придерживаться предположения о том, что пара ближайших одна к другой точек состоит из точек рг. и рл, без потери общности предположим, что в массиве У' точка рг, находится перед точкой рл.
В этом случае точка рл является одной из семи точек, следующих после точки рг, даже если точка рг. встречается в массиве У' настолько рано, насколько зто возможно, а точка рл — настолько поздно, насколько зто возможно. Таким образом, корректность алгоритма, предназначенного для поиска пары ближайших точек, доказана. Реализация и время работы алгоритма Как уже упоминалось, наша цель — сделать так, чтобы время работы представленного алгоритма описывалось рекуррентным соотношением Т(п) = 2Т(п/2) + 0(п), где Т(п) — время работы алгоритма для гг точек. Основная сложность — это добиться, чтобы массивы Хь, Хл, У(, и Уго которые передаются в рекурсивных вызовах, были отсортированы по соответствующей координате и чтобы массив )" был отсортирован по координате )г.
(Заметим, что если массив Х, который Часть Г72 Избранные темы передается в рекурсивном вызове, уже отсортирован, то разбиение множества Р на подмножества Рг и Рн легко выполнить за время, линейно зависящее от количества элементов.) Ключевое наблкщение состоит в том, что в каждом вызове следует сформировать отсортированное подмножество отсортированного массива. Например, пусть в каком-то отдельно взятом рекурсивном вызове заданы подмножество Р н массив У, отсортированный по юэординате у. В процессе разбиения множества Р на подмножества Рд и Рл нужно образовать массивы Уь и Ун, которые должны быть отсортированы по координате у, причем эти массивы необходимо сформировать в течение линейного времени. Этот метод можно рассматривать как антипод процедуры Мнкце, описанной в разделе 2.3.1: отсортированный массив разбивается на два отсортированных массива.
Эта идея реализована в приведенном ниже псевдокоде. 1 Пусть Ус[1..У.1епуЯ и Ун[1 ..У.1епуЯ вЂ” новые массивы 2 Уг,1епдМ = Ун.1епд1п = 0 3 Гог 1 = 1 го У. 1епд1Ь 4 Ы У[1] Е Рь 5 Уь.1епудз = Уь.(епугп+ 1 б Уь[Уь.1епдЯ = У[в] 7 е)зе Ун.1епудз = Ун. 1епд1п+ 1 8 Ун[Ун.1епд16] = У[1] Мы просто проверяем точки массива У в порядке нх расположения в этом массиве. Если точка У[1] принадлежит множеству Ры она добавляется в конец массива Уь; в противном случае она добавляется в конец массива Ун.
С помощью аналогичного псевдокода можно сформировать массивы Хы Хн и У'. Последний вопрос — как сделать так, чтобы точки были отсортированы с самого начала. Для этого следует выполнить их предварительную сортировку (ргезог6пй), которая осуществляется один раз перед первым рекурсивным вызовом. Отсортированные массивы передаются в первом рекурсивном вызове; затем они будут дробиться в рекурсивных вызовах до тех пор, пока это будет необходимо. Предварительная сортировка добавит ко времени работы алгоритма величину 0(п 1б п), но позволит выполнять каждый шаг рекурсии в течение линейного времени. Таким образом, если обозначить через Т(п) время обработки каждого шага рекурсии, а через Т'(п) — общее время работы всего алгоритма, то можно получить равенство Т'(п) = Т(п) + 0(п)яп) и )' 2Т(п(2) + 0(п), если и > 3, ]( 0(1), если и < 3 . Таким образом, Т(п) = 0(п 1я и) и Т'(п) = 0(п 1к и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
