Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 234
Текст из файла (страница 234)
пт] и вычисляющий значение р(Р1) для ! = 1,2,...,пз. Чему равно время работы этого алгоритма? б. Определим для произвольного образца Р[1 .. т] величину р" (Р) как пзах1«, р(Р;). Докажите, что если образец Р выбирается случайным образом из множества всех бинарных строк длиной пт, то математическое ожидание р'(Р) равно 0(1). в. Докажите, что приведенный ниже алгоритм поиска подстрок корректно находит все вхождения образца Р в текст Т[1 .. и] за время 0(р'(Р)п + гп), кеРет!Т10ы-МАтснек(Р, Т) ! т = Р.!епдй 2 и = Т.!епдй )г = 1+ р'(Р) 4 9=0 5 а=О 6 зчййе з < и — тп 7 !ГТ[з+д+1]==Р[д+1] 8 9 =9+! 9 !Гд == ги 10 рпп! "Образец найден со сдвигом" з 11 !Гд ==т или Т[з+д+1] ф Р[д+ 1] 12 з = з+ шах(1, [д//с]) 13 9=0 Этот алгоритм был предложен Галилом (Пай!) и Сейферасом (Бе!Гегаз).
Развивая зти идеи, они получили алгоритм поиска подстрок с линейным временем работы, использующий всего 0(1) памяти, кроме необходимой для хранения строк Р и Т. Заключительные замечания Связь поиска подстрок с теорией конечных автоматов обсуждается в книге Ахо (АЬо), Хопкрофта (Норсгой) и Ульмаиа (11!!шап) [5].
Алгоритм Кнута- Морриса — Пратга [213] разработан Кнутом (Кпц1Ь) и Праттом (Ргац) и независимо Моррисом (Могпз); результаты своих исследований они опубликовали совместно. Рейнгольд (Ке!пйо!й), Урбан (1!гЬап) и Грие (Опез) [292] привели альтернативную трактовку алгоритма Кнута — Морриса-Пратта. Алгоритм Рабина — Карпа был предложен Рабином (КаЬ1п) и Карпом (Катр) [200]. Галил (Оарй) и Сейферас (Бе!Гегаз) [125] разработали интересный детерминистический алгоритм поиска подстрок с линейным временем работы, в котором используется лишь 0(1) памяти сверх необходимой для хранения образца и текста. Глава 33. Вычислительная геометрия Вычислительная геометрия — это раздел информатики, изучающий алгоритмы, предназначенные для решения геометрических задач.
В современных инженерных и математических расчетах вычислительная геометрия, в числе других областей знаний, применяется в машинной графике, в робототехнике, при разработке СВИС, при автоматизированном проектировании, в металлургии, в статистике... Увы, книга слишком ограничена в обьеме для полного перечисления. Роль входных данных в задачах вычислительной геометрии обычно играет описание множества таких геометрических объектов, как точки, отрезки или вершины многоугольника в порядке обхода против часовой стрелки.
На выходе часто дается ответ на такие запросы об этих объектах, как наличие пересекающихся линий или параметры новых геометрических объектов, например выпуклой оболочки множества точек (это минимальный выпуклый многоугольник, содержащий данное множество). В этой главе мы ознакомимся с несколькими алгоритмами вычислительной геометрии в двух измерениях, т.е. на плоскости. Каждый входной объект представлен множеством точек (рп рз, рз,...), где каждая точка р, = (ко у,) образована парой действительных чисел яо рл е м'. Например, и-угольник Р представлен последовательностью вершин (рс, ры рз,..., р„з) в порядке обхода границы многоугольника Р. Вычислительная геометрия может работать в трех измерениях и даже в большем их числе, но визуализация подобных задач и их решений может оказаться очень трудной.
Однако даже в двух измерениях можно ознакомиться с хорошими примерами применения методов вычислительной геометрии. В разделе 33.1 показано, как быстро и точно ответить на такие основные вопросы о расположении отрезков: если два отрезка имеют общую конечную точку, то как следует перемещаться при переходе от одного из них к другому— по часовой стрелке или против часовой стрелки, в каком направлении следует сворачивать при переходе от одного такого отрезка к другому, а также пересекаются ли два отрезка. В разделе 33.2 представлен метод, известный под названием "выметание" (звеершя) или "метод движущейся прямой". Он используется при разработке алгоритма со временем работы 0(п 1к и), определяющего, имеются ли пересечения среди и отрезков.
В разделе 33.3 приведены два алгоритма "выметания по кругу", предназначенные для вычисления выпуклой оболочки множества и точек (наименьшего содержащего их выпуклого многоугольника): сканирование по Грэхему (ОгаЬаш'з зсап), время работы которого равно 0(п!яп), и обход по 10бг Гяаяа 33. Вычияяитеяьяяя гяаиетрия Джарвису ()агч(з'з шагсЪ), время выполнения которого равно 0(пй), где й — юличество вершин в оболочке. Наконец в разделе 33.4 приводится алгоритм на основе парадигмы "разделяй и властвуй" со временем работы 0(п1к и), предназначенный для поиска пары ближайших точек в заданном на плоскости множестве из п точек. 33.1. Свойства отрезков В некоторых представленных в этой главе алгоритмах требуется ответить на вопросы о свойствах отрезков.
Выпуклой комбинацией (сопчех сошЪ1па6оп) двух Различных точек Р1 = (хпУ1) и Рг = (хг,Уг) называетсл любаЯ точка Рз = (хз, уз), такая, что для неюторого значения о, принадлежащего интервалу О < а ( 1, выполняются равенства хз = гях1+ (1 — о)хг и Уз = пу1 + (1 — о)уг (пишут также рз = гяр1 + (1 — гя)рг). Интуитивно понятно, что в роли рз может выступать любая точка, которая принадлежит прямой, соединяющей точки р1 и рг, и находится между этими точками. Если заданы две различные точки, р1 и Рг, то отРезком (йпе зепшеп1) Р1Рг называетсв множество выпУклых комбинаций р1 и рг.
Точки р1 и Рг называются копечпымп тачками (епдро(пв) отрезка р1 рг. Иногда играет роль порядок следования точек р1 и рг, и тогда говорят о капраеленпам отрезке (41гесгед зейзпепг) р1рг. Если точка Р1 совпадает с началом координат (опя1п), т.е. имеет координаты (О, О), то направленный отрезок Рзрг можно рассматривать как вектор (чесгог) рг.
В этом разделе исследукпся перечисленные ниже вопросы. 1. Если заданы два направленных отрезка, рор| и роорг, то находится ли отрезок рор1 в направлении по часовой стрелке от отрезка рщорг относительно их общей точки ро? 2. Если заданы два отрезка, Рер1 и р|рг, то в какую сторону следует свернуть в точке р1 при переходе от отрезка Рлрз к отрезку р1рг? 3. Пересекаются ли отрезки Рзрг и Рзрх ~ На рассматриваемые точки не накладывается никаких ограничений. На каждый из этих вопросов можно ответить за время 0(1), что не должно вызывать удивления, поскольку объем входных данных, которыми выражается каждый из этих вопросов, равен О(1).
Кроме того, в наших методах используются только операции сложения, вычитания, умножения и сравнения. Не понадобится ни деление, ни вычисление тригонометрических функций, а ведь обе зти операции могут оказаться дорогостоящими и приводить к проблемам, связанным с ошибками округления. Например, метод "в лоб" при определении того, пересекаются ли два отрезка, — найти для каждого из них уравнение прямой в виде у = тх + 6 (где т — юэффициент наклона, а 6 — координата пересечения с осью у), вычислить точку пересечения этих прямых и проверить, принадлежит ли зта точка обоим отрезкам.
В таком методе при вычислении координат точки пересечения используется деление. Если отрезки почти параллельны, этот метод Чаешь Рл. Избранные шемы )ббг очень чувствителен к точности операции деления на реальных компьютерах. Изложенный в данном разделе метод, в котором удается избежать операции деления, намного точнее. Векторное произведение Вычисление векторного произведения составляет основу методов работы с отрезками. Рассмотрим векторы р) и рз, показанные на рис.
33.1,(а). Векторное ироизяеа)еиии (сгоаз рп)бцс() рг х рз можно интерпретировать как знаковое значение площади параллелограмма, образованного точками (0,0), р), рз и рг + рз = (хг + хз,))) + ()з). Эквивалентное, но более полезное определение векторного произведения — определитель матрицы': рг х рз = т)ет = хг9з — хзуг = — рз хрг. Если величина р) х рз положительна, то вектор рг находится по часовой стрелке от вектора рз относительно начала координат (О, О); если же векторное произведение отрицательно, то вектор р) находится в направлении против часовой стрелки от вектора рз. (См.
упр. 33.1.1.) На рис. 33.1,(б) показаны области, расположенные по часовой стрелке и против нее относительно вектора р. Граничный случай возникает, когда векторное произведение равно нулю. В этом случае векторы кбуглинеарны (со11шеаг), т.е. направлены в одном и том же нли в противоположных направлениях. л Р).
Рг l,::: :ь::! (0,0): л (а) (б) Рис. 33Л. (в) Векторное произведение аеаторов рг и рг представляет собой плопидь параллелограмма со знаком. (6) Область со светлой ппридоваой содержит векторы, находящиеся от р по часовой стрелке. Область с темной пприлошшй содержит векпэры, накодашиеся от р против часовой стрелки. Ня самом деле векшрное произведение — трехмерная концепция. Это вектор, перпендикулярный векшрям рг и рэ, направление «оторош определяется правилом правой руки, а величина равна )хг ля — хэлг ! Олиако в этой паве удобнее тракговать напорное произведение просто квк величину хгрг — хэуг. Глава 3 Ь Вычислительная геаметрая Рз Рз Против часовой стрелки По часовой стрелке Ро (а) Ро (б) Рнс.
33.2. Использованне векторного пронзведення для определенна направленна поворота последовательных стрезюв рор~ н р1рз в точке рз (выявляем, повернут лн направленный отрезок р~~3 по часовой стрелке нлн против нее относнтельно направленного отрезка Рсрз). (а) В случае направленнв против часовой стрелки выполняется поворот влево. (б) В случае нвщивлення по часовой стрелке выполнястса понорот вправо. (рз — ро) х (рз — ро) = (х( — хо)(уг — уо) — (хг — хо)(уз — уа) Если это векторное произведение положительно, рорз находится по часовой стрелке от рорз, если отрицательно — против часовой стрелки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
