|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[267] 35.11 (К упр. 35.3-4) (a)Звёздный многоугольник: из точки р видна любая точка его границы. (b)Многоугольник, не являющийся звёздным. Слева закрашена тень точки q, справа - тень точки ql. Ядро пусто, так как эти области не пересекаются. 35-3.4 Пусть даны многоугольник Р и точка q на его границе. Тенью (shadow) точки q называется множество всех точек г, для которых что отрезок qf не выходит за пределы многоугольника Р. Многоугольник Р называется звёздным (star-shaped), если внутри него есть точка р, из которой видна вся его граница (другими словами, р принадлежит тени любой точки границы многоугольника Р). Множество всех таких точек р называется ядром (kernel) многоугольника Р (см. рис. 35.11). Даны вершины зв/здного га-угольника Р, перечисленные в порядке обхода границы против часовой стрелки. Покажите, как можно найти СН(Р) за время 0(п). 35.3-5 Задача об отыскании выпуклой оболочки множества Q в режиме «on-line» (on-line convex-hull problem) состоит в следующем: нам дают га точек одну за другой; в каждый момент времени мы должны указать выпуклую оболочку всех точек, полученных к этому моменту. Можно применить проход Грэхема на каждом шаге заново, и тогда общее время работы алгоритма будет равно О (га2 lgra). Придумайте алгоритм, требующий времени О (га2). 35.3-6* Используя просмотр точек слева направо, найдите выпуклую оболочку га точек за время О (га lgra). 35.4. Отыскание пары ближайших точек Пусть теперь нам надо найти среди га 2 точек множества Q пару ближайших друг к другу точек. Расстояние между точками понимается в обычном смысле: точки р\ = (x\,yi) н р2 = (2:2,2/2) находятся на расстоянии у7(х\ - х2)2 + (у\ - У2)2 Вообще говоря, две точки могут совпадать (тогда расстояние между ними равно 0). Такая задача может возникнуть, например, в системах контроля за транспортом: полезно знать, какие два транспортных средства ближе всего друг к другу (риск столкновения) Если искать пару ближайших точек «в лоб», надо перебрать все С2 = 0(га2) пары точек. В этом разделе мы с помощью метода «разделяй и властвуй» построим алгоритм, время работы которого описывается рекуррентным соотношением Т(п) = 2Т(га/2) + 0(га), т.е. равно О (га lgra). Метод «разделяй и властвуй» для отыскания ближайших точек. Входные данные каждого рекурсивного вызова алгоритма состоят из подмножество Р С Q и двух массивы X и У. Каждый из массивов содержит точки подмножества р, но порядок в них разный: в массиве X точки расположены в порядке возрастания абсцисс, а в массиве У - в порядке возрастания ординат. Заметим, что мы не можем позволить себе сортировать точки при каждом вызове, так как в этом случае получится соотношение (как минимум) Т(п) = 2Т(п/2) +0(ralgra), т.е. Т(п) = 0(га1п2 га). (Мы увидим, как эту трудность можно обойти с помощью «предсортировки». Итак, пусть мы получили Р,Х и У. Если \Р\ 3, перебираем все пары точек (максимум три) и сравниваем расстояние. Если же \Р\ > 3, мы поступаем так: Разделяй (divide): Находим вертикальную прямую /, которая делит множество Р на два подмножества Pl и Pr половинного размера (\Рь\ = П-Р/2], \Pr\ =точки, лежащие на прямой /, как-то поделены между Pl и Pr). Массив X делим на массивы Xl и Xr, содержащие точки подмножеств Pl и Pr (сохраняя порядок); массив У делится на массивы Yl и Yr аналогичным образом. Властвуй (conquer): После деления Р на Pl и Pr, выполняем два рекурсивных вызова и находим пару ближайших точек в множестве Pl (входные данные этого вызова - подмножество Pl и массивы Xl и Yl), а также пару ближайших точек в множестве Pr (входные данные - Pr, Xr и Yr). Обозначим расстояния между ближайшими точками в подмножеств Pl и Pr через Sl и Sr. Положим S = min (Sl, deltaR). Соединяй (combine): Для всего множества Р парой ближайших точек является либо одна из найденных пар точек (расстояние S), либо некоторая «приграничная» пара точек, в которой одна точка принадлежит множеству Pl, а другая - Pr (если среди таких пар есть пара с расстоянием меньше S). Очевидно, что точки такой приграничной пары отстоят от прямой / не более, чем на S, т.е. находятся в симметричной относительно / вертикальной пограничной полосе шириной 2S (рис. 35.12 (а)). Чтобы найти такую приграничную пару, если она существует, проделаем следующее. 1.Создадим массив У/, поместив в него все точки из массива У, которые попадают в пограничную полосу (с той или иной стороны от прямой /). (Порядок сохраняем: массив У/ отсортирован по ординатам точек.) 2.Для каждой точки р массива Y ищем такие точки массива У, которые удалены от р не более, чем на S. Как мы вскоре увидим, достаточно рассмотреть только 7 соседних (в порядке возрастания ординат) точек в массиве У. Мы вычисляем расстояние от р до каждой из этих 7 точек. Выполнив это для всех точек р из У, находим 8/ - расстояние между точками массива У/, расположенными ближе всего друг к другу. 3. Если 8 < 8, то пара ближайших точек находится внутри вертикальной полосы и мы возвращаем эту пару точек и расстояние 5. В противном случае мы возвращаем пару, найденную при одном из рекурсивных вызовов, и расстояние 8. Сейчас мы докажем правильность этого алгоритма, а затем обсудим детали его реализации (необходимые, чтобы уложиться в О(гаlgra) действий. Правильность алгоритма Нужно понять лишь, почему достаточно сравнивать каждую точку полосы лишь с семью следующими за ней (в порядке возрастания ординаты). Сейчас мы в этом убедимся. Пусть (при некотором вызове) ближайшей парой точек является пара из точек pl £ Pl и рд £ Рд (рис. 35.12 (а)), и расстояние 8 между этими точками строго меньше 8. Точка pl должна находиться слева от / на расстоянии не более 8 (или на самой прямой); рд - справа на расстоянии не большем 8 (или на прямой). Кроме того, расстояние по вертикали между pl и рд также не превосходит 8. Следовательно (рис. 35.12 (а)), точки pl и рд можно поместить в прямоугольник размера 8x28, симметричной относительно прямой /. (Конечно, в него могут попасть и другие точки.) Покажем теперь, что внутри этого прямоугольника может быть не более 8 точек из множества Р. Рассмотрим его левую половину - квадрат 8x8. Все точки из Pl находятся на расстоянии не менее 8 друг от друга, поэтому в этом квадрате может быть максимум 4 таких точки (в каждой его четвертинке может быть не более одной точки), см. рис. 35.12 (Ь). В правой половине прямоугольника (не считая границы) точек из Pl быть не может, так что всего в прямоугольнике не более 4 точек из Pl - По аналогичным причинам там не более 4 точек из Рд. Заметим, что случай 8 точек действительно возможен: четыре точки из Pl могут быть в углах левого квадрата, а четыре точки из Рд - в углах правого (две точки будут общими для Pl и -Рд). а Теперь ясно, что что для каждой точки достаточно проверить 7 точек, непосредственно следующих за ней в массиве У: если между двумя ближайшими точками есть ещё 7 промежуточных (в порядке возрастания ординат), то все 9 точек попадут внутрь прямоугольника, а этого быть не может, как мы видели. Детали реализации и время работы алгоритма. Наша цель - получить для времени работы алгоритма рекуррентное соотношение Г(га) = 2Г(га/2) + 0(п) (здесь Г(га) - время обработки га точек). Чтобы этого достичь, мы должны предполагать, что входные массивы X и У отсортированы по абсциссе и ординате соответственно (тогда разделить множество на левую и |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||